### techneer's blog

By techneer, history, 3 years ago, ,

I'm stuck with this problem. My code is alwyas "time-exceeded" in test cast 31 even if I implemented DP-solution with n^2.

Could anyone tell me why my code never passes the test cases?

Below is my code.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int matrix[1001][1001];
int count2[1001][1001];
int count5[1001][1001];
char dir2[1001][1001];
char dir5[1001][1001];

int factor_of_k(int n, int k)
{
int count = 0;

while (n % k == 0)
{
n /= k;
count++;
}

return count;
}

int main()
{
int n;

cin >> n;

for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> matrix[i][j];

for (int i = 0; i <= n; i++)
{
count2[i][0] = 1999999999;
count2[0][i] = 1999999999;
count5[i][0] = 1999999999;
count5[0][i] = 1999999999;
}

for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
int up = count2[i-1][j];
int left = count2[i][j-1];

if (i == 1 && j == 1)
count2[i][j] = factor_of_k(matrix[i][j], 2);
else
count2[i][j] = min(up, left) + factor_of_k(matrix[i][j], 2);

dir2[i][j] = (up < left ? 'D' : 'R');

up = count5[i-1][j];
left = count5[i][j-1];

if (i == 1 && j == 1)
count5[i][j] = factor_of_k(matrix[i][j], 5);
else
count5[i][j] = min(up, left) + factor_of_k(matrix[i][j], 5);

dir5[i][j] = (up < left ? 'D' : 'R');
}

if (count2[n][n] < count5[n][n])
{
cout << count2[n][n] << endl;

int i = n, j = n;
vector<char> path;

while (i != 1 || j != 1)
{
path.push_back(dir2[i][j]);

if (dir2[i][j] == 'D' && i >= 2) i--;
else j--;
}

for (int k = 0; k < path.size(); k++)
cout << path[path.size() - k - 1];

cout << endl;
}
else
{
cout << count5[n][n] << endl;

int i = n, j = n;
vector<char> path;

while (i != 1 || j != 1)
{
path.push_back(dir5[i][j]);

if (dir5[i][j] == 'D' && i >= 2) i--;
else j--;
}

for (int k = 0; k < path.size(); k++)
cout << path[path.size() - k - 1];

cout << endl;
}

return 0;
}



 » 3 years ago, # |   0 Auto comment: topic has been updated by techneer (previous revision, new revision, compare).
 » 3 years ago, # |   0 Auto comment: topic has been updated by techneer (previous revision, new revision, compare).
 » 3 years ago, # | ← Rev. 2 →   0 Taking the path with the minimum number of twos or the path with the minimum number of fives isn't sufficient to the get the answer. Try this testcase: 3 2 2 2 5 10 2 5 5 5 The answer should be 1, taking the path of all twos until the last number or the path with all fives except for the first two.
 » 2 months ago, # |   0 You are not considering the zeros in input while calculating the number of twos and fives for each input.Also if there is one zero in the input then the answer cannot exceed one.
•  » » 2 months ago, # ^ |   +6 dude hes offline for 3 months
•  » » » 2 months ago, # ^ |   +1 The last comment except this was 3 years ago too :/