Editorial for Codeforces Round 920 (Div. 3)

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

1921A - Square

Tutorial

Solution

t = int(input())
for _ in range(t):
    a = [[int(x) for x in input().split()] for i in range(4)]
    x = [p[0] for p in a]
    dx = max(x) - min(x)
    print(dx * dx)

1921B - Arranging Cats

Idea: pashka, prepared: ikrpprppp

Tutorial

Solution

t = int(input())

for _ in range(t):
    n = int(input())
    start = [int(x) for x in input()]
    finish = [int(x) for x in input()]
    pairs = list(zip(start, finish))
    add_amnt = sum(int(a < b) for a, b in pairs)
    rmv_amnt = sum(int(a > b) for a, b in pairs)
    print(max(add_amnt, rmv_amnt))

1921C - Sending Messages

Idea: step_by_step, prepared: step_by_step, Vladosiya

Tutorial

Solution

t = int(input())
for _ in range(t):
    n, f, a, b = map(int, input().split())
    m = [0] + [int(x) for x in input().split()]
    for i in range(1, n + 1):
        f -= min(a * (m[i] - m[i - 1]), b)
    print('YES' if f > 0 else 'NO')

1921D - Very Different Array

Idea: Vitaly503, prepared: pashka

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

struct test {
   void solve() {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        vector<int> b(m);
        for (int i = 0; i < m; i++) cin >> b[i];
        sort(a.begin(), a.end());
        sort(b.rbegin(), b.rend());
        vector<int> c(n);
        long long s = 0;
        for (int i = 0; i < n; i++) {
            c[i] = b[m &mdash; n + i];
            s += abs(c[i] &mdash; a[i]);
        }
        long long res = 0;
        for (int k = 0; k <= n; k++) {
            res = max(res, s);
            if (k < n) {
                s -= abs(c[k] &mdash; a[k]);
                c[k] = b[k];
                s += abs(c[k] &mdash; a[k]);
            }
        }
        cout << res << "\n";
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        test().solve();
    }
    return 0;
}

1921E - Eat the Chip

Idea: ikrpprppp, prepared: ikrpprppp

Tutorial

Solution

def solve():
    h, w, xA, yA, xB, yB = map(int, input().split())

    if (xA - xB) % 2 == 0:
        winner = "Bob"
        if xA >= xB:
            win = False
        elif yA == yB:
            win = True
        else:
            if yA < yB:
                n_turns = yB - 1
            else:
                n_turns = w - yB
            win = xB - 2 * n_turns >= xA

    else:
        winner = "Alice"

        xA += 1
        yA += 0 if yB - yA == 0 else 1 if yB - yA > 0 else -1

        if xA > xB:
            win = False
        elif yA == yB:
            win = True
        else:
            if yA < yB:
                n_turns = w - yA
            else:
                n_turns = yA - 1
            win = xB - 2 * n_turns >= xA

    print(winner if win else "Draw")


t = int(input())

for _ in range(t):
    solve()

1921F - Sum of Progression

Idea: Vitaly503, prepared: Vitaly503

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

long long precalc[322][200322];
long long precalci[322][200322];

void solve() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    int pivot = 1;
    while (pivot * pivot < n) {
        pivot++;
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < pivot; i++) {
        for (int j = 0; j <= i; j++) {
            precalc[i][j] = 0LL;
            precalci[i][j] = 0LL;
        }
        for (int j = 0; j < n; j++) {
            precalci[i][j + i + 1] = precalci[i][j] + a[j] * (j / (i + 1) + 1);
            precalc[i][j + i + 1] = precalc[i][j] + a[j];
        }
    }
    while (q--) {
        int s, d;
        long long k;
        long long ans = 0;
        cin >> s >> d >> k;
        s--;
        if (d > pivot) {
            for (int i = s; i <= s + (k - 1) * d; i += d) {
                ans += a[i] * ((i - s) / d + 1);
            }
            cout << ans << " ";
            continue;
        }
        long long last = s + d * k - d;
        int first = s;
        cout << precalci[d - 1][last + d] - precalci[d - 1][first] -
                (precalc[d - 1][last + d] - precalc[d - 1][first]) * (first / d) << ' ';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tests;
    cin >> tests;
    while (tests--) {
        solve();
        if (tests) cout << "\n";
    }
    return 0;
}

1921G - Mischievous Shooter

Idea: Vitaly503, prepared: goncharovmike

Tutorial

Solution

//ciao_chill
#include<bits/stdc++.h>
using namespace std;
#define int long long

int n, m, k;
vector<vector<int>> a;


bool prov(int i, int j) {
    return 0 <= i && i < n && 0 <= j && j < m;
}

int ans() {
    int cnt = 0;
    int dp[n][m];
    int pref[n][m];
    int pref_up[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            pref_up[i][j] = a[i][j];
            if (prov(i - 1, j))
                pref_up[i][j] += pref_up[i - 1][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = m - 1; j >= 0; j--) {
            pref[i][j] = a[i][j];
            if (prov(i - 1, j + 1))
                pref[i][j] += pref[i - 1][j + 1];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dp[i][j] = pref_up[i][j];
            if (prov(i - k, j))
                dp[i][j] -= pref_up[i - k][j];
            if (prov(i, j - 1))
                dp[i][j] += dp[i][j - 1];
            if (j < k) {
                int i1 = j - k + i;
                if (i1 >= 0)
                    dp[i][j] -= pref[i1][0];
            }
            else
                dp[i][j] -= pref[i][j - k];
            if (prov(i - k, j))
                dp[i][j] += pref[i - k][j];
            cnt = max(cnt, dp[i][j]);
        }
    }

    return cnt;
}

void solve() {
    cin >> n >> m >> k;
    k++;
    char c;
    bool st[n][m];
    a.resize(n);
    for (int i = 0; i < n; i++) {
        a[i].resize(m);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
        {
            cin >> c;
            st[i][j] = (c == '#');
            a[i][j] = st[i][j];
        }
    }

    int mx = ans();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = st[n - i - 1][j];
        }
    }
    mx = max(mx, ans());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = st[i][m - j - 1];
        }
    }
    mx = max(mx, ans());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = st[n - i - 1][m - j - 1];
        }
    }
    mx = max(mx, ans());

    cout << mx << '\n';

}

signed main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int tt;
    cin >> tt;
    while (tt--)
        solve();

    return 0;
}

S[0] = |a[0] - b[m-n]| + .. + |a[n-1] - b[m-1]| S[1] = |a[0] - b[0]| + (S[0] - |a[0] - b[m-n]|) S[2] = |a[1] - b[1]| + (S[1] - |a[1] - b[m-n+1]|) . . . S[n] = |a[n-1] - b[n-1]| + (S[n-1] - |a[n-1] - b[m-1]|)

Comments (83)

Write comment?

goextreme

10 months ago, # |

nice E and F

→ Reply

I_love_Leyeli_Meredova

10 months ago, # ^ |

-12

в задаче Е в последней строчке написано Элис хотя должно быть Алиса

kevbamboo

+12

The problems were nice. I solved A-E in-contest and F about 10 hours later.

For some reason I feel like E was easier to figure out than D.

Also my F submission is in-queue even though it got accepted earlier (?)

baijin_xu

9 months ago, # ^ |

I agree that.E was easier than D

cerelac

+17

prefixsum forces

bgopc

Beautiful problems specially a to f Couldnt figure out g in time I misread a,b both which was abs terrible since the penalty I got from both was almost as twice as usual For A I thought that the squares aren't parallel to the Axis so I wrote a function to validate the squares, the i assumed every possible square and find the max Before I code the last part just reread the ! Question and...

0x3F

Video solution of F (Chinese)

vimwang

Why D can use prefix sum without considering absolute value symbols?

DavidBarbu

I reached 1000 and I am so happy. Hope to reach pupil soon!

R2M

Finally crossed 1500. Had no idea how to solve F.

djm03178

← Rev. 8 →

I wonder what the intention for the strict limits for F was. The model solution 241944593 runs in approximately 1s, which is around half of the limit, and it consumes almost full memory allowed (1010600 KB).

The very same solution reaches very close at the limit just by swapping the array dimensions that leads to a worse cache hit rate: 241946807, which is what my own solution 241780298 exactly did and barely passed.

It's quite unfriendly with other slower languages, and with only a few trivially inefficient elements it's easy to exceed the time limit as well as the memory limit. It would've made more sense to set a bit more lenient TL and ML as done in problem G.

pashka

+11

It's always a tradeoff. The problem here is that the optimized naive solution, written in good C++ works about 2.5 s, so we cannot extend the TL any further.

That's a lot faster than I imagined. Guess you couldn't really do much about the ML as well as Polygon only allows up to 1024 MB ML.

Oh, i checked again and I was wrong, we added more tests with many long sequences, and not it works more than 4s, but still pretty close.

yadavDipesh

indeed the time limit is too tight.
same code after converting to c++ by gpt works in 900ms whereas it gives tle on test 3 in java

Yes, maps and lists are much slower in Java

But there are a lot of accepted submissions in Java, actually. Here is one for example https://codeforces.me/contest/1921/submission/243773379

It's sad that you cannot use standard java containers in problems with such strict time limits, but I don't think we can do anything about it.

I solved a lot of contests in Java, and at some point I learned how to implement anything using only simple arrays, but it's painful, I agree. That's why I moved to C++ for contests at some point.

Thanks for the reply
Instead of map and arraylists, I used 2d array and the case which was giving TLE now passes in 450ms

EgorUlin

Solution for G without prefix sums: 241838352.

The idea is very similar to the author's solution with prefix sums over $$$O(nm)$$$, but in this solution the recalculation is done over $$$O(\text{min}(n, m))$$$. In this solution, I go through all the red squares (from the parsing) and subtract them, and I also go through and add all the green squares.

The total time complexity of this solution is $$$O(nm\ \text{min}(n, m))$$$.

vivekshah777

E was doable

_Spongey

Fr but never thought E would be just if elses lol

humane_rdgfc

i also had same intution for D as editorial ,but so much less confidence in contest .can anyone please justify why the greedy approach(same as editorial) will work.

@authors

Always, the difference between minimum and maximum is the max possible to get... Wym

it is maximum diff now ,but by taking out maximum such element,we might be reducing maximum difference for second smallest element. you are saying local optimum decision will lead to global optimum(that is exactly greedy),i am asking why it will always result in optimum answer

vstiff

Usually proving that swapping any two elements doesn't improve the answer is enough.

Azzmi

See my submission first before reading the proof.

The greedy approach can be neatly summarized as choosing the pair that gives the largest absolute difference and then we can pop the two corresponding elements and then we can continue doing the greedy.

We need to prove two things:

(1) That the largest distance is either abs(a.front() - b.back()) or abs(a.back() - b.front()).

Proof. Note that any selected pair a[i] and b[j] have an associated direction from a[i] to b[j] in the number line (either right or left). If the direction is right, we can make the difference larger if we change a[i] to a.front() and b[j] to b.back(). The case is similar to if the direction is left.

(2) Choosing the largest difference is optimal.

Proof. Without loss of generality, assume that abs(a.front() - b.back()) gives the largest difference. Assume that the two pairs are (a.front(), b[j]) and (a[i], b.back()) (other cases like when a.front() or b.back() is not paired is trivial). Then by swapping, it's easy to visualize that (a.front(), b.back()) and (a[i], b[j]) is not worse.

rubiks1729

can u pls elaborate (2) choosing largest difference is optimal "Assume that the two pairs are (a.front(), b[j]) and (a[i], b.back())" what are we assuming

Then by swapping, it's easy to visualize that (a.front(), b.back()) and (a[i], b[j]) is not worse. After swapping what is not worse than what?

avighnakc

7 months ago, # ^ |

In the second part, he's saying 'let's assume that we pair up a.front() with some other element in b that is not b.back(), and pair b.back() with something else in a'. Then if we swap b[j] with b.back() to get the pairs (a.front(), b.back()) and (a[i], b[j]), the sum of the absolute differences in this case won't be worse than the previous one.

KisuraOP

The Solution Code of D may meet some display problem?

On my view, there are some — in the brackets of abs(), they look like:

c[i] = b[m &mdash; n + i];
s += abs(c[i] &mdash; a[i]);

I don't know if it's an issue with my browser.

I_need_7.0_IELTS

actually the &mdash is the minus sign -

SuperMo

what does that line mean c[i] = b[m — n + i]; is it b[m-n+i] or what is it

Ayush_Raj100

Yup

RPGLILSTAR

Me too! It's confusing!!!

+10

Can someone explain why are we taking d=sqrt(q) ?

+23

We want to minimize $$$nd + qn/d$$$, When we increase $$$d$$$, the first part will increase, and the second part will decrease, and the minimal point will be when they become equal: $$$nd = qn/d$$$, from that we can get $$$d=\sqrt{q}$$$.

yvbf

We can also sort queries by $$$ (d,s \mod d) $$$, and for all queries with same $$$ (d,s \mod d) $$$, we preare the prefix sum using items : $$$ a_{s \mod d}, a_{d+s \mod d},a_{2 \cdot d+s \mod d}, \cdots $$$, which are $$$ \frac{n}{d} $$$ items in total. For some fixed $$$d$$$, $$$d$$$ queries would be needed to make prefix sum calculation cover the whole $$$n$$$ array. Worst case is when $$$ 1+2+3+ \cdots + x=q$$$, get $$$x \approx \sqrt q $$$ , so the total time complexity of prefix sum preparing is $$$n \sqrt q $$$.

I get really stuck when it comes to understanding the problems so deeply with respect to constraints.

say_yas

Can Problem D be solved with dynamic programming approach? dp[i][j] = maximum diff when a[i] is paired with b[j].

transition: dp[i][j] = abs(a[i]-b[j])+max value from dp[i-1] (other than dp[i-1][j] as jth element is paired with current element.)

return max value from dp[n-1];

is this approach correct?

Tobzhan

I also thought about dp but finding max value from dp[i-1] takes O(m) or I can not come up with better way to do it, overall it will be slow.
Personally I solved it by sorting both arrays and using two pointers on each of them and taking values by greedy approach.

I thought something like this .We will need to keep 2 largest values from the dp[i-1] array . As mostly we will use largest value and if the currently chosen index is equal to index with greatest in dp[i-1] then we will use the second largest value. We can maintain this values in such array maxValue[n][2] and update it while processing dp states.

l_love_CP

-9

почему моё решение 241780647 использует multiset но в тегах не было добавлено структуры данных?

Shofiqur

← Rev. 3 →

Editorial is not attached as "Tutorial" in problem statement page yet. May it would be fixed.. UPD: Fixed Now..

humblebose

bklode

rishabhxchoudhary

F Video editorial + Live Coding (English): https://youtu.be/mJVq_nW8iQk

weiron_RX

Thank u man, really helped me

Welcome

MaxWelll

Can someone help my find out why my submission to E gives WA?: expected: 'DRAW', found: 'BOB'

smit_384

← Rev. 2 →

why you are doing wins==true in if(w — ya — 1 <= dh /2) and in else aslo ? in else there will be draw

Thank you!

What a silly mistake...

ShaoNianTongXue5307

+19

who setted this problem G and why

Heap_OverFlow

Sirs teaching Englishs. 😂

So spreading the awareness xD

Red0

After 18 contests, I've finally reached specialist, and so far, the only active specialist in Seattle! :)

MatthewC3297

I have an alt. sol for F that uses memoization.

Suppose we split the array into $$$d$$$ subsequences of increment $$$d$$$ for every $$$d$$$ from $$$1$$$ to $$$n$$$.

Ex: Original array is $$$[1,2,3,4,5]$$$

$$$d = 1: [1,2,3,4,5]$$$

$$$d = 2: [1,3,5],[2,4]$$$

$$$d = 3: [1,4], [2,5], [3]$$$ (You get the idea)

If we can generate both the prefix sums and the partial sums of the values multiplied by their index (eg $$$[1,3,5]$$$ becomes $$$[1\cdot1, 1\cdot1 + 3\cdot2,1\cdot1 + 3\cdot2 + 5\cdot3] = [1,7,22]$$$.

We can use these two precomputed arrays to evaluate the queries efficiently. However, precomputing all of these will be too slow, instead, we can create them and store them as we process queries since we don't need to precompute every subsequence.

To store them, we would just need something like a map, the key would be a pair $$$(d,s\%d)$$$ where $$$d$$$ is the increment and $$$s\%d$$$ represents the first element's index of the subsequence.

The worst case is that for every query, we have to create both types of prefix sum arrays for the largest, not-yet-computed sequence. It should be clear that given array of size $$$n$$$ and $$$n$$$ queries, the total iterations should be around $$$O(n\sqrt{n})$$$ (or plus a log factor depending on which map).

My code: 241999941 (which uses custom hash + unordered map)

mega_bot

In problem c, doesn't the phone lose charge at 0 moment and also will the phone lose charge after it sends a message or before?

could someone explain?

Scyther_07

Can please tell me why is this submission giving a TLE for Problem F? (Time complexity: $$$O((N + Q) * sqrt(N))$$$)

umar.aligarh

Don't declare vectors(prefix sum) for every test case, make them of fixed size [10^5+1][320]

TheBhediyaOfDalalStreet

I have a nice greedy solution to D which just selects the largest possible distance at every iteration until all elements in $$$a$$$ have been paired, but I don't have a proof.

Code: 242031960

Can anyone prove it?

I have also used this method during the contest.

In sorted $$$ a_1, a_2, \cdots a_n $$$ and sorted $$$b_1,b_2, \cdots b_m$$$ , WLOG, let us assume max diff value is $$$ | a_1 - b_i |$$$. Obviously $$$i$$$ could only be $$$1$$$ or $$$m$$$ .

If $$$i=1$$$,

when $$$b_1 < a_1, |a_1-b_1|<|a_n-b_1|$$$ ,
when $$$b_1 > a_1, |a_1-b_1|<|a_1-b_m|$$$ ,
so $$$i \neq 1$$$.

If $$$i=m$$$,

when $$$b_m<a_1, |a_1-b_m|<|a_1-b_1|$$$,
so it must be $$$b_m>a_1$$$ .

Assume in optimal solution, $$$b_j$$$ paired with $$$a_1$$$ ,

if $$$b_m$$$ is not paired with any value in $$$a$$$, we can move $$$a_1$$$ from pair with $$$b_j$$$ to $$$b_m$$$ to get a better solution.
If $$$b_m$$$ is paired with some $$$a_k$$$ , since $$$a_1<a_k , b_j<b_m , a_1<b_m , |a_1-b_j|<|a_1-b_m|$$$ , it can be shown that $$$|a_1-b_j|+|a_k-b_m| \leq |a_1-b_m|+|a_k-b_j|$$$.

So, pair $$$a_1$$$ with $$$b_m$$$ must be in some optimal solution.

Thanks. You motivated me to prove it myself. I came up with a not-so-elegant proof with the same outline as yours

taarkik

Not able to figure out whats wrong with my solution https://codeforces.me/contest/1921/submission/242087071

AvaraKedavra

Don't understand the equations in F at all. Feels like editorial has been written for someone who already understands the solution.

"The key idea is that we know how to calculate the sum (i−l+1)⋅ai for l≤i≤r fast – we need to calculate all prefix sums i⋅ai and ai for 1≤i≤k, then take the difference between the r-th and (l−1)-th of i⋅ai and subtract the difference between the r-th and (l−1)-th multiplied by l−1"

This certainly could have been explained in a better way.

___JuBo

Thanks for the editorial!

codex47

Can somebody explain solution of problem E to me? I am just gonna type what I understood so somebody else won't have to type much.

From what I understood, Alice can only win when the distance is odd and vice versa(This part was intuitive). Draw happens when loser tries to dodge winner in the game as he knows he is gonna lose. So to draw losing player can run to either extreme left or right and If there's enough distance in either left or right they successfully dodge the winner.

Is this correct or am I missing something? Beside calculating all of this is too much as well.

case3

Correct. They will meet on some row which is predefined. At the meeting junction if its alice turn then bob has to run for draw or alice win or vice versa.It has comments

I can't understand what is the code doing in problem D like why are you using this code with some define lines that are not even written , please don't forget that there are some beginners here I can't figure out what is mdash

Somebody in comment already said that its just minus. Here's the link.

did you understand the code because I'm trying for more than 5 hours and reached nothing and I feel so tilted, the idea is so complicated , or maybe I'm just so dumb

There's a youtube video for this entire contest. It's in english by some master or cm. Link.

NO, I couldn't understand the solution they have given in editorial.

I'll try to explain how I did it.

Look from array b you want to choose n integers and arrange it in a order such that diff is maximum as stated in problem.

Now for every position if you think about it there are only four options.

First this is something for sake of notation. min of array a = mna, max of array a = mxa min of array b = mnb, max of array b = mxb

Now just create all 4 pairs using above numbers let's say d1 = abs(mna — mxa), d2 = abs(mna — mnb) and so on.

Now you just have to pick whatever is maximum.

So if you keep both a and b sorted and create 4 pointers each pointing to above mxa, mxb, mna, mnb. You can increment decrement pointers based on which one is maximum.

nice explanation thanks but there should be no point of trying (mna-mnb) and (mxa-mxb) and the other two will be enough right ?

Yeah those two cases are useless.

how did so many people solve D ,like is there any standard problem for it or I'm just bad at this because even after reading editorial and tracing almost 10 different codes I still don't think that I can come up with this my self at all, and with the problem being 1100 it's more frustrating

alexiuscp

DP/greedy problems are usually difficult to prove but the solutions are rather intuitive and rely largely on observation. After solving lots of DP/greedy problems, you will start to observe the patterns in these types of problems.

Basically the solution herein lies in the fact that we know the maximum sum is formed by using the largest/smallest elements in b.

To maximize the sum, greedily we want to pair largest b elements with smallest a elements, and vice versa because doing so, we get larger absolute differences.

The first idea is to greedily pair elements one by one such that their absolute difference is the largest. However, you may have noticed this solution does not always work.

The reason lies in the non-greedy structure of this problem, pairing something affects the maximum sum of absolute difference of remaining pairs in the future, and another pair which is not chosen greedily may be better.

Rather than forming the maximum sum, we could instead bruteforce over all possible maximum sums and update ans = max(ans, s). We know we could form the maximum sum by pairing elements of a with k largest elements and n-k smallest elements in b, for some k.

For simplicity's sake, we will use words and slowly transition into using variables.

After sorting a and b, we have..

a = smallest, smaller, .., smaller, .. largest
b = largest, larger, .., larger, .. smallest

Let's start by pairing a with the n smallest elements in b. There are many ways to arrange these in some order such that we get the maximum possible sum, but we can easily observe that the optimal order is always to pair the smallest with largest, for each element.

|smallest - larger| + .. + |largest - smallest| >=
|smallest - smallest| + .. + |largest - larger|

thereby using the corresponding indices,

|a[0] - b[m-n]| + .. + |a[n-1] - b[m-1]| >=
|a[0] - b[m-1]| + .. + |a[n-1] - b[m-n]|

With similar logic, we iteratively form the next sum by replacing the pair a[0],b[m-n] with a[0],b[0] and so on. We can easily calculate this updated sum in O(1) using S = S - |a[i]-b[m-n+i]| + |a[i]-b[i]|

Thus we form the possible maximum sums as such,

and thus, ans = max(S[0], S[1], .., S[n]).

Hello everyone. I am having trouble with problem F. I understand that its a standard problem but the part where we need to hop by d steps is making it hard for me to understand.

I have a scenario can someone please explain on this. d = 5, k=6, s=3

Here the sequence required is: a3 + 2a8 + 3a13 ... 6a28

I have 2 series which can be computed in O(1): S1 = a1 + a2 + a3 ... an S2 = a1 + 2*a2 + 3*a3 ... n*an

How can I get the required sum if someone is available to dry run it.

gardengnome

Precomputed prefix sums starting from index 3 with step size 5:

ps1 = a3 + 2a8 + 3a13 + 4a18 + 5a23 + ...

ps2 = a3 + a8 + a13 + a18 + a23 + ...

Let's say you want to compute the sum for 3 elements starting from index 13:

a13 + 2a18 + 3a23 = (3a13 + 4a18 + 5a23) -2*(a13 + a18 + a23)

You can get get these two parts from prefix sums ps1 and ps2.

There's a youtube video for this entire contest. It's in english by some master or cm. Link. Actually he just explains brute force approach so don't waste your time on it.

Brute force approach is easy to figure out but I am not able to understand editorial. All I understand is they are multiplying it by some value in order to reduce time complexity when running the queries. What is even the intuition behind the solution?

Can somebody explain the intuition or Is it just way above my level so I should leave it?

Maybe putting summed indexes this way helps:

1 2 3 4 5 6
  2 3 4 5 6
    3 4 5 6
      4 5 6
        5 6
          6

If you need sum from 4 to 6 then you have to subtract triangle 1..3 and rectangle of top 3 lines which is (4+5+6)*3 = (sum without multiplication) * (s/d)

After some optimisations you get answers quite fast.