Unexpected TLE on Codeforces DP problem

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!