JasonMendoza2008's blog

By JasonMendoza2008, 5 hours ago, In English

This code gets MLE but only uses, if I'm correct, three arrays of size n <= 2*10^5 for that problem: https://codeforces.me/contest/2038/problem/B.

Am I missing something?

I thought one long long was 8 Bytes and therefore 3*8*2*10^5 = 48*10^5 would be 4.8 MB?

Would love to be enlightened, thanks! Note that I'm not asking how to solve that problem, but rather why in the world I am getting MLE. Link to the MLE verdict: https://codeforces.me/contest/2038/submission/292217786

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

void solve() {
    long long n;
    cin >> n;
    vector<long long> a(n), a_copy(n);

    for (long long i = 0; i < n; i++) {
        cin >> a[i];
    }

    auto is_feasible = [&](long long target) -> bool {
        for (long long i = 0; i < n; i++) {
            a_copy[i] = a[i];
        }
        bool first_time = true;
        while (a_copy[0] > target || first_time) {
            first_time = false;
            for (long long i = 0; i < n; i++) {
                long long a_i = a_copy[i];
                if (a_i > target) {
                    long long excess = ((a_i - target) / 2) + ((a_i - target) % 2);
                    a_copy[i] -= 2 * excess;
                    long long nxt_idx = (i + 1) % n;
                    a_copy[nxt_idx] += excess;
                }
            }
        }
        return all_of(a_copy.begin(), a_copy.end(), [&](long long x) { return x == target; });
    };

    long long total_sum = accumulate(a.begin(), a.end(), 0LL);
    vector<long long> targets;

    for (long long i = 0; i <= total_sum / n; i++) {
        targets.push_back(i * n);
    }

    long long l_ptr = -1, r_ptr = targets.size() - 1;
    while (l_ptr < r_ptr) {
        long long mid = (l_ptr + r_ptr + 1) / 2;
        if (is_feasible(targets[mid] / n)) {
            l_ptr = mid;
        } else {
            r_ptr = mid - 1;
        }
    }

    if (r_ptr == -1) {
        cout << -1 << endl;
        return;
    }
    cout << total_sum - targets[l_ptr] << endl;
}

int main() {
    long long n_tests;
    cin >> n_tests;

    for (long long test_nb = 0; test_nb < n_tests; test_nb++) {
        solve();
    }

    return 0;
}
»
4 hours ago, # |
  Vote: I like it +6 Vote: I do not like it

Total_sum can be big, as a_i <= 10^9. When you do targets array it can be humongous it seems

  • »
    »
    4 hours ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Well it can go up to 10^5*10^9 which definitely fits in a long long, I don't see how that would be related to a MLE anyway?

    • »
      »
      »
      4 hours ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      The size of targets array would be 10^9

      • »
        »
        »
        »
        4 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah I'm stupid. Thanks..