shishyando's blog

By shishyando, 7 weeks ago, In English

We know about FST and we are really, really sorry about it. Even though we still hope that you liked the problems.

A: Digit Minimization
B: Z mod X = C
C: Column Swapping
D: Traps
E: MEX vs DIFF
F: Diverse Segments
G: Euclid Guess
H: Hard Cut
 
 
 
 
  • Vote: I like it
  • -198
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +229 Vote: I do not like it

Weak pretest C...

»
7 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +167 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    pretest for D are also very good!!!!!! the best round of this year

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you prove your solution?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it -54 Vote: I do not like it

      i don't have time to prove my solutions on the contest. it's better to get a WA than lose a lot of time

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        then it's your problem that your solition failed system testing, not authors. if we did have very very strong pretests, some problems could be solved by just guessing the solution which is bad for me

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
          Rev. 2   Vote: I like it +10 Vote: I do not like it

          well, if someone tries to guess the solutions, he gets a huge penalty. Also it's possible to guess the answer only in div2 A, so the pretest for other tasks should be strong

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it +24 Vote: I do not like it

            ok, your opinion is not bad too, but that's codeforces and if your solution passed pretests, it doesn't mean that it will past system testing

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I proved my solution and it worked as charm if elements were distinct, I didn't consider when elements are equal.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -33 Vote: I do not like it

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

»
7 weeks ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +21 Vote: I do not like it

    It's guaranteed that the sum of n*m over all test cases does not exceed 2*(10^5).

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It does say that the sum of $$$n \times m$$$ is less or equal to $$$2\times 10^5$$$

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the statement it says that $$$n \cdot m \leq 2 \text{e}5$$$. So the total number of matrix entries is at most $$$200 000$$$.

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

    It is given that sum of n*m will be less than 2*10^5.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The size of the matrix is not 10^10 it is 10^5 , you can read the constraints again, so the entire matrix has 10^5 elements in total . so ya this number is doable . Happens.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    This test case will give -1 for all(mostly) those who got WA

    • 1 3
    • 2 2 1
  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    if you found anywhere that previous element in column is greater than next one then you have to check totally left and totally right untill you didn't get their exact position and then store them like this 1 4 3 3 3 3 or this 1 4 4 4 4 3 .

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, you are right. In the contest, I just did totally right for the minimum element and forgot about the totally left for the maximum element; that's why I got WA on 12.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We can easily sort the seq and check which element is not in the sorted sequence. it won't miss anything but time complexity would be O(nlogn).

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can somebody mention test case 12 of problem C?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add tutorials for other problems too!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

ابلعععععع downvotes

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really fast editorial thanks!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

very good c pretest, very challenging pretest, LOVE IT

»
7 weeks ago, # |
  Vote: I like it +57 Vote: I do not like 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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    damn, i had that idea, but i thought that I should only do that when a_i — (n — i) > 0

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    used the same approach

»
7 weeks ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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 :((

»
7 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

Problem G's tests were not very good: 157719356

»
7 weeks ago, # |
  Vote: I like it +52 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

$$$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)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    swap (3, 2) -> 21 -> swap(2, 1) -> 1

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I though that we can swap only consecutive digits

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Logic for $$$n > 3$$$: move mimimum digit to $$$2nd$$$ position and don't touch until last Alice step. Then swap with $$$1st$$$ and done.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is there any idea for solving D using binary search ?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, it could make sense if not all of $$$k$$$ jumps could be used for some reason, but here it is proved that we should use all of them, so solution is greedy.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is anybody getting WA on test case 20 in C? Specifically 71st case

»
7 weeks ago, # |
Rev. 3   Vote: I like it -59 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's 2022 for 5 months bro, get out of your room.

»
7 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

The worst pretests EVER.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Some hacks in problem E returning unexpected verdict?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to fix WA5 in F? My solution

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 .

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too. Someone, please explain D.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's simple. You're at the ith index and you decide to choose to jump implying you'll take a extra penalty for all following traps worth 1. So in total extra damage = 1 x (n-i) also the damage avoided is ai. So ideally choose max ai-(n-i) values

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice Explanation. Better than solution itself. Language of solution was not that much comprensive.

»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    idk but unfortunately it's bad to use conditional like this

    else if(ind.size() > 2){ cout<<-1<<endl; return; } ( u already check in !is_sorted ) or swap in this task. I had the same problem

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When you return if m == 1, you do not read some a values, and next iteration of solver reads them instead of new n and m.

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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).

»
7 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can find the final MEX without using binary search. Just try to fill in the holes starting from 0 and stop when the number of holes gets higher than k. (Submission)

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, Have you read the editorial of task $$$E$$$.

    If yes? In the author's implementation, in the current iteration wherein we are assuming the $$$mex$$$ to be $$$i$$$, where do we ensure that $$$i$$$ is not present in the set $$$s2$$$? I mean, where do we ensure that $$$i$$$ is surely getting picked up and replaced with some other non-negative integer. If $$$i$$$ is not removed, then the $$$mex$$$ is definitely not $$$i$$$, won't it affect the final $$$ans$$$?

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      For first, i write this before editorial, for second, you can no tnihg in this solution and implementation it turns out to be very simple without places where you can make a mistake)

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I guess we cannot ensure i is not in s2. But this will not affect the answer: if mex is something larger, then currently we over-estimated the cost and later when we enumerate to the actual value of mex we will get the corresponding true cost.

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Weak pretest in B -_-

»
7 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    +1

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in problem D, test 77 (which caused many FSTs) was not in main tests, but it was added because someone hacked a contestant with it
    It's sad that they didn't even consider that case in main tests

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

In Editorial for problem A maximum is written instead of minimum

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Good problems but weak pretests. Oh well...

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody suggest some test case for mine problem C submission.It,s showing WA on test 21.

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

too much weak pretest for problem C ;)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

make the pretest strong. On today`s c question I got the pretest passed and then on system checking it gets failed. At least add one corner pretest to pass in system checking so that the solution will also pass in system checking.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
7 weeks ago, # |
Rev. 3   Vote: I like it +38 Vote: I do not like it

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

Problem E
Problem G

E Code

G Code

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

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

    For E: "and we do not care about any element >= m." Don't we also need to make sure that m should not be present for mex to be m? edit: is the reason that we can ignore this, the fact that, let's say when we fix mex = m, the actual mex was m+5, then we will get a strictly better answer when we fix the actual mex to be m+5?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
7 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lost here. Can you please share your understanding possibly with an example explanation ?

»
7 weeks ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

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:

My Implementation
  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    isn't this possible that for some trap we might get a (save on damage) negative and then we should simply not jump that trap right so , why always do k jumps

    jumping on a trap with negative (damage save) would be increasing damage.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Have you read the intended solution? Why wouldn't it be solvable?

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

      I mean that I wonder if it's solvable when $$$a<b<c \le 10^{18}$$$,bacause we have a limit of $$$x,y,z \le 10^{18}$$$.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        My Solution for B: long y=b; long p=c+b-1/b; long x=p*y+a; long z=c;

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Yes, it is. Try this, $$$x=a+b+c, y=b+c, z = c$$$

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nope, it is not. X must be greater than C and also fit in condition <= 10^18. It would not work for C=10^18

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I developed a way to solve the task when $$$a<b<c\le10^{18}$$$ and $$$x,y,z \le 2 \times 10^{18}$$$.

        And I'm curious if we can make the constraints a little smaller.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This round has some great problems like F but the pretest for C can be stronger next time.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

C examples are so poor

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried something different for problem B. I took y = 'b', and x = first multiple of 'b' strictly greater than 'c' and z = x+c. It had passed the pretests but failed the system testing because of the tle in my implementation.It has passed now.

https://codeforces.com/contest/1684/submission/157761850

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    x = first multiple of 'b' strictly greater than 'c' + a;

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please give simple example in which my code is failing in problem c. my submission id: 157723953

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

H can be solved with dfs.

157757076

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello all, I've tried problem D using priority_queue and that gave me WA, while the same logic gets accepted if I use set, can you please tell me what's wrong with priority_queue.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain for problem A , how can we get the middle digit when n = 3?...In particular , how can we get 1 from 312?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    312 1st operation — 213 So left number = 21 2nd operation — 12 So left number = 1

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Not a very good way to give an editorial!

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What's the problem with editorial?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I preferred the editorials better when there were hints given you know, those are great during up solving a contest. well everyone has their own taste so.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

Code
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    better than the editorial solution....thanks

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried to understand official editorial for 2 days. Yours I understood instantly, thank you sir.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same doubt

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Notice that first value to remove can never be negative(you can always remove last element in A without penalty), also notice that removing ANY element from A(and related value from B) is increasing left values in B by 1(values from left in A do not add extra penalty 1 for already removed element from right, values from right in A increase their value by 1 from already removed element from left)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Its always optimal to use all the k jumps. Reason for this is clearly mentioned in editorial:
    it is always better to use all k jumps. If we jumped over less than k traps then we can jump over the last trap and the total damage will be less
    Try reading it properly.

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

nice editorial explanation

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Never seen so many downvotes in an editorial before :')

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Getting WA on testcase 19 for Problem C: https://codeforces.com/contest/1684/submission/157778479

Could anyone help me? why is this getting failed?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

pretest<<<problem :(level)

»
7 weeks ago, # |
Rev. 2   Vote: I like it -42 Vote: I do not like it

THIS CODE GIVING WA IN TEST CASE 2. pls help```` ~~~~~

include

include

include

using namespace std;

define fo(ini,n) for(int i=ini; i<n; i++)

define ll long long

void solve(); int main(){ int t;cin>>t; while(t--){ solve(); } return 0; } void solve(){ int m,n; cin>>n>>m; vector<vector> arr(n, vector(m)); fo(0,n){ for (int j = 0; j < m; j++) { cin>>arr[i][j]; } } int diff=0,a=0; vector r(m); r=arr[0]; int f=-1,s=-1; sort(r.begin(),r.begin()+m); for (int j = 0; j < m; j++) { if(arr[0][j]!=r[j]){ diff++; if(diff>2){ cout<<-1<<endl;return; } if(f!=-1)s=j; if(s==-1){ f=j; } } } if (diff) { fo(0,n){ swap(arr[i][f],arr[i][s]); } } fo(0,n){ for (int j = 0; j < m-1; j++) { if(arr[i][j]>arr[i][j+1]){ cout<<-1<<endl; return; } } } if(diff==0)cout<<1<<" "<<1<<endl; else cout<<1+f<<" "<<1+s<<endl; } ~~~~~

»
7 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I want to post my code here as it is giving wa but as i paste it in the comment section all the indendation goes trash.How to post it pls tell

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain the sol of d problem??

»
7 weeks ago, # |
Rev. 2   Vote: I like it -41 Vote: I do not like it

Solution of D with brief explanation -

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;
 
void init_code(){
    #ifndef ONLINE_JUDGE
    freopen("ip.txt", "r", stdin);
    freopen("op.txt", "w", stdout);
    #endif 
}

int main () {
    init_code();
    /*
        1. jump -> -a[i]+n-i-1 damage added to total without jump -> n-(a[i]+i+1)

        But for first jump k-1 is added additionally (as after first jump k-1 jumps will be made for which +1 bonus for first jump will not be counted, but in 1. we have counted those bonus damage as well)

        Similarly for second jump it will be k-2
        for 3rd k-3 and so on

        so total 0+1+2+....k-1 = (k-1)*k/2 is extra calculated.

        so total ans has one variable -> a[i]+i ... we have to maximize this to minimize total damage.
    */

    int t; cin >> t;
    while(t--) {
        ll n, k; cin >> n >> k;
        vector<int> a(n);
        ll ans = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            ans += a[i];
            a[i] += (i+1);
        }

        sort (a.begin(), a.end());
        reverse (a.begin(), a.end());

        for (int i = 0; i < k; i++) {
            ans += n;
            ans -= a[i];
        }

        ans -= (k*(k-1))/2;

        cout << ans << endl;
    }
}
»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I passed B in 1.5 hours, hooray

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in A problem if a testcase like 213 what will be the output? first i swap 2 and 1 and that it becomes 123 3 removed 12 second i swap 2 and 1 and that it becomes 21 1 removed 2 then how the 2 nd condition in editorial will work?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is meant by "FST"?

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hint: diff — mex = count of unique numbers after mex

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      is it like this: diff — MEX = number of uniques greater or equals MEX. so, maximizing MEX minimizes that quantity.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you change a number to increase the MEX it will either won't change the answer or increase it, but never decrease it. So, maximing the MEX is a greedy choice

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Somebody please tell the time complxity of C?

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like 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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my C got WA on test 13: 157808169

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

very Good question 'A' and 'B' and very weak pretest 'C'

»
7 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you think about this approach during the contest, how to realize that this approach is wrong when only sum=5?It is too difficult for me.

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

      I upsolved the problem after the editorial. Also I did not know about the $$$K=5$$$ corner case: 111101 -> 11-11-01 is 7 with my construction.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

D is very difficult for me. are there any other problems like this ? how to get the idea for this?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it +19 Vote: I do not like it
    $$$ x \bmod y \equiv a $$$
    $$$ y \bmod z \equiv b $$$
    $$$ z \bmod x \equiv c $$$

    Let's try to reduce our possible solutions, by assuming that $$$x > z$$$, which leads us to $$$z = c$$$ using the third expression. You could try and play with $$$x < z$$$, but it wouldn't help much. Also, $$$z = c$$$ only works because $$$b < c$$$, as $$$z$$$ needs to be greater than $$$b$$$ on the second expression.

    Assuming that $$$z = c$$$, we are left with only two expressions:

    $$$ x \bmod y \equiv a $$$
    $$$ y \bmod c \equiv b $$$

    Using equivalent expressions:

    $$$ x = a + k_1 y $$$
    $$$ y = b + k_2 c $$$

    Applying the second expression on the first:

    $$$ x = a + k_1(b + k_2 c) $$$
    $$$ x = a + k_1 b + k_1 k_2 c $$$

    Now we need to find $$$k_1$$$ and $$$k_2$$$ that satisfies our initial assumption $$$x > z$$$, the simplest and most direct guess, which also leads to the editorial's solution: $$$k_1 = k_2 = 1$$$

    $$$ x = a + b + c $$$
    $$$ y = b + c $$$
    $$$ z = c $$$

    Also, this only works because $$$a < b$$$, as $$$b+c$$$ needs to be greater than $$$a$$$ in the first expression.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there any video solutions in English or Hindi?

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

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).

»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Does anyone know WHY I got so many downvotes? I have seen similar insane and meaningless downvotes elsewhere on Codeforces so I already know this crazy atmosphere. But this is wrong. Stop doing your meaningless downvotes and in particular, downvoting my comments doesn’t increase your rating.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

nice ZXC like for doters

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Damn! The pretests for B were weak.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes , they are very...the solution that he gave is also not valid for some of the some inputs that I can give

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Weak pretest for B

»
5 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Hello,

On the MEX vs DIFF problem. Can someone explain me why the output of the following input is 2 instead of 3, please. Test: #24 says it is 2.

1
10 4
9 9 5 5 8 8 9 9 8 9

-------------------
5 5 8 8 8 9 9 9 9 9
5 5 8 8 8 9 3 2 1 0

DIFF = 7
MEX = 4
DIFF - MEX = 3
»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Ugly implementation problems