techneer's blog

By techneer, history, 3 years ago, In English,

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, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by techneer (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by techneer (previous revision, new revision, compare).

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.