When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

shishyando's blog

By shishyando, 22 months ago, translation, In English

Hi, Codeforces!

We are glad to invite you to Codeforces Round 792 (Div. 1 + Div. 2) which will take place on May/19/2022 17:35 (Moscow time). You will have 2 hours to solve 8 problems. The round will be rated for participants of both divisions.

I would like to thank those who made this round possible:

We would also like to thank NEAR for supporting the round. This company is founded by former competitor AlexSkidanov. NEAR is built by many prominent competitive programmers, including twice ICPC champion eatmore and GCJ and TCO winner Egor.

  • The participants who end up in the first 255 positions will receive prizes in NEAR coins. The participant on the first place will receive Ⓝ128, the next two participants will receive Ⓝ64, the next four participants will receive Ⓝ32, etc.

Score Distribution:

500750125015001750200025003250

We really hope that you like the problems! Good luck!

Editorial: link

  • Vote: I like it
  • -426
  • Vote: I do not like it

| Write comment?
»
22 months ago, # |
  Vote: I like it -57 Vote: I do not like it

As a tester, I really loved the round. One of my favorites in recent years, I'd vote at least two tasks for candidates to 'best of 2022'. Please participate!

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +202 Vote: I do not like it

    As per history of codeforces, whenever a tester says the round will be very good, the contest turns out to be bad.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +190 Vote: I do not like it

    fucking clickbait

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +382 Vote: I do not like it

    I'm sorry that these two tasks had to be replaced, I hope that we'll see them in the future.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +73 Vote: I do not like it

      Don't get me wrong, the problems were ok and interesting, but Kacper is always fascinated by so-so problems.

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        You know people don't have to like the same thing, right? You're around 3400, I'm around 2400 — we're not the same xD

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

          Yeah, ofc. I can be mistaken too, so I'm all ears, which problems deserve to be the best ones in 2022 and why?

          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it +86 Vote: I do not like it

            BTW. I tested quite a long time ago, and have learnt only recently about some issues like extremely weak pretests in C or short contest duration. I wouldn't support any of these decisions...

            In my opinion, D is an exceptionally good easy problem that has everything: nice, natural and simple statement which almost makes you wonder why is this not a well-known task. The solution was far from obvious to me, yet very simple and elegant. Although I guess perception changes if someone is as high rated as you, Mateusz. Most people wouldn't nominate easy problems to 'best of ...' because 'it is all obvious anyway'. But overall I don't remember any task of similar difficulty or easier having a 'wow-factor' for me in 2022. Simple and good algorithm problems are so rare nowadays...

            My other favourite task was G. I just loved solving this problem, as I was unravelling new layers of inference-based observations without doing bullshit guessing like "oh I can't prove this but it has to work this way, otherwise unsolvable". Plus, of course, somewhat natural statement about algorithms and reduction to something standard in the end. You know, I like when the task is not just about some formulas...

            I tried to give some justification. Of course you may not agree with it. Oh, and also, it's mid-May so it's comparatively easier to be best in 2022 :)

            I hope you've at least somewhat enjoyed the round despite my tiny bit of clickbait

            • »
              »
              »
              »
              »
              »
              »
              22 months ago, # ^ |
                Vote: I like it +14 Vote: I do not like it

              But I think the solution for problem D is very obvious if you are familiar with the thought of splitting answer into each position's contribution.

              • »
                »
                »
                »
                »
                »
                »
                »
                22 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                xyf007 if you know some similar problem to problem D ,please send me links for this type of problem

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

          Then I'll give my opinion as someone much closer to 2400 than 3400: among A-G, I liked D but it's not like super amazing. In CEF, I mostly put effort into not messing up my implementation since I immediately knew roughly what I needed.

          G is a combo of avoiding mistakes in reading, reducing GCD to the simplest possible form (the construction) and avoiding mistakes in typing since the construction says to find matching. I suppose the construction part's nice, at least it doesn't feel like divine revelation like most constructions, but I'm just not a huge fan of construction problems in general.

          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            G is the type of problem I hate the most. It teases your appetite by giving a problem which in general is NP-complete but you're told it can be solved due to some special property of the sets involved, but then it turns out thats it's the dullest property possible. Moreover if you look at those gcd sequences they feel soooo random the property in question just has to be some nonsense like

            Spoiler
            • »
              »
              »
              »
              »
              »
              »
              22 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              what is the general NP-complete version of G? (the only thing i can think of is removing the $$$\leq m$$$ constraint on the output, but that's certainly not NP-complete.)

              • »
                »
                »
                »
                »
                »
                »
                »
                22 months ago, # ^ |
                  Vote: I like it -8 Vote: I do not like it

                Arbitrary sequences given in yhe input rather than those generated by Euclid algorithm

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +273 Vote: I do not like it

    Maybe one task is best of 2011.

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

    This comment didn't age well.

»
22 months ago, # |
Rev. 4   Vote: I like it +211 Vote: I do not like it

I think having 2 hours and 15 minutes in a 8-problem contest is better.

»
22 months ago, # |
  Vote: I like it -14 Vote: I do not like it

I hope the contest is good

»
22 months ago, # |
  Vote: I like it +246 Vote: I do not like it

As a tester, I missed the final rated round of my teenage.

»
22 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I don't think 2 hours is really enough to solve 8 problems.Maybe 2 and a quarter or two and a half is better?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Don't judge without seeing the problems. Coordinators,testers,setters know the problems and according to that they would have set the duration. So probably 2 hours would be appropriate.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +107 Vote: I do not like it

    It's funny that such a things are proposed by a participants who anyway will not solve all of them :)

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Thanks for being considerate of the very small fraction of the LGMs who has the ability to AK the round, but may get into time trouble.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +139 Vote: I do not like it

      Well, AKing and LGMs are one thing but even for me 8 problems in 2 hours usually means a bad contest experience. Yeah, I won't solve them all but the experience still generally looks like "implement, implement, implement, implement, implement, contest ends" rather than "implement, think, implement, think, implement" in a round with less problems.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    don't worry for tourist.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agreed

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester, I want to say participate in this round!

»
22 months ago, # |
  Vote: I like it +47 Vote: I do not like it

Earlier there was a separate Div1 and Div2 round, but now it's a combined round. What was the reason?

»
22 months ago, # |
  Vote: I like it +61 Vote: I do not like it

As a tester, I'm a bit jealous that you all get to compete for prizes lol

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +66 Vote: I do not like it

    Previously you got double happiness of Grandmaster and 69 at once so it got balanced.

»
22 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Why is it combined?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it -80 Vote: I do not like it

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +76 Vote: I do not like it

    I think because it has prize and div 2 users also have chance to win the prize

»
22 months ago, # |
  Vote: I like it +44 Vote: I do not like it

As a tester, I get to mention _Vanilla_ for no reason.

»
22 months ago, # |
  Vote: I like it +87 Vote: I do not like it

I have also registered to round with id 1683 (that is, round #792 div 1), while it was visible. Can't wait to see where I will get redirected when the contest starts.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +66 Vote: I do not like it

    If anyone interested, it didn't even offer me to proceed to the contest page

»
22 months ago, # |
  Vote: I like it +27 Vote: I do not like it

NEAR coins in this round worth a lot less than NEAR coins in that previous round. :(

»
22 months ago, # |
  Vote: I like it +10 Vote: I do not like it

looking forward strong pretest !

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!

»
22 months ago, # |
  Vote: I like it -7 Vote: I do not like it

You will have 2 hours to solve 8 problems.

Gonna have to dance with pen now

»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I really love the coins distribution.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to register now

»
22 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Hopefully, I pass system test for all questions for which my pretests are passed. Last two times it didn't :(

»
22 months ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

Weak pretests for C I guess. My $$$O(N^3)$$$ passed lol.

»
22 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Problem H was here. Unfortunately, I wasted most of my time on the contest on H because the solutions posted there are wrong.

»
22 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

tourist gets back to rank 1 through 1 hack!

»
22 months ago, # |
  Vote: I like it +183 Vote: I do not like it
Trying to hack B
»
22 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Tougher B: Link

»
22 months ago, # |
  Vote: I like it +17 Vote: I do not like it

greedy forces!

»
22 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Most of the problems were nice, I liked the contest as a whole. Though unfortunately F just felt like tedious implementation (30+ mins) with not much thinking involved.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

some one pls tell that how to solve C :*

  • »
    »
    22 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    find any wrong positions of any two elements and replace their columns then check your solution is correct or not. wrong positions means that an array element such that it doesn't exist in allowed position in a sorted array .

    for example : in this array [1,2,3,3,4], the allowed positions for 3 is 3 or 4 only and for 2 is 2 only .

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What about [4 4 3] ?

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

        We should always pick the two extreme ones only(If there exist any). In this case index [1, 3].

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

          Or just Compare them with the sorted array and check which are not in position .

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Find the first index i such that a[i] > a[i+1]. Now, all elements at index less than equal to i will be sorted, so you can't swap a[i+1] with some a[j], j < i. Also a[i] can't be swapped with a[j], j < i. So you can only swap a[i] with some a[j], j > i. So find j such that a[j] <= a[i+1] and (j+1 == n || a[j+1] >= a[i]). Swap columns i and j

»
22 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Hmm, where did I see that plot twist happen before?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me whats wrong in my D solution here

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

    Consider this test

    1
    3 1
    2 1 1
    

    your solution says that the answer is 4, but you can achieve a score of 3 by jumping over the third trap.

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

      OMG, What are the odds that my tool (which uses a random seed) generated the same testcase Ticket 7275 as you (and we replied within seconds of each other xD).

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Do you yourself create test cases by stress testing after every contest on your website or is it created automatically?

        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          It's semi automatic. (There's some definitely some code involved, but I've created library, utility functions and macros that help me to create generators (and reuse existing ones) in an efficient manner.

          The customization part is automatic though.

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

    Failing testcase: Ticket 7275

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing contest, I love it!

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    I take my words back. Very weak pretests, especially for task C

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

I think you should use Bold words to tell us following operation exactly once in problem C, It wasted me 1h!

»
22 months ago, # |
  Vote: I like it +12 Vote: I do not like it

C was dirty case-work. and the mex=0 case of E(WA pretest 6) should have been in the samples.

However, D and F were cool.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    how was C casework?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It took me forever to figure out WA pretest 6 lol.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    On the topic of samples, the samples of D are so weak that if you mistakenly sort by $$$a_i - i$$$ (or even just $$$a_i$$$) instead of $$$a_i + i$$$ you will still pass the samples.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      Why exactly is that bad? If someone was guessing the current samples would make it harder to guess.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For F I have the same opinion with you, But does the person who didn't put case n = 1 and m = 1 in this problem have the permission to say this thing?

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I dont think they are comparable. that would be like that problem A didnt have a 2-digit sample lol.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    My solution to C require no casework (though I don't know if I will FST)

    Sort each row and check if there are at most 2 columns that differ. And if there are such 2 columns we try swapping them.

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

      I did the same. Find the leftmost and the rightmost columns that doesn't match and swap them. Not certainly sure how to prove the correctness. Update: My solution FST'd

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dirty case-work, AND the pretests were among the weakest in recent history. In a problem with multiple test cases per input, so there is no excuse for this. Disgusting.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    what dirty case work? just sort the columns lexicographically and find the number of non-equal columns what kind of case work is that?

»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Is D a DP solution?? if yes then how do i optimise it from O(n^2) complexity

»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Made a clutch solution on E at 1:59:46 and it passed pretests. :)

»
22 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I feel like F was slightly easier than D,E. At least D required an idea, F was just juggling claims about segments.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    For me both D and E were instant, F required some thinking. Should have thought a bit more though, almost TLEd in system tests, with 1949ms / 2000ms >_>

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Seems like you overcomplicated it. Check my solution, it just looks at all pairs of indices with the same value (efficiently, not bruteforce) and gets the best left endpoint for each right endpoint from there.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

spent too much time on different DP strategies for D but then realized it can be done by greedy

»
22 months ago, # |
  Vote: I like it -30 Vote: I do not like it

B is not a programming problem.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Based on the previous comments of yours, I feel like ranting about math problems in a contest is a recurring theme of yours lol.

    • »
      »
      »
      22 months ago, # ^ |
      Rev. 3   Vote: I like it +6 Vote: I do not like it

      That's actually my core competence ;)

      Edit: lol, I was fairly close

      Spoiler
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's how I felt, too :)

    After wasting 20+ minutes on paper trying to do math and coming up empty handed, I started trying to guess the formula. Guess I should do less math and more guessing from now on...

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

is E solvable without implicit treap? my idea was to find answer for mex(0), mex(1), ..., mex(n). each would take log^x (n) time. for each mex(i), you do the following:

  • if you have i currently in the array, decrease it's frequency by one, otherwise find the element with smallest frequency and change it to i

  • (update the change frequency in the implicit treap, erase the previous frequency and insert the new one, if it is > 0)

  • now you have k-i-1 operations left, you use them to decrease DIFF as much as possible. you decrease DIFF as much as possible by changing the numbers with smallest frequencies to the number with biggest frequency until you can. you don't have to actually change them, just find how many of the smallest frequencies sum up to <= k. that's doable with binary search in implicit treap with sum queries.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can do it with two segment trees, one for sum and one for count of distinct numbers.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    I binary search the largest possible MEX, then remove group of numbers more than MEX greedily.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thats sounds easier, didn't know you have to maximize mex

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +3 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

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have the same idea, but I found the largest MEX greedily.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please give a hint about D

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    Hint
  • »
    »
    22 months ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    First drop the first k traps and then start from k + 1 and check if there is a better drop than the worst drop from the previous k drops.

    I used a Heap for this.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, How to solve C? I understood the statement and I can't implement the solution. any help?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    find any wrong positions of any two elements and replace their columns then check your solution is correct or not. wrong positions means that an array element such that it doesn't exist in allowed position in a sorted array .

    for example : in this array [1,2,3,3,4], the allowed positions for 3 is 3 or 4 only and for 2 is 2 only .

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can refer to mine. 157703045 I just checked if there exists any such row where the (j+1)th element is smaller than the jth element, if it exists then I simply marked that row and and searched for two indices in that particular row where the numbers should be swapped. Then simply for that two indices i swapped the values for every row. After that simply traversed the matrix and checked whether the conditions are violated or not. If any such case found then print -1. else print those two indices.

  • »
    »
    22 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    First of all if $$$m = 1$$$, then the answer is $$$1$$$ $$$1$$$ otherwise :

    We consider a number in an array $$$bad$$$ if it is not in it's correct place in sorted form of the main array, So if the number of $$$bad$$$ numbers in any row was more than $$$2$$$ then the answer is $$$-1$$$, In other cases, Store the index of one of the rows that has exactly $$$2$$$ $$$bad$$$ numbers, then find the indices of two $$$bad$$$ numbers in that row, For example they're at indices $$$i$$$ and $$$j$$$, then swap all the pairs at indices $$$i$$$ and $$$j$$$ for each row or better to say is swap column's $$$i$$$ and $$$j$$$, Then after all if you found any row unsorted, the answer will be $$$-1$$$ otherwise the answer will be $$$i$$$ and $$$j$$$.
    157737517

»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve E?

»
22 months ago, # |
  Vote: I like it +43 Vote: I do not like it

I hope there won't be 700 systests in H which will disappear later like some time ago.

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

    26 were enough :P

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

      Yeah, during the contest my solution passed them twice (with different parameters), but after the contest it failed (I guess due to time-dependent seed).

»
22 months ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

FSTforces. Wait and see how many people will FST on C.(including me :( )

  • »
    »
    22 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Same here :(
    Found out WA test only after the contest end :(

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this was the best speed forces. what is happening there?

»
22 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Why is pretests for C so weak?!

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you know it as of now? AFAIK, system testing has not yet begun.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, I discovered an error in my program after I first passed these tests, and I fixed it, thinking it would be fine now and locked the problem, then I got myself hacked with another test...

    • »
      »
      »
      22 months ago, # ^ |
      Rev. 2   Vote: I like it +30 Vote: I do not like it

      Here's a test that I and probably some other ones will FST on:(

      1
      1 3
      2 1 1
      

      I thought we just need to try swapping columns with $$$a_{i,j}<a_{i,j-1}$$$.

      FST for me again!

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The answer should/can be "1 3"?

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

          Yes, codes that wiil FST on this case will output "-1".

          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I see, luckily I am still in :)

»
22 months ago, # |
  Vote: I like it +9 Vote: I do not like it

nice round hope not to turn on depression mode after system tests

»
22 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Question B appeared on codeforces not long ago

https://codeforces.com/gym/103415/problem/H

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

    But in this round there was a constrain , i.e a<b<c. Which makes the problem in this contest easier

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

nice problems...In D I sorted in non-increasing order as {value-(n-index),index} then took the first k pairs and set their indexes as the traps to be jumped over,I thought this would be optimal and it passed, but any proof why it's optimal??

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Consider the amount of damage you prevent by picking each trap. Say the first trap you pick is index $$$i$$$. You save $$$a_i - (n - i)$$$ damage because you no longer take $$$a_i$$$ damage from the $$$i$$$th trap, but all $$$n - i$$$ traps after index $$$i$$$ take bonus damage. After picking the first trap, ALL remaining values increase by $$$1$$$. Traps before index $$$i$$$ increase by $$$1$$$ because there is one less trap after it that takes bonus damage. Traps after index $$$i$$$ also increase by $$$1$$$ because you save the $$$+1$$$ bonus damage dealt by index $$$i$$$ by choosing that trap. So all values change by the same amount, and it is correct to still sort by $$$a_i - (n - i)$$$ for future decisions.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    There is an easy proof by changing the problem to an equivalent one.

    Note that we always jump exactly k times. Change the problem, such that we DO take the bonus damage when jumping over a trap (we still don't take the trap's base damage). Note that the answer to the changed problem is always $$$k (k - 1) / 2$$$ larger than the answer to the original, so subtract this from your answer to get an equivalent problem.

    But now, the damage we avoid by jumping over trap $$$i$$$ (zero-indexed) with damage $$$a[i]$$$ is exactly $$$a[i] - (n - 1 - i)$$$, as desired.

»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

FSTForces..

»
22 months ago, # |
  Vote: I like it +21 Vote: I do not like it

So many system test failure in C

»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Wow very strong pretests. Good bye codeforces shifting to Atcoder and Codechef

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

I only solved A, I hope next contest I will solve 3 problems.

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

    It works in O(c). It's obvious that it TLEs if a = 1 b = 2 c = 1e8 and 10000 testcases.

»
22 months ago, # |
  Vote: I like it +19 Vote: I do not like it

When the test-case setters confuse a Codeforces Div. (1 + 2) with a TopCoder SRM.

»
22 months ago, # |
  Vote: I like it +57 Vote: I do not like it

Thank's for this brilliant pretests

»
22 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Poor pretest hurts more than wa, thanks to problem setters for giving me a bad day

»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

The wonderful pretest made me go through the worse 520.

»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for the amazing pretests :(

»
22 months ago, # |
  Vote: I like it +4 Vote: I do not like it

What is there in D's Test Case 77?
FSTs in both C and D, hope the edge cases that I've apparently missed are outrageous enough...

  • »
    »
    22 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Test case #77 for D:

    1
    10 5
    1 1 1 1 1 1 1 1 1 1
    
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I also got WA 77. The mistake I made in my code is that k * (k-1) / 2 in line 64 should be i * (i-1) / 2. How did it passed the pretest??

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      My mistake was this simple single line condition that was unnecessary ig:
      if((*ptr).first >= 0)

»
22 months ago, # |
  Vote: I like it +15 Vote: I do not like it

f*** the pretests of C

»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Other than problem C, I liked this round a lot. Problems D, F and G were nice, and for an easy problem, B was very good.

»
22 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Finally algo tasks and systests, thank you!

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Weak pretests hurt :'(

»
22 months ago, # |
  Vote: I like it +4 Vote: I do not like it

PRETESTS SUCKS Especially for D, how can wrong code even pass systests? (If test case 77 wasn't added by the hack, many wrong code might be passed!)

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The problems were not bad, but the pretests were extremely weak. How did my D pass the pretest even though I mistook i * (i-1) / 2 for k * (k-1) / 2?

After getting -200 delta, now I have to go back to candidate master and participate Div.2-only rounds again.

»
22 months ago, # |
  Vote: I like it +41 Vote: I do not like it

As a tester, you all guys did shitty job

»
22 months ago, # |
Rev. 3   Vote: I like it +115 Vote: I do not like it

 pretest

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it
Meme
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody give me any stress test for E?

»
22 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Thank you for the contest.

»
22 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Despite the pretests for B and C, the system tests for problem G are also weak. Some greedy solutions without any type of matching algorithm can easily pass them. Some Accepted codes even wrote a case wrong(big + 2 * small > m instead of 2 * big + small > m). See 157733355, 157719356, 157726787.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    I feel the need to identify myself as one of the big + 2*small jokers because I just find it so incredibly funny that you can pass systests with such a mistake

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      I passed systests in 1684F - Diverse Segments with a completely wrong solution: 157733083

      (fun fact: I finished writing the code $$$1$$$ minute after the end of the round, I was mad because I missed a huge delta, and only now I've realized that I wouldn't have deserved the AC)

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There were 22 tests in problem C, and Mine had to fail on the last one :) lucky me

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1300 (before sys test) -> 900 (after sys test) lol

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

I'm thinking about why Codeforces divide test cases to pretests and system tests, and there might be two reasons.

  1. Using pretests instead of full tests during the contest can sometimes avoid the server being overwhelmed by too many judging tasks.

  2. If someone come up with corner cases which are not initially included in the system tests, those cases will be added to system tests and a rejudging is needed. But a rejudging is almost the same as pretests / system tests.

In the ideal case where the server is very powerful and the original system tests already cover all corner cases, I think we probably don't need pretests / system tests.

See also this discussion.

»
22 months ago, # |
Rev. 3   Vote: I like it -43 Vote: I do not like it

Cheaters copying each other code for C need to stfu and stop crying. Try to learn and get good, then you wouldn't cry about failing test.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    BASED

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

    This is racist and nitpicky at the same time. You cant really say that everyone who failed C copied code. There are reds who failed C. Also associating indians to cheaters or vice versa is not correct either.

»
22 months ago, # |
  Vote: I like it +19 Vote: I do not like it

At least the rating of this announcement behaves like crypto prices.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was it the following distribution of problems today?

Div2 A
Div2 B 
Div2 C / Div1 A
Div2 D / Div1 B
Div2 E / Div1 C
Div2 F / Div1 D
         Div1 E
         Div1 F

Or it’s slightly different?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1684/submission/157739291 can anyone help me in getting where i am going wrong

»
22 months ago, # |
  Vote: I like it +73 Vote: I do not like it

To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!

»
22 months ago, # |
  Vote: I like it -78 Vote: I do not like it

How did this () contest get NEAR's support?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well they don't get to look through the problems before sponsoring a round, they just decide to sponsor a round that's likely to have a lot of attention, and then sponsor it.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why so many downvotes?

»
22 months ago, # |
Rev. 4   Vote: I like it +39 Vote: I do not like it

Good contest , but f**king pretests !

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

weak pretests on C

»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Although I don't perform well in this contest, I appreciate the quality of the problems, especially the problem D. I didn't realize that the reduced scores of jump can firstly be ignored and finally be calculated by k*(k-1)/2 after all jumps. According to this property, the reduced cost of each jump in index i can be calculated by a[i]-(n-i-1). Then I can sort the reduced costs and simply use greedy strategy by choosing the first k large reduced costs to solve the problem D.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea why this solution is getting TLE?

The complexity (as I calculated) is O(m*n), where m*n<=2*10^5

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This happens beacuse in some case you don't input all the numbers for this testcase and then your programme input them in the next test case so all numeration of the input numbers breaks.

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

      Cheers, man! I was only calculating complexity and etc, never checked the logical part before.

»
22 months ago, # |
  Vote: I like it -9 Vote: I do not like it

good contest and good problems.

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

Do we need to sort the columns in C? I thought it could be done faster than O(m * nlog(n)) time. My O(m * n) solution was accepted. My idea behind it is as follows:

  • I check how many pairs of columns violate the rules of a good grid. If there are no such columns, we don't need to do anything. Swap any column with itself. If there are more than two such pairs of columns, the grid cannot be fixed with a single swap. Now we're left with non-trivial cases.
  • Else, if there are two such pairs of columns, I swap the larger column of the first pair with the smaller column of the second pair. For example, with one single row [1 5 3 4 2 6], the pairs of columns that violate the rule are the 2nd and 3rd ([5 3]) and the 4th and 5th ([4 2]) columns. Hence, I swap column 2 with 5, and the row becomes [1 2 3 4 5 6].
  • Else, if there is only one such pair of columns, I swap the larger column that comes first with the smaller column that comes last. As in, with one single row [1 2 2 1 3], I swap column 2 and 4 and the row becomes [1 1 2 2 3], and [1 2 1 1 3] becomes [1 1 1 2 3].
  • After those swaps, I check if the grid satisfies the conditions. If it still violates them, the grid must be unfixable.

Is my complexity analysis wrong? Can anyone hack my solution?

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

Please help ;(. I don’t know how to get my crypto.

P.s. My email is unavailable. Maybe I should restore my email?

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

    I bet you will get some instructions after removing of cheaters

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I get my near? I got place 128 but I didn't receive an email.

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

    Maybe you will receive an email after removing the cheaters.

»
22 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Where is the prize?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Regarding getting the prize, if I submitted public key from my old account, then my money for this round is gone? The bot does not seem to create new accounts even with new public keys.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone recommend where I can exchange this NEAR nonsense for USD or any real currency?

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

After sending the public key, I accidentally refreshed the web page and I lost my passphrase. What should I do?

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

great round bro enjoyed reading problems