First.

F solution format is broken? last line of it

Bouns: solve C with n,k,q<=2e5

Interesting and thought-provoking problems! I really enjoyed this contest!

This contest might be one of my new favorites, even though Problem D absolutely DEMOLISHED me :3

D involves sorting, so I guess you should mention complexity as nlogn

For E, this my O(n) solution, which isn't magical at all.

void solve(){
    int n,k;
    cin>>n>>k;
    v<int> a(n*3+5);
    for(int x,i=0;i<n;++i){
        cin>>x;
        a[x]++;
    }
    int current_count = 0, current_source = -1;
    int ans = 0;
    for(int i=0;i<a.size();++i){
        a[i] += current_count;
        if(current_source !=-1 && current_count != 0){
            ans = max(ans, i-current_source);
        }
        if(a[i]>k){
            if(current_source == -1){
                current_source = i;
            }
            current_count = a[i]-1;
        }else{
            current_source = -1;
            current_count = 0;
        }
    }
    cout<<ans<<"\n";
}

Here's a $$$O(n)$$$ solution for E.

Although, the solution to F is correct and the margin of error is quite big. I don't think it is a practical approach during the contest.

Instead I used a similar solution that computed the cost of getting all answers to a certain modulo.

So we start with dp[1]=-1000, dp[x]=inf for all other x. The cost of starting position is -1000 as the first transition is discounted.

Then for increasing i,j we compute dp[i*j]=min(dp[i*j],dp[i]+n-n/j+1000*j)

The lowest cost is dp[y], y>=n.

My solution got down to cost of 923188 https://codeforces.me/contest/2157/submission/350336820 What was the lowest cost anyone got?

For E, you can just simulate the process in O(n) (this seems to be magic):

Implementation: https://codeforces.me/contest/2157/submission/350355897

Simpler sol'n to D

void solve() {
    long long n, l, r;
    cin >> n >> l >> r;
    vector<long long> v;
    long long b = 0;

    for (int i = 0; i < n; ++i) {
        long long a;
        cin >> a;

        if (a < l) {
            b += (l - a);       
            v.push_back(l);  
        }
        else if (a > r) {
            b += (a - r);      
            v.push_back(r);     
        }
        else {
            v.push_back(a);     
        }
    }

    sort(v.begin(), v.end());

    int k = v.size();
    for (int i = 0; i < k / 2; ++i) {
        b += (v[k - 1 - i] - v[i]); 
    }

    cout << b << "\n";
}

I don't understand question D, can someone explain the sample test cases pls?

The remaining elements are the ones which are only covered by a MEX constraint. In order to be satisfied, a MEX constraint must contain at least k such elements (because it must contain all the elements between 0 and k−1, which would violate a min constraint). In particular, assigning i mod k at the i-th such element works (if a MEX constraint contains k such elements, their values are [0,1,…,k−1], possibly shifted).

I don't understand why i%k works if i belongs to the MEX category.

Problem F was one of the most beautiful problem i have ever solved<3

What is wrong with my solution. The key idea was to decrease one occurrence of each value x, instead of increasing (cnt[x]-1) values by one.

Ah, seeing the solution for B now makes sense.

Damn I was close, shame I was late.

Really enjoyed my first attempt, cheers guys.

If anyone's up for helping, I genuinely do not understand where my solution failed for C: 350330832.

The part where I ran into issues was filling in the mexes, for which I greedily sorted them based on length and filled the free spaces with the remaining missing numbers. For some reason, that was incorrect.

Which problem was which at SWERC?

my solution to B: 350397978

I came up with this but can't prove why it works. Can someone explain it?

You can actually solve E by just simulating the operations in a smarter way. First, as in the editorial, you see that only the frequencies matter and you can make a priority queue that takes in a struct with 3 parameters: the index, the number of things that have the same value and how many operations it took for the numbers to get to this position ( if you have five 1's, the you can put in the priority queue the triplet {1,4,0} as the numbers are all one, there are 4 of them that need to be moved and they have been moved already 0 times).

Then, the priority_queue should keep the triplets in ascending order, sorted after the first number, the other 2 won't matter as you will see further ( so {3,2,0} is before {4,0,0} and after {2,9,1} ).

Then, you take the first triplet and before you increment the numbers, you see if there are any other pairs that share the first number from the triplet. If this is true, you can simply make one pair instead of the 2, and the resulting pair, if the other 2 are {a,b,c} , {a,d,e} would be {a,b+d,max(c,e)}, because you now have b+d numbers that need to be moved and the number of moves that it would take is just the biggest of the 2.

With this, you can still have a clean nlogn solution.

https://codeforces.me/contest/2157/submission/350358558

Can anyone help me in proving the correctness of this solution for today's D? I reached the solution through an observation by plotting on Desmos.

Isn't D basically just finding the distance of each number to the median? (https://codeforces.me/contest/2157/submission/350333441)

That's what I did, with the exception that if the median is outside the range of l <= x <= r, then you set this target median as l or r, whichever is closer, since that's the closest value to each value in the array while still being in the possible range.

I guess it's kind of said in the editorial with "The worst case is either x=l or x=r"

Dang... I'm happy I got to the point of F of getting every possible skill to be at n-2, n-4, n-6 etc. then to be at n-4, n-8, n-12 etc. but that ends up being over 2 million cost. Didn't know how to get the right segment length / layer / modulo / power, though I started trying to write a function to minimize.

"magical" O(n) solution for E: 350347721

#####
(none)
(none)
(none)
(none)

#
#
###
(none)
....

####
#####
....

a $$$O(n)$$$ solution for E

void solve() {
	int n, k; cin >> n >> k;
	vector<int> a(n+1), b(n*2+10);
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++) b[a[i]] ++;
	int r = 0, l = 0, ans = 0;
	for(int i=1;i<=n*2;i++) {
		if(i <= r) {
			r += b[i];
		} else if(b[i] > k) {
			ans = max(ans, r-l);
			r = i + (b[i]-k);
			l = i;
		}
	}
	ans = max(ans, r-l);
	cout << ans << '\n';
}

The statement of E is really terrible.

In problem H, was it known during testing that the most straightforward way of writing a brute force works? Just consider values from $$$1,2,\cdots,n$$$ in order, and decide whether to put each element on the left or right, write a dfs (with minimal pruning) and it passes.

It occured to me after I had submitted that it works because of the intended construction, the first branch tried will be $$$1,?,?,\cdots,?$$$, and the next branch will be $$$2,3,4,?,?,\cdots,?,1$$$.

I tried switching Left->Right to Right->Left and the code immediately gets TLE (xd), maybe it would be better to ask for anti-bitonic permutations after all?

I would say D have have a very simple solution, and its very natural to think that if(a[n/2]>=l && a[n/2]<=r) then we select a[n/2] as p because by median property we can say that sum of absolute difference between all elements and its median is minimum otherwise p = min(a[n/2],r) and p = max(a[n/2],l) and the code is ~~~~~ void solve() { ll n, l, r; cin >> n >> l >> r; vector a(n); repp(i, n) { cin >> a[i]; } sort(all(a)); ll ans = 0; ll median = a[n / 2]; median = max(l, a[n / 2]); median = min(r, median); for (int i = 0; i < n; i++) { ans += abs(a[i] — median); } cout << ans << endl;

} ~~~~~

`

please explain B, i tried to read that and not understandable.

In particular, since x, y >= 0, a 4 is a step either up or right while an 8 consists of two steps, one up and one right. So you make a + 2b steps in total, and only a + b of them can be in the same direction.

https://codeforces.me/contest/2157/submission/350375681

can somebody tell me why my code is not Correct For Problem C

Another solution to problem D using the mathematical median

We need to find the maximum possible score you can guarantee, that is, the minimum score we can win if we iterate all possible values of $$$p$$$ over $$$[l,r]$$$.

Let's solve an easier version of a problem with $$$l=1$$$ and $$$r=1e9$$$.

The mathematical median has an exciting property, the minimised absolute deviation property. In other words, for a sorted array $$$a_1,a_2,...,a_n$$$, $$$\sum_{i=1}^{n}|m-a_i|$$$ will be minimized if $$$m=a_\left\lfloor \frac{n}{2} \right\rfloor$$$, the array's median.

The answer would be $$$\sum_{i=1}^{n}|m-a_i|$$$.

Now, let's return to the original problem.

Define $$$m$$$ as the position in $$$[l,r]$$$ where we will win the minimum score. After we sort the array $$$a$$$, we will set the value of $$$m$$$ to be the median of $$$a$$$ if it is in the range $$$[l,r]$$$. Otherwise, $$$m=l$$$ if the median is strictly less than $$$l$$$, and $$$m=r$$$ if the median is strictly greater than $$$r$$$.

The answer would be $$$\sum_{i=1}^{n}|m-a_i|$$$, and the overall complexity is $$$O(nlogn)$$$.

My submission: 350340949

Bonus of G:

In each step we are using approximately a cost of $$$\sum_{i=1}^{100} \frac{1}{\max(i,101-i)} \approx 1.38$$$

Since the size is halved at every stage, we have $$$\log 100 \approx 6.64$$$ layers. So very very roughly do we use $$$1.38 \times 6.64 \approx 9.16$$$?

I did a O(N) solution for E, will leave the explanation if interested. It has the same objective of the editorial explanation, looking for the final value for each i where frec[i] > k.

Observation 1: Given an i where frec[i] > k, none of the indices j > i, where frec[j] > 0, will be the final value for i. The reason is that each time a frequency is passed from an index to another, atleast k positions are passed. So if the next index has a frequency > 0, then it will be atleast k+1 and will continue passing it on.

Think of indices with frec[index] > 0, as Xavi Alonso's (football player), every time a ball is given to index, it will pass it to the next index.

Observation 2: All elements that passed values will always be > 0. This means we are only interested in the elements with frequency = 0, and once an element with frequency = 0, passes the ball (value), it will become greater than 0.

We have frequencies different than 1 and frequencies equal to 1. Let an array A be a path where A_i, passed its frequencies to A_{i+1}. Note that all elements except the last will equal to 1.

Implementation: Iterate from 3*N to 1. We will store the values with frequency different than 1, and the idea is to maintain a sorted array with elements from [i+1, 3*n] that have frequency != 1. If the ith element has frequency > k, then iterate the array and start checking if it can be an endpoint or not, and accumulate the total frequencies passed. Note that there will be 0s and elements greater than 1, one will be a possible endpoint the other will add more frequencies. 350497294

    for(int i = 3*n; i>=1; --i){
        if(frec[i] > k){
            ll cur = 0;
            while(pending.size()){
                auto [idx, val]= pending.back();
                pending.pop_back();
                
                int right = cur + frec[i]+val; // assumes all elements from [i, idx] are already 1, so it only considers the sum without taking the 1s into account. This makes the 0s, -1s
                if(right <= k){
                    ans = max(ans, idx-i);
                    pending.push_back({i, right-1});
                    break;
                }
                cur += val;
            }
        }else{
            pending.push_back({i,frec[i]-1}); // It will be assumed that all frequencies 
        }
    } 

For Problem D, I believe using the median provides a simpler and cleaner solution. I would appreciate it if someone could review my implementation.

350522473

never thought I'd be able to see an easy Div2E (solvable by me) before GTA 6

We can actually analyze and solve problem F in a provably optimal way. The main idea is to analyze the problem the full tree of operations, instead of trying to construct the passes in blocks of $$$m$$$.

As in the editorial, we'll think of the state as a set of "alive values" which are possible. Each operation on must take an alive value $$$y$$$ and merge $$$y$$$ into the closest $$$y+l$$$ that's currently alive: there's no reason to pick a bigger $$$l$$$, since that wouldn't help us any more than just going to $$$y+l$$$, and there's no reason to pick a smaller $$$l$$$, since we could just delay the operation until we do merge $$$y+l$$$ (the relative order will never change, so the cost will be the same).

Let's fix the number of decreasing passes of operations as $$$d$$$, so that we pay $$$1000(d-1)$$$ for the passes.

Now, let's consider the (ordered) tree of merges of alive values over each pass. This tree should have $$$d+1$$$ layers, with $$$n$$$ leaves at the bottom, and each node's children form an interval of the next layer. A node's actual "alive value" is just the index of its rightmost leaf, since we always merge to the right; let the rightmost leaf of node $$$n$$$ be $$$r(n)$$$.

Now, let's analyze the total cost of the merges. Consider an interior node $$$n$$$ with children $$$c_0, c_1, \ldots c_t$$$. We have $$$r(n) = r(c_t)$$$, and we'll merge them from right to left over the pass and pay

We can simplify these differences, though: if we have $$$sz(n)$$$ be the number of leaves in the subtree of $$$n$$$, note that

Thus, the cost instead equals

Regrouping, we have the cost equals

Now, we can change the order of summation to group by each leaf. Let's label each leaf $i$ with an array $$$a_i$$$ of length $$$d$$$ corresponding to the path we take from the root to this leaf: leaf $$$i$$$ is in the $$$a_{i,j}$$$-th child at layer $$$j$$$. Then, the total cost of all operations is exactly

Thus, we can actually construct our tree by picking the smallest possible arrays $$$a_i$$$. After fixing $$$d$$$, we can construct at most $$$\binom{d + w - 1}{w}$$$ arrays $$$a_i$$$ with total sum $$$w$$$. We can pick them greedily, and then construct the tree afterwards.

For $$$n = 250000$$$, it turns out the optimal depth is $$$d = 113$$$ and the optimal cost is $$$855330$$$. This is the smallest depth where all leaves have weight $$$\le 3$$$.

Code: 350576854

Could somebody help me out in this problem, 2104D - Array and GCD in this question there is no constraints on coins if it is given that number of coins left in last should be zero. could somebody help me , as i am not able to think the solution,ecnerwala and TheScrasse

Didn't realise O(N) solution is already posted by someone for Problem E. My comment was redundant. removed for now. sorry.

DFS Round.

Hello. There is a typo in the editorial of problem H. "We can also transform a solution to (n,m) into a solution to (n+1,m+1)" should be "We can also transform a solution to (n,m) into a solution to (n+1,m)".

Here's my method for estimating the expected cost of problem G.

On the $$$i$$$-th layer of the trie. It divides the $$$n$$$ nodes into $$$2 ^ i$$$ parts. Consider what the MST of each part looks like.

Well, the longest edge connects the node with the minimum index and the maximum index, and then the node inside the range connects to the further node of the node with the minimum index and the maximum index.

In $$$i$$$-th layer, 'cause the testcases are generated randomly, we consider each part has a close number of nodes. So we consider each part has $$$\dfrac{n}{2 ^ i}$$$ nodes.

The range of the $$$k$$$ node randomly chosen from $$$n$$$ nodes is $$$r = \dfrac{k - 1}{k + 1}n$$$. For the other nodes, we consider the worst situation; the rest nodes are distributed near the middle of the range. So the distances are $$$\dfrac{d}{2}, \dfrac{d}{2} +1, \cdots$$$.

I used the following Python script to calculate it:

total = 0
for i in range(0, 6):
    n = 100
    delta = (n - (1 << i)) / (n + (1 << i)) * n
    print(delta)
    ans = 0
    ans += 1 / delta
    for j in range(1, int((n / (1 << i)) / 2)):
        ans += (1 / (delta / 2 + j)) * 2
    print(ans)
    total += ans * (1 << i)

print(total)

And the result is $$$9.140841614572105$$$.

https://codeforces.me/contest/2157/problem/C Can anybody explain where my code is wrong?

struct query {
    int l, r, t;
};

bool cmp(query &a, query &b) {
    if(a.l != b.l) return a.l < b.l;
    if(a.r != b.r) return a.r < b.r;
    return a.t < b.t;
}

void solve() {
    int n,k,q;
    cin >> n >> k >> q;
    vector<query> arr(q);
    for(int i=0; i<q; i++) {
        cin >> arr[i].t >> arr[i].l >> arr[i].r;
    }
    vi ans(n, k+1);
    sort(all(arr), cmp);
    for(int i=0; i<q; i++) { 
        if(arr[i].t == 1) {
            if(i>0 && arr[i-1].t == 2 && arr[i].l <= arr[i-1].r) {
                ans[arr[i-1].r] = k;
                continue;
            }
            ans[arr[i].l-1] = k;
            continue;
        }
        if(i == 0 || (i > 0 && arr[i].l > arr[i-1].r)) {
            for(int j= arr[i].l-1, cur = 0; cur < k; j++, cur++) {
                ans[j] = cur;
            }
        }
        else if(i > 0 && arr[i-1].t == 1) {
            for(int j = arr[i-1].r, cur = 0; cur < k; j++, cur++) {
                ans[j] = cur;
            }
        }
        else if(i > 0 && arr[i-1].t == 2) {
            int  j = arr[i-1].r, l = arr[i-1].l-1;
            while(j > 0 && ans[j-1] == k+1) j--;
            for(int cur=0; cur < k && j < arr[i].r; j++, cur++) {
                ans[j] = cur;
            }
        }
    }
    for(int v:ans) cout << v << " ";
    nl;
}

For E, this my O(n) solution.

Consider paving wave to the right. When paving way, either you create a new paved way, or you merged previous paved segments into one. So creating new and merging old paved way is in 2*n.

For element i with freq[i] (a = freq in code), you can stop if you finish pave freq[i] — k entries, and the total length of the paved way is the minimum number of operation (might merging with other paved road so that the final position of the bricks will be freq[i] — (freq[i] — k) = k.

Hopefully this can help you! Please let me know if further explanation is needed

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(2 * n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        x--;
        a[x]++;
    }

    int ans = 0;
    vector<pair<int, int>> ones;
    for (int i = 2 * n - 1; i >= 0; i--) {
        if (a[i] == 0) continue;
        pair<int, int> cur{i, i + a[i]};
        int need = max(a[i] - k, 0), tot = 0;
        while (!ones.empty() && cur.second >= ones.back().first) {
            auto [l, r] = ones.back();
            ones.pop_back();
            if (need >= l - cur.first) {
                tot += r - cur.first;
                need -= l - cur.first;
            } else {
                tot += need;
                need = 0;
            }
            cur.second += r - l;
            cur.first = r;
        }
        ans = max(ans, tot + need);
        cur.first = i;
        ones.push_back(cur);
    }
    cout << ans << '\n';
}

hello, ik im quite late but in question c can anyone pls explain where i went wrong? where i messed up?

352570105

this is my submission void solve() { ll n, k, q; cin >> n >> k >> q; vector a(n, 0); vector<pair<ll, ll>> m; while (q--) { ll c, l, r; cin >> c >> l >> r; l--, r--; if (c == 1) { for (ll i = l; i <= r; i++) { if (a[i] == 0 || a[i] == 2) { a[i]++; } } } else { for (ll i = l; i <= r; i++) { if (a[i] == 0 || a[i] == 1) { a[i] += 2; } } m.pb({l, r}); } } vector ans(n, -1); for (ll i = 0; i < n; i++) { if (a[i] == 3) { ans[i] = 1000000000; } else if (a[i] == 1) { ans[i] = k; } else if (a[i] == 0) { ans[i] = 1000000000; } } sort(all(m)); f(i, m) { vector temp(ans.begin() + i.ff, ans.begin() + i.ss + 1); ll mi = mex(temp); if (mi == k) { mi = 1000000000; } for (ll j = i.ff; j <= i.ss; j++) { if (ans[j] == -1) { ans[j] = mi; temp[j — i.ff] = mi; mi = mex(temp); }

if (mi==k)           
        {
            mi = 1000000000;
        }
    }
}
f(i, ans) cout << i << " ";
cout << endl;

}

my basic logic was sooo 4 cases on each index case 1: c=1 then ill put a[i]= k. basically it should be the min soo who cares if there are multiple k as long as there is nothing <k. case 2: i has no constraint, neither c=1 nor c=2 soo there i put a[i]=1e9. thats massive enough to not cause any issue anywhere neither with min nor with mex. case3: c=1&&c=2 that means i have to satisfy both mex and min, soo a[i]!=k. a[i]>=k cuz of this >=k then that means it can't help making mex =k soo i just put it a[i]=1e9. same logic with case 2. case 4: ill take mex and put the next 'non locked' index as that mex, now mex will increase by something based on what all stuff is present in the array. recalc mex and repeat. if mex=k i can't put k there soo again logic of case 2 put 1e9. (locked ones are case 1,2,3) non locked are the remaining ones btw

can anyone pls help me?

A good conpetition! they are interesting

a better code for the D problem since i find the editorial code difficult to understand,353609790

but the hints were good enough to get me through the idea

Solution of Adjusting Drones (Problem E)- Would anyone please tell which testcase it's giving error on ? 353740562

I don't think you can see the code

why is almost nobody talking about problem D solution using ternary search

In D, although it can be guessed, but editorial introduces out of the sudden concepts like red and blue element, which the task didn't even mention. Also, to complement editorial, I think the crucial insight is that for fixed x (p in description), the score can be written as linear function f(x)=ax+b

$$$(|3|-|2|)x+(\sum_{\in{2}}{a_i} - \sum_{\in{3}}a_i)$$$, where 2 is a set of elements assigned to 2nd option and 3 defined analogously. It becomes clear, why it's enough to check x=l and x=r (cases when a is positive and negative). It's not hard to notice that for fixed |2| and |3| counts, it's optimal to choose largest elements to 2 set and smallest to 3 set (constant part, the difference between max and min).

In 2nd Sketch of proof, it's not proven/mentioned that R B is always better than B R. In 3rd Sketch of proof, you might model 3 situations where the p is in middle, to the right of y and to the left of x. In all cases, the difference is y-x (positive).

One thing that I can't understand is that the provided solution roughly takes n/2 lowest elements as R (unless it's always guaranteed to be lower than l, similar for B) and n/2 highest as B (tries to make both sides as equal as possible). Why does this construction work? And the middle element is left as white in case of odd array length.

problem C : https://codeforces.me/contest/2157/submission/359948184 How to become better in implementation? help me with guidlines. I was tring to solve the problem and my idea of the solution actually the same which i have verified after getting wrong answer in test case 2 several times and ends up reading tutorials. In the tutorial solution what he did i actually wanted to do that but i tried to to it different implementation. I was quite surpriced to see the editorial solutions how simply he did it. can you have a look on my previous submission what did i do wrong?

my O(n) solution for E (it's possible to get rid of the deque and the pair but I'm just lazy):

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

#define pb push_back
#define ll long long
#define endl '\n'

void solve(){
    int n, k;
    cin >> n >> k;

    vector<int> arr(n), freq(3 * n + 1, 0);
    for(int i = 0; i < n; i++){
        cin >> arr[i];
        freq[arr[i]]++;
    }
    
    int ans = 0, last = 0;
    deque<pair<int, int>> dq;
    function <void (int)> func = [&](int x){
        if(x > k){
            dq.push_front({x - 1, last * dq.empty()});
        }else if(dq.size()){
            dq[0].first += x - 1;
        }
    };

    for(int i = 1; i <= 3 * n; i++){
        if(freq[i] == 0 && dq.size()){
            if(dq.size() == 1)
                last = dq[0].second;
            freq[i] = dq[0].first;
            dq.pop_front();
        }

        func(freq[i]);
        if(dq.size())
            ans = max(ans, ++dq.back().second);
        else
            last = 0;
    }

    cout << ans << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    cin >> t;

    while(t--)
        solve();

    return 0;
}

A $$$O(n)$$$ solution to E

my O(n) solution for problem E. Adjusting Drones

void sol(){
  cin >> n >> k;
  for(int i = 1; i <= 2 * n + 1; i ++) cnt[i] = 0;
  for(int i = 1; i <= n; i ++) cin >> a[i], cnt[a[i]] ++;
  
  int total = 0;
  int ans = 0;
 
  for(int i = 1; i <= 2 * n; i ++){
    if(cnt[i] > k){
      total ++;
      cnt[i + 1] += cnt[i] - 1;
    }else{
        ans = max(ans, total);
        total = 0;
    }
  } 
  cout << max(ans, total + max(0, cnt[2 * n + 1] - k)) << '\n';
}