0
$\begingroup$

Problems:

A table with $n$ rows and $m$ columns is filled with number from $1$ to $100$ (duplication allowed). The player starts at $(1, 1)$. He can only move right or down. The goal is to reach $(n, m)$. Let $S$ be the product of numbers the player has met along the way to $(n, m)$. Find maximum number of trailing zeros of $S$ if the player moves optimally.

What I think about this problem is to use Dynamic Programming. $S$ is equal to $2^x\times5^y\times other\ primes$ so the answer should be $min(x, y)$ but finding maximum $x$ or $y$ is not optimal. $min(x, y)$ instead should be maximized. Please help with this problem.

$\endgroup$
1
$\begingroup$

For each cell $(i,j)$, store the set of possible pairs $(x,y)$'s.

Now, DP by scanning row-major from top row to bottom row, for each cell $(i,j)$, only needs to consider $(i,j-1)$ and $(i-1,j)$ (if any), either choose or not to choose $(i,j)$. So from the stored set in $(i,j-1)$ and $(i-1,j)$, compute $(i,j)$'s set easily.

Try to finish the above idea in details. And then code it in your favorite programming language will quickly improve your DPing skill.

$\endgroup$
  • $\begingroup$ My idea is to let $DP(i, j ,k)$ equals to the maximum 2s at $(i, j)$ with $k$ 5s. The transition would be $DP(i, j, k) = max(DP(i-1, j, k-P_5), DP(i, j-1, k-P_5)) + P_2$ for arbitrary $k$ where $P_2$ and $P_5$ are number of 2s and 5s in cell $(i, j)$ respectively. Thanks for your help. It really help me solve this problem. $\endgroup$ – PeppaPig Sep 30 '18 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.