Привет, Codeforces!
Мы приглашаем вас принять участие в контесте, который пройдет в 19.05.2022 17:35 (Московское время). У вас будет 2 часа на решение 8 задач. Раунд рейтинговый для участников обоих дивизионов.
Я бы хотел поблагодарить тех, благодаря кому этот раунд состоится:
- Artyom123 и KAN за координацию раунда и активную помощь
- gamegame, generic_placeholder_name, kpw29, physics0523, teraqqq, Kirill22, SecondThread, vsinitsynav, SlavicG, flamestorm, snowysecret, KiruxaLight за тестирование и много полезного фидбека, благодаря которому мы неоднократно меняли раунд
- MikeMirzayanov за наши любимые платформы Codeforces и Polygon
Также мы бы хотели поблагодарить компанию NEAR, при поддержке которой проходит этот раунд. Компанию основал бывший участник соревнований AlexSkidanov. Также в команде, разрабатывающей NEAR, работают многие известные участники сообщества, например, дважды чемпион мира ICPC eatmore и победитель GCJ и TCO Egor.
В раунде предусмотрены призы в NEAR коинах для участников, которые займут первые 255 мест. Победитель раунда получит Ⓝ128, участники на втором и третьем месте по Ⓝ64, участники на следующих четырех позициях по Ⓝ32, и так далее.
Кроме того мы рады сообщить, что достоверные участники (уже участвовавшие хотя бы 5 рейтинговых раундах), занявшие одно из первых 255 мест, также получат приглашения в проект CrowdForces! Этот проект запущен на NEAR уже как полгода и позволяет участникам получать Ⓝ за решение задач на CrowdScript с разных платформ: Codeforces, SPOJ, E-Olymp, AtCoder, UVa Online Judge.
Именно с этим проектом связаны легенды в условиях на русском языке. Они идут курсивом в первом абзаце каждой задачи.
Разбалловка задач:
500 — 750 — 1250 — 1500 — 1750 — 2000 — 2500 — 3250
Мы надеемся, что вам понравятся задачи! Удачи на контесте!
Разбор: ссылка
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!
As per history of codeforces, whenever a tester says the round will be very good, the contest turns out to be bad.
fucking clickbait
I'm sorry that these two tasks had to be replaced, I hope that we'll see them in the future.
Don't get me wrong, the problems were ok and interesting, but Kacper is always fascinated by so-so problems.
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
Yeah, ofc. I can be mistaken too, so I'm all ears, which problems deserve to be the best ones in 2022 and why?
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
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.
xyf007 if you know some similar problem to problem D ,please send me links for this type of problem
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.
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
there's a shit ton of one- and two- element sets
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.)
Arbitrary sequences given in yhe input rather than those generated by Euclid algorithm
Maybe one task is best of 2011.
This comment didn't age well.
I think having 2 hours and 15 minutes in a 8-problem contest is better.
I hope the contest is good
As a tester, I missed the final rated round of my teenage.
Happy Birthday In Advance..
I hope the problems are interesting and easy. Good luck for my first contest , and for everyone too!
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?
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.
It's funny that such a things are proposed by a participants who anyway will not solve all of them :)
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.
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.
don't worry for tourist.
Agreed
Удачи всем вы все всё сможете но я постараюсь решить хотя бы задачи A и B.
А я вам желаю решить все восемь задач :)
It's impossible if you use Python
As a tester, I want to say participate in this round!
Earlier there was a separate Div1 and Div2 round, but now it's a combined round. What was the reason?
I am also thinking about it ;)
Prizes
As a tester, I'm a bit jealous that you all get to compete for prizes lol
Previously you got double happiness of Grandmaster and 69 at once so it got balanced.
Why is it combined?
I think because it has prize and div 2 users also have chance to win the prize
As a tester, I get to mention _Vanilla_ for no reason.
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.
If anyone interested, it didn't even offer me to proceed to the contest page
NEAR coins in this round worth a lot less than NEAR coins in that previous round. :(
But still more than a t-shirt, see current price
Near year party is over
Can't wait for the contest. Hopefuly I'll be able to solve at least 2 questions.
looking forward strong pretest !
Hahahahaha.
TimDee
Good luck!
You will have 2 hours to solve 8 problems.
Gonna have to dance with pen now
I really love the coins distribution.
I am not able to register now
Hopefully, I pass system test for all questions for which my pretests are passed. Last two times it didn't :(
operationforces
Weak pretests for C I guess. My $$$O(N^3)$$$ passed lol.
Problem H was here. Unfortunately, I wasted most of my time on the contest on H because the solutions posted there are wrong.
tourist gets back to rank 1 through 1 hack!
Tougher B: Link
greedy forces!
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.
some one pls tell that how to solve C :*
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 .
What about [4 4 3] ?
We should always pick the two extreme ones only(If there exist any). In this case index [1, 3].
Or just Compare them with the sorted array and check which are not in position .
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
Hmm, where did I see that plot twist happen before?
Can anyone tell me whats wrong in my D solution here
Consider this test
your solution says that the answer is 4, but you can achieve a score of 3 by jumping over the third trap.
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).
Do you yourself create test cases by stress testing after every contest on your website or is it created automatically?
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.
Failing testcase: Ticket 7275
Amazing contest, I love it!
I take my words back. Very weak pretests, especially for task C
I think you should use Bold words to tell us following operation exactly once in problem C, It wasted me 1h!
I think you should read the problem statement carefully.
you fking want to express sth?
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.
how was C casework?
Dirty
It took me forever to figure out WA pretest 6 lol.
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.
Why exactly is that bad? If someone was guessing the current samples would make it harder to guess.
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?
I dont think they are comparable. that would be like that problem A didnt have a 2-digit sample lol.
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.
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
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.
what dirty case work? just sort the columns lexicographically and find the number of non-equal columns what kind of case work is that?
Is D a DP solution?? if yes then how do i optimise it from O(n^2) complexity
I did a greedy
It's greedy
I didn't use DP. Refer it if it passes system test :|
Made a clutch solution on E at 1:59:46 and it passed pretests. :)
I feel like F was slightly easier than D,E. At least D required an idea, F was just juggling claims about segments.
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 >_>
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.
spent too much time on different DP strategies for D but then realized it can be done by greedy
B is not a programming problem.
Based on the previous comments of yours, I feel like ranting about math problems in a contest is a recurring theme of yours lol.
That's actually my core competence ;)
Edit: lol, I was fairly close
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...
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.
You can do it with two segment trees, one for sum and one for count of distinct numbers.
I binary search the largest possible MEX, then remove group of numbers more than MEX greedily.
thats sounds easier, didn't know you have to maximize mex
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
I have the same idea, but I found the largest MEX greedily.
Please give a hint about
DFirst 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.
Hello, How to solve C? I understood the statement and I can't implement the solution. any help?
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 .
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.
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
How to solve E?
I hope there won't be 700 systests in H which will disappear later like some time ago.
26 were enough :P
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).
FSTforces. Wait and see how many people will FST on C.(including me :( )
Same here :(
Found out WA test only after the contest end :(
this was the best speed forces. what is happening there?
Why is pretests for C so weak?!
How do you know it as of now? AFAIK, system testing has not yet begun.
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...
Here's a test that I and probably some other ones will FST on:(
I thought we just need to try swapping columns with $$$a_{i,j} \lt a_{i,j-1}$$$.
FST for me again!
The answer should/can be "1 3"?
Yes, codes that wiil FST on this case will output "-1".
I see, luckily I am still in :)
nice round hope not to turn on depression mode after system tests
You guys are not already depressed?
problem B： https://mirror.codeforces.com/gym/103415/problem/H
Question B appeared on codeforces not long ago
https://mirror.codeforces.com/gym/103415/problem/H
But in this round there was a constrain , i.e a<b<c. Which makes the problem in this contest easier
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??
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.
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.
FSTForces..
So many system test failure in C
Wow very strong pretests. Good bye codeforces shifting to Atcoder and Codechef
I only solved A, I hope next contest I will solve 3 problems.
It works in O(c). It's obvious that it TLEs if a = 1 b = 2 c = 1e8 and 10000 testcases.
When the test-case setters confuse a Codeforces Div. (1 + 2) with a TopCoder SRM.
Thank's for this brilliant pretests
Poor pretest hurts more than wa, thanks to problem setters for giving me a bad day
The wonderful pretest made me go through the worse 520.
Thanks for the amazing pretests :(
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...
Test case #77 for D:
I also got WA 77. The mistake I made in my code is that
k * (k-1) / 2in line 64 should bei * (i-1) / 2. How did it passed the pretest??My mistake was this simple single line condition that was unnecessary ig:
if((*ptr).first >= 0)
f*** the pretests of C
and the pretests of D also
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.
problem B
the additional constraint : a<b<c made the problem easier, so it may look similar but not same
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.
Actually, 1028E - Restore Array is strictly harder than both problems.
Finally algo tasks and systests, thank you!
Weak pretests hurt :'(
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!)
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) / 2fork * (k-1) / 2?After getting -200 delta, now I have to go back to candidate master and participate Div.2-only rounds again.
As a tester, you all guys did shitty job
*systest
Can somebody give me any stress test for E?
Thank you for the contest.
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 > minstead of2 * big + small > m). See 157733355, 157719356, 157726787.I feel the need to identify myself as one of the
big + 2*smalljokers because I just find it so incredibly funny that you can pass systests with such a mistakeI 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)
There were 22 tests in problem C, and Mine had to fail on the last one :) lucky me
1300 (before sys test) -> 900 (after sys test) lol
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.
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.
BASED
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.
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.
The point is not all indians are cheaters...not all cheaters are indians
Yup not all, only 90%+ and increasing over time, and it happened on almost all the popular contest platform.
At least the rating of this announcement behaves like crypto prices.
Was it the following distribution of problems today?
Or it’s slightly different?
https://mirror.codeforces.com/contest/1684/submission/157739291 can anyone please help i am not able to understand where i am going wrong
https://mirror.codeforces.com/contest/1684/submission/157739291 can anyone help me in getting where i am going wrong
To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!
How did this () contest get NEAR's support?
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.
Why so many downvotes?
For excellent pretest:-)
Good contest ， but f**king pretests !
totally agree
weak pretests on C
i am loser that can not have a green color, wuwuwuwu,cry...
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.
Use seg tree and D will not be easy
Any idea why this solution is getting TLE?
The complexity (as I calculated) is O(m*n), where m*n<=2*10^5
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.
Cheers, man! I was only calculating complexity and etc, never checked the logical part before.
good contest and good problems.
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:
Is my complexity analysis wrong? Can anyone hack my solution?
Please help ;(. I don’t know how to get my crypto.
P.s. My email is unavailable. Maybe I should restore my email?
I bet you will get some instructions after removing of cheaters
How can I get my near? I got place 128 but I didn't receive an email.
Maybe you will receive an email after removing the cheaters.
Where is the prize?
shishyando?
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.
Can anyone recommend where I can exchange this NEAR nonsense for USD or any real currency?
After sending the public key, I accidentally refreshed the web page and I lost my passphrase. What should I do?
great round bro enjoyed reading problems