Weak pretest C...

Good F though i didn't solve it in time:)

very good round! especially pretest for C! THANK YOU!!!!!!!!!!!!

Passed pretests for C, but failed in system test. Please make the pretests stronger

for C, how can we load so many elements into a matrix if the size of the matrix is 10 ^ 5 x 10 ^ 5 ??

I got WA on test 12 in C, and so many people also getting this, can anybody tell me why this happened? Thank You :)

Can somebody mention test case 12 of problem C?

Please add tutorials for other problems too!

downvote

very good c pretest, very challenging pretest, LOVE IT

I solved problem D without realising the fact that we should always use all $$$k$$$ jumps, here is my approach:

Let $$$b_i$$$ denote the reduction in the damage you can get by jumping over the $$$i$$$-th mine. Initially, $$$b_i = a_i - (n - i)$$$ as the $$$n - i$$$ mines after $$$i$$$ each gain an extra point of damage.

Now notice how the array $$$b$$$ changes after we jump over a mine, say at position $$$j$$$. For $$$i<j$$$, $$$b_i$$$ would increase by $$$1$$$ as there is one less mine affected by the additional damage. For $$$i>j$$$, $$$b_i$$$ would also increase by $$$1$$$ as the additional damage from jumping over $$$j$$$ can be skipped as well.

Therefore we can show that the relative ordering of values in $$$b$$$ never changes, and we can do a simple greedy, taking the maximum $$$b_i$$$ each step.

I set the condition for 3 incorrect positions in C, but there was WA 2 xd, I had to remove it and got OK/ 157699542 and 157709794 UPD i do not check other data in test :((

Problem G's tests were not very good: 157719356

Great round, why do you downvote??? I understand that this round has weak pretests, but problems weren't bad

$$$Concise$$$ tasks! The main thing was the idea, not the knowledge of a well-known complex algorithm.

P.S. I almost solved D using logic as in editorial, but also used a segment tree for.. who knows. Got WA. Removed segment tree — got AC :D (Always important to prove solution first)

Tell me please where I am wrong In A if we have a 3 digits number like 312, the answer should be 2, because there is no way that Alice can play, so that she gets 1. What is wrong with that logic?

is there any idea for solving D using binary search ?

Maybe some of the problems are one of the best in 2022 (as one of the testers said). But problem C is one of the worst this year (problem on its own + pretests). So sad pretests were bad for this round.

The worst pretests EVER.

Some hacks in problem E returning unexpected verdict?

How to fix WA5 in F? My solution

Still couldn't understand problem D . I got the part why we need to use all k jumps but why pickih the k maximal values of ai — (n — i) would work ? Can someone explain .

nice, great, awesome, incredible, unbelievable, insane, amazing, astounding, astonishing pretests for C.

Weak pretest C... Many top coders did mistakes in a hurry but at least that test case should be in the pretest. 1 FST can ruin a full contest.

Can somebody write the editorial on "How to understand this editorial !!"

In addition to weak pretests in C and D, it is also bad TESTS in G. Look at this submission. This is the most simple greedy solution, which should not pass the test, but it did.

This is my approach for problem D - Let's say you can jump only once. Then our main aim is to find the index jumping over which gives us minimum total damage. Consider two indices i, j such that i < j. If we see, either we jump at element at index i or index j, it will add same answer (n — j) to subarray [j+1, n]. So, main concern is subarray [i, j]. Now, if we remove i, then total damage for this subarray will be a[i+1] + a[i+2] ...... + a[j] + (j — i). If we remove j , then total damage for subarray [i, j] = a[i] + a[i+1] + ..... + a[j-1].

On subtracting first equation from second we get a[i] — a[j] — (j — i). So, if it's better to remove j in optimal solution then above written expression should be less than equal to 0 i.e. a[i] — a[j] — (j — i) <= 0 which implies a[i] + i <= a[j] + j. So, here we seen for two indices. Similarly can be proved for other indices as well. So, sort given elements according to a[i] + i and jump over maximum k elements sorted according to a[i] + i.

https://codeforces.net/contest/1684/submission/157737407 What is wrong with my submission?

Weak pretests in C? That might be happened sometimes. The biggest problem is, if someone did not hacked main test 77 in problem D, many wrong solutions might get AC (and unwarranting scores).

In E there is the following funny solution — note that it is always advantageous to make such a change in which the mex increases. So, to find out the final mex, you can simply do a binary search.

And if we know the final mex, then we must delete all the elements of the not less mex in order of increasing the number of occurrences in the array.

Weak pretest in B -_-

I think that pretest is made to not make a load of testing when the round is running... so the pretests must be so strong, so when someone get pretests passed, his probability to get accept should be 95% or above, because when I got WA on pretests I could modify my code and submit it again and got accepted, but after the round has finished and got WA or TLE in the tests after pretests I can't do anything in that time....

So the pretest should contains all tricky tests and corner tests and TLE tests.

Since there is no editorial for problem E could somebody give me a brief explanation of his idea please?

Contest was great, one of the most enjoyable for me. Weak pretests ≠ bad contest.

In Editorial for problem A maximum is written instead of minimum

Good problems but weak pretests. Oh well...

There is a person who is inexplicably similar to my code. I think it may be that someone in my room maliciously distributed my code. Unfortunately, I have no evidence

too much weak pretest for problem C ;)

wow very original problem H!!!!!

https://artofproblemsolving.com/community/c6h1472066p8547136

My solution ideas for E, G, since there is no tutorial for E and G, yet.

E Code

G Code

(Sorry for not including formal proofs and latex, i find it easier to understand and explain intuitions)

The solution for E is different from mine, I used binary search (once again XD)

I'm just counting with inspect element, but in the top 2000 competitors, I ended up with 559 FSTs, a failure rate of 28%. Compare that with the last Div. 1 + 2 round, where I got 91 FSTs, or 4.5%, or the one before that with 76 FSTs, or ~4%. That's pretty absurd.

Secondly, let's say that we immediately get n−i damage if we jump over i-th trap. This way the first trap that we jump over will cause k−1 damage more than it should (because of k−1 traps that we jump over next), the second will cause k−2 damage more, ..., the last one will cause 0 damage more. So the total damage only increases by k(k−1)2 which does not depend on the traps that we choose. That's why the traps that we have to jump over in this problem are the same.

Can someone please explain what the author is trying to say here. I don't get how we get k-1 more damage if we do 1st jump, shouldn't it be n-i-(k-1). and similarly for 2nd jump n-i2-(k-2) and so on.

Edit: Figured it out.

My take on D.

We have to make K jumps, suppose we make them at indices (i1 , i2 , i3 .... ik) [0-indexed].

1. First Jump will save us --> ( a[i1]-(n-i1-1)+(k-1) )dmg --> (a[i1] + i1 + constant1)
2. Second Jump will save us --> ( a[i2]-(n-i2-1)+(k-2) )dmg --> (a[i2] + i2 + constant2)
3. Kth Jump will save us --> ( a[ik]-(n-ik-1)+(0) )dmg --> (a[ik] + ik + constantk)

We see that the jumps will be more beneficial for us if we do them on traps which have higher a[i] + i value, as they give us better minimization of dmg. Thus the greedy approach :).

Edit:

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

#define ll long long int
#define mod 1000000007
// #define inf 0x3f3f3f3f
#define F first
#define S second
#define nl "\n"
#define PI 3.141592653589793
#define inf 1000000000000000000LL
#define pb push_back


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

    vector<ll> a(n) ;
    vector< pair<ll,ll> > b(n) ;
    for(int i=0 ; i<n ; i++){
        cin >> a[i] ;
        b[i] = {a[i]+i,i} ;
    }
    sort(b.rbegin(), b.rend()) ;

    for(int i=0 ; i<k ; i++)
        a[b[i].second] = -1 ;

    ll dmg = 0, bonus = 0 ;

    for(int i=0 ; i<n ; i++){
        if(a[i] != -1)
            dmg += a[i] + bonus ;
        else
            bonus++ ;
    }

    cout << dmg << nl ;
}


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    std::cout << std::fixed << std::setprecision(0);
    int testCases ;
    cin >> testCases ;
    while(testCases--){
        solve() ;
    }
    return 0 ;
}

In task B,I didn't read the statement correctly and took it as $$$ a < b < c \le 10^{18}$$$.

Is this task solvable then?

Anyone can explain F? I can’t get the idea from editorial. I tried to compute the shortest second occurrence of the same number for L and R, but not sure how to get minimum range.

I don't know a good place to say this or not but the 'You have to to do the following operation exactly once' should have been in bold letters in problem C.

H can be solved with dfs.

157757076

Can someone please help me understand why my solution for D is failing.

In D how is jumping over the first trap causing $$$k - 1 $$$ shouldn't it be $$$ n - 1 $$$? The first line of the second paragraph is literally that.

Not a very good way to give an editorial!

For D, I thought that it would be a good idea to check for all jumps $$$0 \leq x \leq k$$$ the minimal value of damage taken; since the problem said "no more than k jumps".

Let $$$sum = \sum_j a_j$$$ .

For 1 jump, the total damage taken is $$$sum + (n-k) - a_k$$$ where $$$k$$$ is the index that we jump over. $$$n-k$$$ is the bonus damage we will get from all further traps after $$$k$$$.

For 2 jumps, the total damage taken is $$$sum+(n-k_1-1)+(n-k_2)-(a_{k_1}+a_{k_2})$$$ where $$$k_i$$$ is the index of the $$$i^{th}$$$ jump. Note that $$$-1$$$ with $$$n-k_1$$$ is due to the fact that we jump over $$$k_2$$$ as well and so no bonus damage taken there. (I initially forgot this part and got a WA).

Generalising, for $$$x$$$ jumps, the total damage taken is $$$sum+x*n- \frac{x(x-1)}{2} - [{\sum^x_{i=1}} (a_{k_i} + k_i)]$$$. Here for calculating the $$$[{\sum^x_{i=1}} (a_{k_i} + k_i)]$$$ part, we sum $$$a_i + i$$$ for every $$$i$$$ and store it in a separate array (say b), and then pick the max $$$x$$$ elements from the array greedily. So on each increasing value of $$$x$$$, we subtract the $$$b[n-x]$$$ value and recalculate the damage the this stage.

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

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

    while(t--){
        long long int n,k;
        cin >> n >> k;

        vector<long long int> a(n,0);
        long long int sum = 0;
        for(long long int i = 0; i < n; i++){
            cin >> a[i];
            sum += a[i];
            a[i] += (i+1);
        }

        sort(a.begin(), a.end());
        long long int d = 0;
        long long int i = n-1, x = 1;
        long long int ans = sum;
        while(i >= 0 && x <= k){
            d += a[i];
            long long int temp =  sum + (x*n) - d - (x*(x-1))/2;
            ans = min(temp, ans);
            x++;
            i--;
        }
       cout << ans << endl;
    }
}

https://codeforces.net/contest/1684/submission/157771378 i have checked so many cases but still not able to find the mistake please can anyone help in finding the mistake in this or which case i am missing

In editorial of D, it is said that we must choose k maximal values. But if a[i] — (n-i) happens to be negative (but still coming in k maximal), why to take it. It will increase the cost rather than saving.

how to handle the case when we use less than k jumps in problem d; cause in editorial we always consider k jumps exactly

nice editorial explanation

Can anyone help me understand the solution for problem F in the editorial?

I have understood the entire logic, but facing some problems with the part where we have to calculate j. The editorial says the following:

This j could be found, for example, by binary search in cnt array. To check whether two elements are in the same segments it is possible to use a segment tree or a Fenwick tree. It is possible to store for each i such maximal rj that there is a given segment [lj,rj] and lj≤i.

I am not sure what is cnt array and how we are using segment trees here.

Minor nitpick: Editorial of A says: "Let $$$k$$$ be the length of $$$n$$$, [...] $$$k=1$$$ [...]" — but $$$n \geq 10$$$ according to the input constraints, so there is no case with $$$k=1$$$.

I passed B in 1.5 hours, hooray

What is meant by "FST"?

Does maximizing MEX (in problem E) always yield to the best answer? If it does, how to prove it?

I solved D in the contest with that idea but I still feel something not correct, "we immediately get n−i damage if we jump over i-th trap" but I think it only correct if that is the last jump.. Sr for my bad english, hope you still able to understand what i mean

https://codeforces.net/contest/1684/submission/157771378 i have checked so many cases but still not able to find the mistake please can anyone help in finding the mistake in this or which case i am missing

"This way she can always get the maximal digit of n in the end of the game." maximal -> minimal

Why my C got WA on test 13: 157808169

Problem : 1684C

shishyando i think there is weak test case. case:

1

2 6

10 20 50 30 60 100

1 1 1 1 1 1

Correct ans : 3 4

please check this solution 157739326, get -1 but accepted.

Please also check the almost same two codes( 157871675 , 157866257 ). One is accepted, another is Wrong answer there is no solution.

In problem H there is an easier solution for $$$K>5$$$.

Just cut the number into single digits, and from left to right concatenate a number with the next digit, if the total sum does not exceed the next power of 2. I don't have proof, but probably it is just some case analysis.

Is there a way to come up with solution for problems like problem B. I solved it with Guessing.

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

• A: Digit Minimization
• C: Column Swapping
• D: Traps
• E: MEX vs DIFF
• F: Diverse Segments

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

For E can anybody give a real proof for why maximizing MEX is always the best?

Ugly implementation problems

Wrote a blog for 1684D — Traps : https://blatherstrike.blogspot.com/2023/08/1684d-traps.html

I implemented a DP approach in D... but ended up getting WA on test 2. Can DP not solve D? and why?

here is my submission link -> https://codeforces.net/contest/1684/submission/248797672