[Codeforces Global Round 13] Pekora and Trampoline — O(n) Solution

Revision en1, by prshnt19, 2021-03-01 21:51:27

The basic idea here is the same as given in the Editorial. So please read that first. Now to efficiently do this in O(n) we need to keep track of possible jumps Pekora can make from a given index.

Suppose we have an initial array of {4, 2, 2, 2, 3, 2}. We will traverse from left to right. Now we will start from index 0 (with value 4) because it is greater than 1. We will take it as the starting point. One thing we can observe is that we need to use it 3 times until it becomes 1. In doing so we will make a jump to 4th, 3rd and 2nd index in the 1st, 2nd and 3rd pass respectively. So all we have to do is find a way to store this so that when we come to a new index we already know how many times we will come to this index. I used an array for this to store the range which will be affected by the current index.

My Submission: 108827845

auto solve(vector<int> &A) {
    int i, j, diff, n = A.size();
    ll ans = 0;
    vector<int> C(n + 1);

    auto add = [&](int i, int x) {
        if (i > n) i = n;
        C[i] += x;
    };
    auto sub = [&](int i, int x) {
        if (i > n) i = n;
        C[i] -= x;
    };

    for (i = 0; i < n; i++) {
        if (i) C[i] += C[i - 1];
        diff = A[i] - max(A[i] - C[i], 1);
        add(i + A[i] - diff + 1, 1);
        sub(i + A[i] + 1, 1);
        A[i] -= diff;
        if (C[i] > t) {
            add(i + 1, C[i] - diff);
            sub(i + 2, C[i] - diff);
        }
        if (A[i] > 1) {
            add(i + 2, 1);
            sub(i + A[i] + 1, 1);
            ans += A[i] - 1;
            A[i] = 1;
        }
    }
    return ans;
}
Tags #global round 13, global round, #efficient solution, # solution

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English prshnt19 2021-03-01 21:52:29 7 Tiny change: 'f (C[i] > t) {\n ' -> 'f (C[i] > diff) {\n '
en1 English prshnt19 2021-03-01 21:51:27 1778 Initial revision (published)