shishyando's blog

By shishyando, 7 weeks 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

»
7 weeks 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!

  • »
    »
    7 weeks 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.

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

    fucking clickbait

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -37 Vote: I do not like it
    Testers be like
  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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.

      • »
        »
        »
        »
        7 weeks 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

        • »
          »
          »
          »
          »
          7 weeks 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?

          • »
            »
            »
            »
            »
            »
            7 weeks 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

            • »
              »
              »
              »
              »
              »
              »
              7 weeks 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 weeks 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

        • »
          »
          »
          »
          »
          7 weeks 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.

          • »
            »
            »
            »
            »
            »
            7 weeks 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
            • »
              »
              »
              »
              »
              »
              »
              7 weeks 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.)

              • »
                »
                »
                »
                »
                »
                »
                »
                7 weeks 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

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

    Maybe one task is best of 2011.

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

    This comment didn't age well.

»
7 weeks 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.

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

I hope the contest is good

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

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

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

.

»
7 weeks 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?

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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 :)

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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.

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

    don't worry for tourist.

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

    Agreed

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

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

»
7 weeks 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?

»
7 weeks 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

  • »
    »
    7 weeks 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.

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

Why is it combined?

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

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

»
7 weeks 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.

  • »
    »
    7 weeks 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

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

Hopeforces

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

TestersForces

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

i want to be stronger hhhh.

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

This is my First contest, very excited. All the best to me and you all.

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

It will be fun.

»
7 weeks 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. :(

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

looking forward strong pretest !

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

Good luck!

»
7 weeks 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

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

I really love the coins distribution.

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

okay! wishes all of you

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

I am not able to register now

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

»
7 weeks 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.

»
7 weeks 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.

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

tourist gets back to rank 1 through 1 hack!

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

Tougher B: Link

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

greedy forces!

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

https://codeforces.com/contest/1684/my what can possibly be wrong in my solution for A Help me please i spent 90 minutes on A problem

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

    I will assume that you are talking about this submission

    so i think that the problem is with the numbers between 1000 and 100 (inclusive),in this case you are comparing the first and the third digit which is not always right, for instance the solution to n = 315 is 1 because in the first operation you can swap 3 with 5 then swap 5 with 1.

»
7 weeks 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.

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

some one pls tell that how to solve C :*

  • »
    »
    7 weeks 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 .

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

      What about [4 4 3] ?

      • »
        »
        »
        »
        7 weeks 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].

        • »
          »
          »
          »
          »
          7 weeks 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 .

  • »
    »
    7 weeks 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

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

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

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

Can anyone tell me whats wrong in my D solution here

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

    anyone plz??

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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).

      • »
        »
        »
        »
        7 weeks 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?

        • »
          »
          »
          »
          »
          7 weeks 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.

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

      Got it thank u , will try another approach.

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

    Failing testcase: Ticket 7275

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

Amazing contest, I love it!

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

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

»
7 weeks 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!

»
7 weeks 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.

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

    how was C casework?

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

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

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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.

  • »
    »
    7 weeks 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?

    • »
      »
      »
      7 weeks 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.

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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?

»
7 weeks 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

»
7 weeks 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. :)

»
7 weeks 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.

  • »
    »
    7 weeks 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 >_>

    • »
      »
      »
      7 weeks 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.

»
7 weeks 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

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

B is not a programming problem.

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

    I solved A, C, and D and couldn't solve B

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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
  • »
    »
    7 weeks 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...

»
7 weeks 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.

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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.

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

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

      • »
        »
        »
        »
        7 weeks 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

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

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

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

Please give a hint about D

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

»
7 weeks 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?

  • »
    »
    7 weeks 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 .

  • »
    »
    7 weeks 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.

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

    let sa be a matrix containing sorted rows of a. If at any cell (I, j) a[I][j] != sa[i][j] this column(j) is a candidate column that might be swapped so insert it into a set. In the end, if the set contains more than 2 columns, the answer is -1. If it contains no values, just swap any column with itself. Else the set will contain 2 columns. In this case swap those two columns. And check if a[i][j] = sa[i][j] for all (i, j). If this is true then print those swapped column numbers else print -1.

    Note that the set which had candidate columns won't have only one column at any time because if there is an invalid column, which means the element at the current cell is not at the right position which further means that, this element is at the position of some other element hence that another element is also not in its correct position.

  • »
    »
    7 weeks 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

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

How to solve E?

»
7 weeks 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.

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

    26 were enough :P

    • »
      »
      »
      7 weeks 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).

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

Problem C Can any one help me why my method is wrong for problem C, what i did is take first array from the matrix then save values in other array with type pair<pair<int, int>, int> where the first int is the value of array second is max value in that column and the 3rd is the index of it, then sort it and try get the swaps from sorted to make it unsorted again and I sort the swaps, then swap every array in the matrix and check if it is sorted if yes print swaps else print -1. code

»
7 weeks 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 :( )

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

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

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

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

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

Why is pretests for C so weak?!

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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...

    • »
      »
      »
      7 weeks 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!

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

        The answer should/can be "1 3"?

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

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

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

            I see, luckily I am still in :)

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

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

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

    You guys are not already depressed?

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

      no i have no debression but sometimes my sadness turn into an attention seeking hope i can stop this habit someday

»
7 weeks 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

  • »
    »
    7 weeks 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

»
7 weeks 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??

  • »
    »
    7 weeks 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.

  • »
    »
    7 weeks 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.

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

FSTForces..

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

So many system test failure in C

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

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

»
7 weeks 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.

  • »
    »
    7 weeks 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.

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

    who it even based pretests? try somethign like : 1 1 1e8

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

      1 2 1e8 just forgot a < b but it the same idea in this case you just increase a from 1 to 1e8 with a step = 2 so the time complexity is something like o(c / 2) = o(c)

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

    If every case is a=1 b=2 c=1e8 and t=1e4,how many times you need in your while loop?

»
7 weeks 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.

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

Thank's for this brilliant pretests

»
7 weeks 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

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

The wonderful pretest made me go through the worse 520.

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

Thanks for the amazing pretests :(

»
7 weeks 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...

  • »
    »
    7 weeks 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
    
  • »
    »
    7 weeks 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??

    • »
      »
      »
      7 weeks 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)

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

f*** the pretests of C

»
7 weeks 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.

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

Finally algo tasks and systests, thank you!

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

Weak pretests hurt :'(

»
7 weeks 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!)

»
7 weeks 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.

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

As a tester, you all guys did shitty job

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

 pretest

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

Can somebody give me any stress test for E?

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

Thank you for the contest.

»
7 weeks 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.

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks 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)

»
7 weeks 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

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

Hello guys. 157718271 What is the test 21(24).

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

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

»
7 weeks 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.

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

    1 is right, since the first part of any contest is a server architect's worst nightmare aka stampeding herd problem...

    2 late adds are frowned upon as poor preparation and should be avoided... for this setter, it looks like randomized tests are their first approach to generating tests, so they're unlikely to hit more intentional cases e.g. where most or all elements of an array are equal, or the TLE case of today's B. If I've noticed this as far back as global 16... dunno what else there is to say/do from the outside...

    There was a discussion elsewhere about full(er) tests happening during an ongoing contest after the initial stampeding herd subsides, but it got sidetracked by a discussion on how masochistic we ought to be re: hacks and the like...

    I don't think the issue is the pre/systest system as much as the way coordinators/testers are used. Either they don't see pretests, or they saw them and said 'this looks fine and not random/lazy at all'... But also since setters and testers are usually friendly/local, we're maybe seeing a pattern of them being insufficiently adversarial... I don't want contests funneled into a narrow/boring range either, but if the current process is netting us an erratic/noisy experience, those would be my best guesses for where to start addressing issues (coordinators/testers could also take a setter's FST history into consideration).

    posted from my throne of bricks in full clown makeup

»
7 weeks 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.

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

    BASED

  • »
    »
    7 weeks 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.

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

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

»
7 weeks 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?

»
7 weeks 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

»
7 weeks 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!

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

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

  • »
    »
    7 weeks 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.

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

Why so many downvotes?

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

Good contest

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

Good contest , but f**king pretests !

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

weak pretests on C

»
7 weeks 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.

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

fucked I lost 1000 ranks because I wrote a.resize(n+1, vector(m+1)); instead of for(i: 1 to n) a[i].resize(m+1); in C

»
7 weeks 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

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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.

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

good contest and good problems.

»
7 weeks 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?

»
7 weeks 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?

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

    I bet you will get some instructions after removing of cheaters

»
7 weeks 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.

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

    Maybe you will receive an email after removing the cheaters.

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

Not so good

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

Can anyone tell me whats wrong in my C solution here

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

Good luck everyone!

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

can someone pls tell me what is wrong with my solution in D 157947183 .Thank you in advance!

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

Pretests were absurd.

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

Where is the prize?

»
5 weeks 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.

»
5 weeks 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?

»
5 weeks 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?