The least round way

This problem looks like it wants some cursed DP on gigantic products. It doesn’t. You can throw the actual product in the trash and keep only the part that matters.

Observation 1: trailing zeros only care about $2$ and $5$

For any positive integer $x$, let $v_2(x)$ be the exponent of $2$ in its prime factorization, and $v_5(x)$ the exponent of $5$.

If a path $P$ uses cells $(i,j)$, then for the product along that path:

$$V_2(P)=\sum_{(i,j)\in P} v_2(a_{i,j}), \qquad V_5(P)=\sum_{(i,j)\in P} v_5(a_{i,j}).$$

The number of trailing zeros of a positive product is exactly

$$Z(P)=\min\bigl(V_2(P),V_5(P)\bigr).$$

So each cell contributes only two small costs: how many $2$'s and how many $5$'s it contains.

Observation 2: two separate DPs are enough

This is the real aha. A lot of people see

$$Z(P)=\min(V_2(P),V_5(P))$$

and immediately start inventing some monstrous DP state with both values. Don’t. That’s overkill.

Let

$$T=\min_P V_2(P), \qquad F=\min_P V_5(P),$$

where $P$ ranges over valid paths with non-zero product for now.

Then the optimal answer among those paths is exactly

$$\min(T,F).$$

Why?

• For every path $P$, we have $V_2(P) \ge T$ and $V_5(P) \ge F$, so

  $$Z(P)=\min(V_2(P),V_5(P)) \ge \min(T,F).$$

• Now take a path $P_2$ that achieves $T$. Then

  $$Z(P_2)=\min(V_2(P_2),V_5(P_2)) \le V_2(P_2)=T.$$

  Similarly, a path $P_5$ achieving $F$ satisfies

  $$Z(P_5) \le F.$$

So the optimum is both at least and at most $\min(T,F)$. Therefore it is exactly $\min(T,F)$.

That’s the whole trick. Two ordinary DPs, one for $2$'s and one for $5$'s. No black magic.

DP formulation

For each non-zero cell define

$$c_2(i,j)=v_2(a_{i,j}), \qquad c_5(i,j)=v_5(a_{i,j}).$$

Then run two grid DPs:

$$dp_2[i][j] = c_2(i,j) + \min\bigl(dp_2[i-1][j],\ dp_2[i][j-1]\bigr),$$ $$dp_5[i][j] = c_5(i,j) + \min\bigl(dp_5[i-1][j],\ dp_5[i][j-1]\bigr).$$

Boundary cells only have one predecessor, obviously.

To print the path, store a parent for each state:

• 'D' if the best predecessor is from above, i.e. from $(i-1,j)$,
• 'R' if it is from the left, i.e. from $(i,j-1)$.

Then backtrack from $(n-1,n-1)$ to $(0,0)$ and reverse the string.

Zero cells: the annoying special case

A value $0$ is special because factor counts are not useful there, and the product becomes $0$.

The standard trick for this problem is:

• remember any one zero cell $(z_x,z_y)$;
• in both DPs, treat zero cells as blocked / cost $+\infty$;
• this means the DPs search only among paths whose product stays positive.

After the DPs, let

$$ans = \min\bigl(dp_2[n-1][n-1],\ dp_5[n-1][n-1]\bigr).$$

If a zero exists and $ans > 1$, then going through that zero gives product $0$, and for this problem that is used as answer $1$. So it beats anything with at least $2$ trailing zeros.

So in that case we simply output:

• answer $1$,
• any monotone path that passes through $(z_x,z_y)$, for example $$D^{z_x} R^{z_y} D^{n-1-z_x} R^{n-1-z_y}.$$

This also cleanly handles cases where the start or finish cell itself is zero: the positive-product DP becomes impossible, and the forced-zero path gives answer $1$.

If $ans \le 1$, the zero trick is useless, so just print the better reconstructed DP path.

Correctness summary

• For positive-product paths, minimizing trailing zeros is equivalent to taking the better of:
  • the path minimizing total number of $2$'s,
  • the path minimizing total number of $5$'s.
• Those are exactly what the two DPs compute.
• If a zero exists and every positive-product path has answer at least $2$, then a path through zero gives answer $1$, which is strictly better.

That’s it. The problem looks scary because of the product, but the product is mostly bullshit noise.

Complexity

For each of the $n^2$ cells we do constant DP work, plus counting factors of $2$ and $5$ in a number up to $10^9$, which is tiny.

So the total complexity is

$$O(n^2)$$

time and

$$O(n^2)$$

memory.

With $n \le 1000$, that’s completely fine.