### shishyando's blog

By shishyando, 7 weeks ago, translation,

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!

• -426

 » 7 weeks ago, # |   -57 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, # ^ |   +202 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, # ^ |   +190 fucking clickbait
•  » » 7 weeks ago, # ^ |   -37 Testers be likeAs a tester give me contribution because i tested the round .. seriously
•  » » 7 weeks ago, # ^ |   +382 I'm sorry that these two tasks had to be replaced, I hope that we'll see them in the future.
•  » » » 7 weeks ago, # ^ |   +73 Don't get me wrong, the problems were ok and interesting, but Kacper is always fascinated by so-so problems.
•  » » » » 7 weeks ago, # ^ |   +9 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, # ^ |   +61 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, # ^ |   +86 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, # ^ |   +14 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, # ^ |   0 xyf007 if you know some similar problem to problem D ,please send me links for this type of problem
•  » » » » » 7 weeks ago, # ^ |   -7 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, # ^ |   0 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 Spoilerthere's a shit ton of one- and two- element sets
•  » » » » » » » 7 weeks ago, # ^ |   0 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, # ^ |   -8 Arbitrary sequences given in yhe input rather than those generated by Euclid algorithm
•  » » 7 weeks ago, # ^ |   +273 Maybe one task is best of 2011.
•  » » 7 weeks ago, # ^ |   +7 This comment didn't age well.
•  » » » 7 weeks ago, # ^ |   0 what do you mean??
 » 7 weeks ago, # | ← Rev. 4 →   +211 I think having 2 hours and 15 minutes in a 8-problem contest is better.
 » 7 weeks ago, # |   -14 I hope the contest is good
 » 7 weeks ago, # |   +246 As a tester, I missed the final rated round of my teenage.
•  » » 7 weeks ago, # ^ |   +33 Happy Birthday In Advance..
 » 7 weeks ago, # | ← Rev. 3 →   -27 .
 » 7 weeks ago, # |   +11 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, # ^ |   +5 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, # ^ |   +107 It's funny that such a things are proposed by a participants who anyway will not solve all of them :)
•  » » 7 weeks ago, # ^ |   +27 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, # ^ |   +139 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, # ^ |   +25 don't worry for tourist.
•  » » 7 weeks ago, # ^ |   0 Agreed
 » 7 weeks ago, # |   0 As a tester, I want to say participate in this round!
 » 7 weeks ago, # |   +47 Earlier there was a separate Div1 and Div2 round, but now it's a combined round. What was the reason?
•  » » 7 weeks ago, # ^ |   0 I am also thinking about it ;)
•  » » 7 weeks ago, # ^ |   +14 Prizes
 » 7 weeks ago, # |   +61 As a tester, I'm a bit jealous that you all get to compete for prizes lol
•  » » 7 weeks ago, # ^ |   +66 Previously you got double happiness of Grandmaster and 69 at once so it got balanced.
 » 7 weeks ago, # |   +23 Why is it combined?
•  » » 7 weeks ago, # ^ |   -80
•  » » 7 weeks ago, # ^ |   +76 I think because it has prize and div 2 users also have chance to win the prize
 » 7 weeks ago, # |   +44 As a tester, I get to mention _Vanilla_ for no reason.
 » 7 weeks ago, # |   +87 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, # ^ |   +66 If anyone interested, it didn't even offer me to proceed to the contest page
 » 7 weeks ago, # |   -27 Hopeforces
 » 7 weeks ago, # |   -22 TestersForces
 » 7 weeks ago, # |   -14 i want to be stronger hhhh.
 » 7 weeks ago, # |   0 This is my First contest, very excited. All the best to me and you all.
 » 7 weeks ago, # | ← Rev. 3 →   -24 It will be fun.
 » 7 weeks ago, # |   +27 NEAR coins in this round worth a lot less than NEAR coins in that previous round. :(
•  » » 7 weeks ago, # ^ |   0 But still more than a t-shirt, see current price
•  » » 7 weeks ago, # ^ |   0 Near year party is over
 » 7 weeks ago, # |   +10 looking forward strong pretest !
•  » » 7 weeks ago, # ^ |   0 Hahahahaha.TimDee
 » 7 weeks ago, # |   0 Good luck!
 » 7 weeks ago, # |   -7 You will have 2 hours to solve 8 problems.Gonna have to dance with pen now
 » 7 weeks ago, # |   +5 I really love the coins distribution.
 » 7 weeks ago, # |   0 okay! wishes all of you
 » 7 weeks ago, # |   0 I am not able to register now
 » 7 weeks ago, # |   +13 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 →   +21 Weak pretests for C I guess. My $O(N^3)$ passed lol.
 » 7 weeks ago, # |   +37 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 →   +9 tourist gets back to rank 1 through 1 hack!
 » 7 weeks ago, # |   +183 Trying to hack B
•  » » 7 weeks ago, # ^ |   -18 oh no
 » 7 weeks ago, # |   +31 Tougher B: Link
 » 7 weeks ago, # |   +17 greedy forces!
 » 7 weeks ago, # |   -8 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 →   0 I will assume that you are talking about this submissionso 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, # |   +32 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, # |   0 some one pls tell that how to solve C :*
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 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, # ^ |   0 What about [4 4 3] ?
•  » » » » 7 weeks ago, # ^ |   +3 We should always pick the two extreme ones only(If there exist any). In this case index [1, 3].
•  » » » » » 7 weeks ago, # ^ |   +3 Or just Compare them with the sorted array and check which are not in position .
•  » » 7 weeks ago, # ^ |   0 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, # |   +10 Hmm, where did I see that plot twist happen before?
 » 7 weeks ago, # |   0 Can anyone tell me whats wrong in my D solution here
•  » » 7 weeks ago, # ^ |   0 anyone plz??
•  » » 7 weeks ago, # ^ |   +1 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, # ^ |   +3 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, # ^ |   0 Do you yourself create test cases by stress testing after every contest on your website or is it created automatically?
•  » » » » » 7 weeks ago, # ^ |   +9 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, # ^ |   0 sounds cool!
•  » » » 7 weeks ago, # ^ |   0 Got it thank u , will try another approach.
•  » » 7 weeks ago, # ^ |   +1 Failing testcase: Ticket 7275
 » 7 weeks ago, # |   0 Amazing contest, I love it!
•  » » 7 weeks ago, # ^ |   +39 I take my words back. Very weak pretests, especially for task C
 » 7 weeks ago, # | ← Rev. 2 →   +17 I think you should use Bold words to tell us following operation exactly once in problem C, It wasted me 1h!
•  » » 7 weeks ago, # ^ | ← Rev. 4 →   0 same
•  » » 7 weeks ago, # ^ |   +17 I think you should read the problem statement carefully.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   -72 you fking want to express sth?
 » 7 weeks ago, # |   +12 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, # ^ |   +33 how was C casework?
•  » » » 7 weeks ago, # ^ |   0 Dirty
•  » » 7 weeks ago, # ^ |   0 It took me forever to figure out WA pretest 6 lol.
•  » » 7 weeks ago, # ^ |   0 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, # ^ |   +30 Why exactly is that bad? If someone was guessing the current samples would make it harder to guess.
•  » » 7 weeks ago, # ^ |   0 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, # ^ |   0 I dont think they are comparable. that would be like that problem A didnt have a 2-digit sample lol.
•  » » 7 weeks ago, # ^ |   +35 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 →   +3 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, # ^ |   0 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, # ^ |   +25 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, # |   +3 Is D a DP solution?? if yes then how do i optimise it from O(n^2) complexity
•  » » 7 weeks ago, # ^ |   0 I did a greedy
•  » » 7 weeks ago, # ^ |   +3 It's greedy
•  » » 7 weeks ago, # ^ |   0 I didn't use DP. Refer it if it passes system test :|
•  » » 7 weeks ago, # ^ |   0 Use greedy strategy, O(nlogn)
•  » » 7 weeks ago, # ^ |   0 DP worked but couldn't optimize it further from O(n^2) so I tried with greedy
•  » » 7 weeks ago, # ^ |   0 it was greedy+sorting
 » 7 weeks ago, # |   +6 Made a clutch solution on E at 1:59:46 and it passed pretests. :)
 » 7 weeks ago, # |   +10 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, # ^ |   -8 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, # ^ |   0 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, # |   0 spent too much time on different DP strategies for D but then realized it can be done by greedy
 » 7 weeks ago, # |   -30 B is not a programming problem.
•  » » 7 weeks ago, # ^ |   0 I solved A, C, and D and couldn't solve B
•  » » 7 weeks ago, # ^ |   +19 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 →   +6 That's actually my core competence ;)Edit: lol, I was fairly close Spoiler int z=a+b+c; int x=a+b; int y=b; cout<
•  » » 7 weeks ago, # ^ |   0 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 →   0 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, # ^ |   0 You can do it with two segment trees, one for sum and one for count of distinct numbers.
•  » » 7 weeks ago, # ^ |   +35 I binary search the largest possible MEX, then remove group of numbers more than MEX greedily.
•  » » » 7 weeks ago, # ^ |   0 thats sounds easier, didn't know you have to maximize mex
•  » » » » 7 weeks ago, # ^ |   +3 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, # ^ |   0 I have the same idea, but I found the largest MEX greedily.
 » 7 weeks ago, # |   0 Please give a hint about D
•  » » 7 weeks ago, # ^ |   +7 Hint you need use all the jump. consider the contribution when jumping over some trap: (+cnt)(-a[i])
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   +10 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, # |   0 Hello, How to solve C? I understood the statement and I can't implement the solution. any help?
•  » » 7 weeks ago, # ^ |   0 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, # ^ |   0 Thank you, I'll try to implement it.
•  » » 7 weeks ago, # ^ |   0 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, # ^ |   0 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, # ^ |   0 thxx broo nice explination
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 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, # |   +3 How to solve E?
 » 7 weeks ago, # |   +43 I hope there won't be 700 systests in H which will disappear later like some time ago.
•  » » 7 weeks ago, # ^ |   +24 26 were enough :P
•  » » » 7 weeks ago, # ^ |   +8 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, # |   0 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, 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 →   +28 FSTforces. Wait and see how many people will FST on C.(including me :( )
•  » » 7 weeks ago, # ^ |   -10 Same here :( Found out WA test only after the contest end :(
 » 7 weeks ago, # |   0 this was the best speed forces. what is happening there?
 » 7 weeks ago, # |   -8 Why is pretests for C so weak?!
•  » » 7 weeks ago, # ^ |   0 How do you know it as of now? AFAIK, system testing has not yet begun.
•  » » » 7 weeks ago, # ^ |   0 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 →   +30 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} •  » » » » 7 weeks ago, # ^ | 0 The answer should/can be "1 3"? •  » » » » » 7 weeks ago, # ^ | +10 Yes, codes that wiil FST on this case will output "-1". •  » » » » » » 7 weeks ago, # ^ | 0 I see, luckily I am still in :)  » 7 weeks ago, # | +9 nice round hope not to turn on depression mode after system tests •  » » 7 weeks ago, # ^ | +10 You guys are not already depressed? •  » » » 7 weeks ago, # ^ | -10 no i have no debression but sometimes my sadness turn into an attention seeking hope i can stop this habit someday  » 7 weeks ago, # | +20 Question B appeared on codeforces not long agohttps://codeforces.com/gym/103415/problem/H •  » » 7 weeks ago, # ^ | +1 But in this round there was a constrain , i.e a  » 7 weeks ago, # | +1 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, # ^ | +27 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, # ^ | +12 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, # | +8 FSTForces..  » 7 weeks ago, # | +21 So many system test failure in C  » 7 weeks ago, # | +8 Wow very strong pretests. Good bye codeforces shifting to Atcoder and Codechef  » 7 weeks ago, # | ← Rev. 4 → 0 I only solved A, I hope next contest I will solve 3 problems. •  » » 7 weeks ago, # ^ | ← Rev. 2 → 0 It works in O(c). It's obvious that it TLEs if a = 1 b = 2 c = 1e8 and 10000 testcases. •  » » 7 weeks ago, # ^ | 0 who it even based pretests? try somethign like : 1 1 1e8 •  » » » 7 weeks ago, # ^ | 0 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, # ^ | 0 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, # | +19 When the test-case setters confuse a Codeforces Div. (1 + 2) with a TopCoder SRM.  » 7 weeks ago, # | +57 Thank's for this brilliant pretests  » 7 weeks ago, # | +18 Poor pretest hurts more than wa, thanks to problem setters for giving me a bad day  » 7 weeks ago, # | +8 The wonderful pretest made me go through the worse 520.  » 7 weeks ago, # | +8 Thanks for the amazing pretests :(  » 7 weeks ago, # | +4 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 → +3 Test case #77 for D: 1 10 5 1 1 1 1 1 1 1 1 1 1  •  » » 7 weeks ago, # ^ | +6 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, # ^ | +9 My mistake was this simple single line condition that was unnecessary ig: if((*ptr).first >= 0)  » 7 weeks ago, # | +15 f*** the pretests of C •  » » 7 weeks ago, # ^ | +18 and the pretests of D also  » 7 weeks ago, # | +6 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, # ^ | +61 •  » » » 7 weeks ago, # ^ | 0 the additional constraint : a •  » » » » 7 weeks ago, # ^ | +12 Well, it's strictly easier if I understand it correctly — you can simply copy the code from the gym and submit it in the round. •  » » » » » 7 weeks ago, # ^ | ← Rev. 2 → +36 Actually, 1028E - Restore Array is strictly harder than both problems. •  » » » 7 weeks ago, # ^ | 0 ohh nooo  » 7 weeks ago, # | +9 Finally algo tasks and systests, thank you!  » 7 weeks ago, # | 0 Weak pretests hurt :'(  » 7 weeks ago, # | +4 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, # | +1 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, # | +41 As a tester, you all guys did shitty job  » 7 weeks ago, # | ← Rev. 3 → +115 •  » » 7 weeks ago, # ^ | +26 *systest  » 7 weeks ago, # | 0 Meme ⊙﹏⊙∥  » 7 weeks ago, # | 0 Can somebody give me any stress test for E?  » 7 weeks ago, # | +18 Thank you for the contest.  » 7 weeks ago, # | +10 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, # ^ | +15 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, # ^ | +18 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, # |   0 There were 22 tests in problem C, and Mine had to fail on the last one :) lucky me
 » 7 weeks ago, # |   0 Hello guys. 157718271 What is the test 21(24).
 » 7 weeks ago, # |   0 1300 (before sys test) -> 900 (after sys test) lol
 » 7 weeks ago, # | ← Rev. 3 →   0 I'm thinking about why Codeforces divide test cases to pretests and system tests, and there might be two reasons. Using pretests instead of full tests during the contest can sometimes avoid the server being overwhelmed by too many judging tasks. 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, # ^ |   0 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 →   -43 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, # ^ |   0 BASED
•  » » 7 weeks ago, # ^ |   +2 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, # ^ | ← Rev. 2 →   0 Take a look at this https://leetcode.com/discuss/general-discussion/2039697/weekly-contest-293 Also take a look a few recent contests, there were people uploading solutions mid Codeforces contest.Guess who were the cheaters.
•  » » » » 7 weeks ago, # ^ |   0 The point is not all indians are cheaters...not all cheaters are indians
•  » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +11 Yup not all, only 90%+ and increasing over time, and it happened on almost all the popular contest platform.
 » 7 weeks ago, # |   +19 At least the rating of this announcement behaves like crypto prices.
 » 7 weeks ago, # |   0 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, # |   0 https://codeforces.com/contest/1684/submission/157739291 can anyone help me in getting where i am going wrong
 » 7 weeks ago, # |   +73 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, # |   -78 How did this () contest get NEAR's support?
•  » » 7 weeks ago, # ^ |   0 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, # |   0 Why so many downvotes?
•  » » 7 weeks ago, # ^ |   +7 For excellent pretest:-)
 » 7 weeks ago, # |   0 Good contest
 » 7 weeks ago, # | ← Rev. 4 →   +39 Good contest ， but f**king pretests !
•  » » 7 weeks ago, # ^ |   +22 totally agree
 » 7 weeks ago, # | ← Rev. 4 →   0 weak pretests on C
 » 7 weeks ago, # |   +5 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, # ^ |   0 Use seg tree and D will not be easy
 » 7 weeks ago, # |   -14 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, # |   0 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, # ^ |   0 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, # ^ |   +3 Cheers, man! I was only calculating complexity and etc, never checked the logical part before.
 » 7 weeks ago, # |   -9 good contest and good problems.
 » 7 weeks ago, # | ← Rev. 2 →   0 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 →   0 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, # ^ |   +3 I bet you will get some instructions after removing of cheaters
 » 7 weeks ago, # |   0 How can I get my near? I got place 128 but I didn't receive an email.
•  » » 6 weeks ago, # ^ |   +3 Maybe you will receive an email after removing the cheaters.
 » 7 weeks ago, # |   0 Not so good
 » 7 weeks ago, # | ← Rev. 2 →   0 Can anyone tell me whats wrong in my C solution here
 » 6 weeks ago, # |   0 Good luck everyone!
 » 6 weeks ago, # |   0 can someone pls tell me what is wrong with my solution in D 157947183 .Thank you in advance!
•  » » 6 weeks ago, # ^ |   0 Failing testcase: Ticket 7280
•  » » » 6 weeks ago, # ^ |   0 ohhh..thank you for this!
 » 6 weeks ago, # |   0 Pretests were absurd.
 » 6 weeks ago, # |   +35 Where is the prize?
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # |   0 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, # |   0 Can anyone recommend where I can exchange this NEAR nonsense for USD or any real currency?
•  » » 5 weeks ago, # ^ |   0 metaverse
 » 5 weeks ago, # |   0 After sending the public key, I accidentally refreshed the web page and I lost my passphrase. What should I do?