กำหนดให้ $(r, c)$ แทนช่องในตารางแถว $r$ คอลลัมน์ $c$ และ $A_{r, c}$ แทนค่าในตารางช่อง $(r, c)$ และกำหนดให้ $f(i, j) = k$ เมื่อ $k$ เป็นจำนวนเต็มที่มากที่สุดที่ $j^k$ หาร $i$ ลงตัว

ในข้อนี้ โจทย์ต้องการให้เราเดินจาก $(1, 1)$ ไปยัง $(n, m)$ โดยเดินไปทางขวาหรือลงล่างเท่านั้น เพื่อให้ผลคูณของค่าแต่ละค่าที่เดินผ่าน มีเลข 0 ลงท้ายมากที่สุดเมื่อเขียนในรูปของเลขฐานหก สำหรับจำนวนเต็ม $x$ ที่มี 0 ลงท้าย $k$ ตัวในเลขฐานหก เราจะได้ว่า $f(x, 6) = k$ เสมอ

สำหรับจำนวนเต็ม $x$ ที่มี $f(x, 6) = k$ เราจะสามารถสรุปได้ว่า $k = \min(f(x, 2), f(x, 3))$ เพราะ $6 = 2 \cdot 3$ ดังนั้น เมื่อ $f(x, 6) = k$ แล้ว แสดงว่า $2^k$ และ $3^k$ จะต้องหาร $x$ ลงตัว ดังนั้นในการหาคำตอบของข้อนี้ เราจึงต้องคำนึงถึงทั้งค่า $f(x, 2)$ และ $f(x, 3)$ ทั้งคู่

จากข้อสรุปด้านบนนี้ การที่เราต้องการให้คำตอบของเรามี 0 ลงท้ายมากที่สุดในเลขฐานหก เราจึงต้องทำให้ทั้ง $f(x, 2)$ และ $f(x, 3)$ มีค่ามากที่สุดไปพร้อมๆ กัน เพื่อให้ $min(f(x, 2), f(x, 3))$ มีค่ามากที่สุดที่เป็นไปได้ เราจะใช้ Dynamic Programming เข้ามาช่วย หากเรากำหนดให้ $dp(i, j)$ เป็นค่า $f(x, 6)$ ที่มากที่สุดเมื่อผลคูณที่เดินมายังช่อง $(i, j)$ เป็น $x$ เราจะไม่สามารถทำให้ $f(x, 2)$ และ $f(x, 3)$ มีค่ามากที่สุดไปในเวลาเดียวกัน

แต่เนืองจากตัว constraint ของ $n$ และ $m$ มีค่าน้อยมาก เราจึงนิยาม state ดังนี้แทน กำหนดให้ $dp(i, j, k)$ เป็น $f(x, 2)$ ที่มากที่สุดเมื่อผลคูณที่เดินมายังช่อง $(i, j)$ เป็น $x$ และ $x$ จะต้องหารด้วย $3^k$ ลงตัว การที่นิยามให้ $x$ จะต้องหาร $3^k$ ลงตัวแทนที่จะเป็น $2^k$ เพราะจะสามารถลด จำนวน state ที่ต้องคำนวณลงเนื่องจากผลคูณในการเดินอาจมี 2 เป็นตัวประกอบมากถึง ~1200 ตัวในขณะที่มี 3 เป็นตัวประกอบได้มากสุดเพียง ~800 ตัวโดยประมาณเท่านั้น และการที่นิยาม state ดังนี้ เราจะสามารถพิจารณาการเดินเพื่อทำให้ค่า $f(x, 2)$ มากที่สุดเท่านั้น ในขณะที่เราพิจารณาตัวประกอบที่เป็นยกกำลังของ 3 ทุกรูปแบบ

เราจะสามารถสรุป Transition ได้ดังนี้

$dp(i, j, k) = \max\{dp(i - 1, j, k - f(A_{i, j}, 3)), dp(i, j - 1, k - f(A_{i, j}, 3))\} + f(A_{i, j}, 2)$

ซึ่งมาจากการที่เรามีตัวประกอบ 3 เพิ่มเป็นจำนวน $f(A_{i, j}, 3)$ และตัวประกอบของ 2 เพิ่่มเป็นจำนวน $f(A_{i, j}, 2)$ ตัวเมื่อเดินผ่านช่อง $(i, j)$

เมื่อคำนวณค่าของ $dp(i, j)$ เป็นที่เรียบร้อยแล้ว คำตอบของข้อนี้จะเป็น $\max \limits_{0 \leq i \leq 800} \{min(i, dp(n, m, i) \}$

ซึ่งมาจากข้อสรุป $f(x, 6) = \min(f(x, 2), f(x, 3))$ ดังที่ได้กล่าวไว้ด้านบนนั่นเอง

โค้ดตัวอย่างดังนี้

#include <bits/stdc++.h>

using namespace std;

int n, m;
int dp[105][105][1005];

int main() {
  memset(dp, -1, sizeof dp);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      int a, p2 = 0, p3 = 0;
      scanf("%d", &a);
      for (; a % 2 == 0; a /= 2) // Finding f(A_(i, j), 2)
        p2++;
      for (; a % 3 == 0; a /= 3) // Finding f(A_(i, j), 3)
        p3++;
      if (i == 1 && j == 1) // Base Case
        dp[i][j][p3] = p2;
      else
        for (int k = p3; k <= 1000; k++) { // Transition
          if (dp[i - 1][j][k - p3] != -1)
            dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - p3] + p2);
          if (dp[i][j - 1][k - p3] != -1)
            dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - p3] + p2);
        }
    }

  int ans = 0;
  for (int i = 0; i <= 1000; i++) // Finding maximum answer
    ans = max(ans, min(i, dp[n][m][i]));
  printf("%d\n", ans);

  return 0;
}

Time Complexity: $\mathcal{O}(n \cdot m \cdot (n + m))$