Hi,
I’m doing the problem The least round way, and I have two solutions: One is an O(N^2) DP solution, and the other is O(N^2\log N) dijkstra. Both solutions pass the first 30 test cases, but TLE on the 31st test case. There are no infinite loops in either solution.
For the solutions, I find the minimum \nu_2 and \nu_5 of all paths, then take the minimum of these to find the least round path.
Here are the links to my submissions:
Here’s my DP solution:
#include <climits>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
const int MAX_N = 1000;
int min_v2[MAX_N][MAX_N] {};
int min_v5[MAX_N][MAX_N] {};
int main() {
cin.tie(0)->sync_with_stdio(0);
// freopen("sss.in", "r", stdin);
// freopen("team.out","w",stdout);
int n; cin >> n;
vector<vector<int>> v2 (n);
vector<vector<int>> v5 (n);
for (int i = 0; i < n; i++) {
v2[i] = vector<int> (n);
v5[i] = vector<int> (n);
for (int j = 0; j < n; j++) {
int cur; cin >> cur;
int copy = cur;
while (copy % 2 == 0) {
v2[i][j]++;
copy /= 2;
}
while (cur % 5 == 0) {
v5[i][j]++;
cur /= 5;
}
}
}
// transitions are going down or going right
min_v2[0][0] = v2[0][0];
min_v5[0][0] = v5[0][0];
for (int i = 1; i < n; i++) {
min_v2[i][0] = min_v2[i-1][0] + v2[i][0];
min_v5[i][0] = min_v5[i-1][0] + v5[i][0];
min_v2[0][i] = min_v2[0][i-1] + v2[0][i];
min_v5[0][i] = min_v5[0][i-1] + v5[0][i];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
min_v2[i][j] = min(min_v2[i-1][j], min_v2[i][j-1]) + v2[i][j];
min_v5[i][j] = min(min_v5[i-1][j], min_v5[i][j-1]) + v5[i][j];
}
}
// trace backwards to find the steps
string steps;
if (min_v2[n-1][n-1] < min_v5[n-1][n-1]) {
cout << min_v2[n-1][n-1] << "\n";
int i = n - 1, j = n - 1;
while (!(i == 0 && j == 0)) {
if (i > 0 && min_v2[i][j] == min_v2[i-1][j] + v2[i][j]) {
steps.push_back('D');
i--;
} else {
steps.push_back('R');
j--;
}
}
reverse(steps.begin(), steps.end());
cout << steps << "\n";
} else {
cout << min_v5[n-1][n-1] << "\n";
int i = n - 1, j = n - 1;
while (!(i == 0 && j == 0)) {
if (i > 0 && min_v5[i][j] == min_v5[i-1][j] + v5[i][j]) {
steps.push_back('D');
i--;
} else {
steps.push_back('R');
j--;
}
}
reverse(steps.begin(), steps.end());
cout << steps << "\n";
}
}
Here’s my Dijkstra solution:
#include <climits>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;
pair<int, string> dijkstra(int n, vector<vector<int>>& matrix) {
vector<vector<int>> min_sum;
for (int i = 0; i < n; i++) {
min_sum.push_back(vector<int> (n, -1));
}
using T = pair<pair<int, int>,int>;
priority_queue<T, vector<T>, greater<T>> pq;
pq.push({{0, 0}, matrix[0][0]});
while (!pq.empty()) {
int i, j, val;
i = pq.top().first.first;
j = pq.top().first.second;
val = pq.top().second;
pq.pop();
if (min_sum[i][j] >= 0)
continue;
min_sum[i][j] = val;
if (i < n - 1)
pq.push({{i+1, j}, val + matrix[i+1][j]});
if (j < n - 1)
pq.push({{i, j+1}, val + matrix[i][j+1]});
}
string steps;
int i = n - 1, j = n - 1;
while (i > 0 || j > 0) {
if (i > 0 && min_sum[i][j] == min_sum[i - 1][j] + matrix[i][j]) {
steps.push_back('D');
i--;
} else if (j > 0 && min_sum[i][j] == min_sum[i][j - 1] + matrix[i][j]) {
steps.push_back('R');
j--;
}
}
reverse(steps.begin(), steps.end());
return {min_sum[n-1][n-1], steps};
}
int main() {
cin.tie(0)->sync_with_stdio(0);
// freopen("team.in","r",stdin);
// freopen("team.out","w",stdout);
int n; cin >> n;
vector<vector<int>> v2 (n);
vector<vector<int>> v5 (n);
for (int i = 0; i < n; i++) {
v2[i] = vector<int> (n);
v5[i] = vector<int> (n);
for (int j = 0; j < n; j++) {
int cur; cin >> cur;
int copy = cur;
while (copy % 2 == 0) {
v2[i][j]++;
copy /= 2;
}
while (cur % 5 == 0) {
v5[i][j]++;
cur /= 5;
}
}
}
int min_v2; string v2_steps; tie(min_v2, v2_steps) = dijkstra(n, v2);
int min_v5; string v5_steps; tie(min_v5, v5_steps) = dijkstra(n, v5);
if (min_v2 < min_v5) {
cout << min_v2 << "\n";
cout << v2_steps << "\n";
} else {
cout << min_v5 << "\n";
cout << v5_steps << "\n";
}
}
The issue is that several test cases with N=1000 pass comfortably within the time limits. The last few test cases for the DP solution pass in about 150 ms, but the 31st times out.
I tried generating troubling test cases, but these too also pass in about 150 ms.
Here’s my generator:
#include <climits>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <vector>
#include <random>
using namespace std;
using ll = long long;
int main() {
cin.tie(0)->sync_with_stdio(0);
// freopen("fencedin.in","r",stdin);
freopen("input.txt","w",stdout);
random_device dev;
mt19937 rng(dev());
uniform_int_distribution<mt19937::result_type> dist6(1e7,1e8);
random_device dev2;
mt19937 rng2(dev2());
uniform_int_distribution<mt19937::result_type> dist7(0,3);
cout << "1000\n";
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
int cur = dist7(rng2);
int val = dist6(rng);
if (cur < 2) {
val *= 2;
}
if (cur % 2 == 0) {
val *= 5;
}
cout << val << " ";
}
cout << "\n";
}
return 0;
}
And here’s the result of the last testing:
Screenshot
Could someone explain what is wrong? Thank you!