How can I solve this problem using DP?

Question

Link to the question: http://codeforces.com/contest/2/problem/B

There is a n × n square matrix consisting of non-negative integers. You must find a way that

starts in the upper left cell of the matrix; each next cell is to the right or down from the current cell; the path ends in the lower right cell. moreover, if we multiply all the numbers along the way, the result should be the smallest "rounded". In other words, it must end with the smallest possible number of zeros.

input The first line contains an integer n (2 ≤ n ≤ 1000), n is the size of the matrix. Then follow n lines containing matrix elements (non-negative integers not exceeding 10 ^ 9).

Output On the first line print the least number of trailing zeros. In the second line print the corresponding path.

I thought about the following: in the end, whatever the answer, it should contain the minimum powers of 2 and 5. Therefore, for each entry in the input matrix, I calculated the powers of 2 and 5 and save them in separate matrices.

    for (i = 0; i < n; i++)
    {
        for ( j = 0; j < n; j++)
        {
            cin>>foo;
            matrix[i][j] = foo;
            int n1 = calctwo(foo);   // calculates the number of 2 in factorisation of that number
            int n2 = calcfive(foo); // calculates number of 5's
            two[i][j] = n1;
            five[i][j] = n2;
        }
    }

After that I did this:

for (i = 0; i < n; i++)
{
    for ( j = 0; j < n; j++ )
    {
        dp[i][j] = min(two[i][j],five[i][j]);  // Here, dp[i][j] will store minimum number of 2 and 5's. 
    }
}

But the above is not quite the right answer, I do not know why? Have I implemented the correct approach? Or is this the right way to resolve this issue?

Change: Here are my functions for calculating the number two and the number five in number.

int calctwo (int foo)
{
    int counter = 0;
    while (foo%2 == 0)
    {
        if (foo%2 == 0)
        {
            counter++;
            foo = foo/2;
        }
        else
            break;
    }
    return counter;
}

int calcfive (int foo)
{
    int counter = 0;
    while (foo%5 == 0)
    {
        if (foo%5 == 0)
        {
            counter++;
            foo = foo/5;
        }
        else
            break;
    }
    return counter;
}

Edit2: I / O example specified in the link:

Input:

3
1 2 3
4 5 6
7 8 9

Output:

0
DDRR

Answer 1

, 2, 5, nxn. ,

1 2 3
4 5 6
7 8 9

the powers of 2    the powers of 5       
0 1 0              0 0 0
2 0 1              0 1 0
0 3 0              0 0 0

. : , 2 , 5, . , dp: , , . , , :

 minimal path for the 
 powers of 2                 value
 * * -                         2
 - * * 
 - - *

 minimal path for the 
 powers of 5                 value
 * - -                         0
 * - - 
 * * *

 * - -                      
 * - - 
 * * *

0

1

, , , , , , : ? - . 2 2 a, 5 5 - b. , 2 (.. a < b). 5 c. : 5, 2 (.. c >= a?). , . , (.. c < a) 5, 2. 5 b, , 5- b 5 . . , c > b. c < a so a > b, , a < b. .

2

, 0. , , 1. , 1, 1 , 0.

Answer 2

. pair<int,int> 2 5.

#include<vector>
#include<iostream>
using namespace std;

#define pii pair<int,int> 
#define F first 
#define S second
#define MP make_pair

int calc2(int a){
    int c=0;
    while(a%2==0){
        c++;
        a/=2;
    }
    return c;
}

int calc5(int a){
    int c=0;
    while(a%5==0){
        c++;
        a/=5;
    }
    return c;
}

int mini(int a,int b){
    return a<b?a:b;
}

pii min(pii a, pii b){
    if(mini(a.F,a.S) < mini(b.F,b.S))
        return a;
    return b;
}

int main(){
    int n;
    cin>>n;
    vector<vector<pii > > v;
    vector<vector<int> > path;

    int i,j;
    for(i=0;i<n;i++){
        vector<pii > x;
        vector<int> q(n,0);
        for(j=0;j<n;j++){
            int y;cin>>y;
            x.push_back(MP(calc2(y),calc5(y)));   //I store factors of 2,5 in the vector to calculate
        }
        x.push_back(MP(100000,100000));     //padding each row to n+1 elements (to handle overflow in code)
        v.push_back(x);
        path.push_back(q);     //initialize path matrix to 0
    }

    vector<pii > x(n+1,MP(100000,100000));
    v.push_back(x);               //pad 1 more row to handle index overflow

    for(i=n-1;i>=0;i--){
        for(j=n-1;j>=0;j--){          //move from destination to source grid
            if(i==n-1 && j==n-1)
                continue;

            //here, the LHS of condition in if block is the condition which determines minimum number of trailing 0's. This is the same condition that is used to manipulate "v" for getting the same result. 
            if(min(MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S), MP(v[i][j].F+v[i][j+1].F,v[i][j].S+v[i][j+1].S)) == MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S))
                path[i][j] = 1;         //go down
            else
                path[i][j] = 2;         //go right
            v[i][j] = min(MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S), MP(v[i][j].F+v[i][j+1].F,v[i][j].S+v[i][j+1].S));
        }
    }

    cout<<mini(v[0][0].F, v[0][0].S)<<endl;   //print result
    for(i=0,j=0;i<=n-1 && j<=n-1;){           //print path (I don't know o/p format)
        cout<<"("<<i<<","<<j<<") -> ";
        if(path[i][j]==1)
            i++;
        else
            j++;
    }

    return 0;
}

. - , .

EDIT: .
, 2 . , , 2 , . , , .

- , . 2 5, , 0.

Answer 3

Javascript . :

• smallest_trailer, . 4 , "L", "R", "D" "U". . - . .
• zero_trailer(p,n,nbz) , p, n nbz . , . 2 5. pow_2_5(n), 2 5 n.
• : deepCopy(arr) arr, out_bound(i,j,n) true, (i,j) n, myMinIndex(arr) min 2- ( nb ). .
• MAX_SAFE_INTEGER () , (, ).

, , .

var MAX_SAFE_INTEGER = 9007199254740991;

function pow_2_5(n) {
  // returns the power of 2 and 5 inside n
  function pow_not_2_5(k) {
    if (k%2===0) {
      return pow_not_2_5(k/2);
    }
    else if (k%5===0) {
      return pow_not_2_5(k/5);
    }
    else {
      return k;
    }
  }
  return n/pow_not_2_5(n);
}

function zero_trailer(p,n,nbz) {
  // takes an input two numbers p and n that should be multiplied and a given initial number of zeros (nbz = nb of zeros)
  // n is the accumulator of previous multiplications (a power of 5 or 2)
  // returns an array [kbz, k] where kbz is the total new number of zeros (nbz + the trailing zeros from the multiplication of p and n)
  // and k is the new accumulator (typically a power of 5 or 2)
  function zero_aux(k,kbz) {
    if (k===0) {
      return [1,0];
    }
    else if (k%10===0) {
      return zero_aux(k/10,kbz+1);
    }
    else {
      return [kbz,k];
    }
  }
  return zero_aux(pow_2_5(p)*n,nbz);  
}

function out_bound(i,j,n) {
  return !((i>=0)&&(i<n)&&(j>=0)&&(j<n));
}

function deepCopy(arr){
  var toR = new Array(arr.length);
  for(var i=0;i<arr.length;i++){
    var toRi = new Array(arr[i].length);
    for(var j=0;j<arr[i].length;j++){
      toRi[j] = arr[i][j];
    }
    toR[i] = toRi;
  }
  return toR;
}

function myMinIndex(arr) {
  var min = arr[0][0];
  var minIndex = 0;
  for (var i = 1; i < arr.length; i++) {
      if (arr[i][0] < min) {
          minIndex = i;
          min = arr[i][0];
      }
  }
  return minIndex;
}

function smallest_trailer(grid) {
  var n = grid.length;
  function st_aux(i,j,grid_aux, acc_mult, nb_z, path) {

    if ((i===n-1)&&(j===n-1)) {          
      var tmp_acc_nbz_f = zero_trailer(grid_aux[i][j],acc_mult,nb_z);
      return [tmp_acc_nbz_f[0], path];
    }
    else if (out_bound(i,j,n)) {
      return [MAX_SAFE_INTEGER,[]];
    }
    else if (grid_aux[i][j]<0) {
      return [MAX_SAFE_INTEGER,[]];
    }
    else {
      var tmp_acc_nbz = zero_trailer(grid_aux[i][j],acc_mult,nb_z) ;
      grid_aux[i][j]=-1;
      var res = [st_aux(i+1,j,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"D"), 
                 st_aux(i-1,j,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"U"),
                 st_aux(i,j+1,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"R"),
                 st_aux(i,j-1,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"L")];
      return res[myMinIndex(res)];      
    }
  }
  return st_aux(0,0,grid, 1, 0, "");
}

myGrid = [[1, 25, 100],[2, 1, 25],[100, 5, 1]];
console.log(smallest_trailer(myGrid)); //[0,"RDDR"]
myGrid = [[1, 2, 100],[25, 1, 5],[100, 25, 1]];
console.log(smallest_trailer(myGrid)); //[0,"DRDR"]
myGrid = [[1, 10, 1, 1, 1],[1, 1, 1, 10, 1],[10, 10, 10, 10, 1],[10, 10, 10, 10, 1],[10, 10, 10, 10, 1]];
console.log(smallest_trailer(myGrid)); //[0,"DRRURRDDDD"]

Answer 4

.

https://app.codility.com/demo/results/trainingAXFQ5B-SZQ/

For a better understanding, we can simplify the task and assume that the matrix has no zeros (that is, the matrix contains only positive integers), then the Java solution will be as follows:

class Solution {
    public int solution(int[][] a) {
        int minPws[][] = new int[a.length][a[0].length];

        int minPws2 = getMinPws(a, minPws, 2);
        int minPws5 = getMinPws(a, minPws, 5);
        return min(minPws2, minPws5);
    }

    private int getMinPws(int[][] a, int[][] minPws, int p) {
        minPws[0][0] = pws(a[0][0], p);
        //Fullfill the first row
        for (int j = 1; j < a[0].length; j++) {
            minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
        }
        //Fullfill the first column
        for (int i = 1; i < a.length; i++) {
            minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
        }
        //Fullfill the rest of matrix
        for (int i = 1; i < a.length; i++) {
            for (int j = 1; j < a[0].length; j++) {
                minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pws(a[i][j], p);
            }
        }

        return minPws[a.length-1][a[0].length-1];
    }

    private int pws(int n, int p) {
        //Only when n > 0
        int pws = 0;
        while (n % p == 0) {
            pws++;
            n /= p;
        }
        return pws;
    }

    private int min(int a, int b) {
        return (a < b) ? a : b;
    }
}