Mangooste's blog

By Mangooste, history, 12 months ago, translation,

Hello, Codeforces! (づ｡◕‿‿◕｡)づ ❤

On Feb/12/2022 17:35 (Moscow time) we will host Codeforces Global Round 19.

It is the first round of a 2022 series of Codeforces Global Rounds supported by XTX Markets. The rounds are open and rated for everybody.

The presents for this round:

• 30 best participants get a t-shirt.
• 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The presents for the 6-round series in 2022:

• In each round top-100 participants get points according to the table.
• The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
• The best 20 participants over all series get sweatshirts and place certificates.

The problems were written and prepared by Mangooste, TeaTime, __JustMe__ and EvgeniyPonasenkov.

We are very thankful to people, who made this round possible:

You will have 2.5 hours to solve 8 problems. And we recommend you to read all the problems!

The score distribution will be announced closer to the start of the round.

UPD: The scoring distribution: 500 — 1000 — 1500 — 2000 — 2500 — 3250 — 4000 — 4000

UPD: Editorial.

Congratulations to the winners:

Announcement of Codeforces Global Round 19

• +1029

 » 12 months ago, # |   +334 We tried our hardest to make interesting tasks. We hope you will enjoy solving our problems as much as we did enjoy creating them (づ｡◕‿‿◕｡)づ
•  » » 12 months ago, # ^ |   -41 more confusing question is first
 » 12 months ago, # |   +26 AIs not partipicating again?
•  » » 12 months ago, # ^ |   +18 Call in Google)
•  » » » 12 months ago, # ^ | ← Rev. 2 →   -43 Or apply for a job in Google and ask your boss)
•  » » 12 months ago, # ^ |   +55 :/...
•  » » » 12 months ago, # ^ |   +10 I think google developers are sure that AI will get place in first 5000 rank so it's useless to participate in contests now and they wait until they make enough progress to participate in a contest that they can get a good rank.
 » 12 months ago, # |   +48 I still have PTSD from the last round having cute text emoticons in the announcements.
•  » » 12 months ago, # ^ |   +69 ଘ(੭*ˊᵕˋ)੭* ੈ♡‧₊˚!
•  » » » 12 months ago, # ^ |   +14 ლ(´ڡლ)
•  » » 12 months ago, # ^ | ← Rev. 2 →   +11 hmm same. I couldn't solve D1 B and later got my A hacked, which I couldn't fix by the end of the contest either. :clown:
 » 12 months ago, # |   +76 Proposing to rename master rank to maestro for EvgeniyPonasenkov
•  » » 12 months ago, # ^ |   +6 unfortunately only russians can understand this
 » 12 months ago, # |   +53 As a tester I really enjoyed solving and upsolving problems from this contest. Hope you too!(* ^ ω ^)
 » 12 months ago, # |   +21 cutea
•  » » 12 months ago, # ^ |   +3 here before atilla gets negative contribution
•  » » » 12 months ago, # ^ | ← Rev. 2 →   -10 I decided not to type it (sorry for people who didn't get the context)
•  » » » » 12 months ago, # ^ |   -22 context
•  » » » » » 12 months ago, # ^ |   +8 lmao
 » 12 months ago, # |   0 Good luck to everyone :)
 » 12 months ago, # |   +85 Programmers if the AI fails to beat them
•  » » 12 months ago, # ^ |   +115 Programmers who create the AI :
•  » » » 12 months ago, # ^ |   -27 in the style of akshay bhaiya...XD :)
 » 12 months ago, # | ← Rev. 2 →   +143 I was looking forward to a rated round but then a notification reminded me that I tested a round recently ;(GLHF everyone though, let us all :sip: at this special contest.
•  » » 12 months ago, # ^ | ← Rev. 2 →   -67 hello
•  » » » 12 months ago, # ^ |   +50 No.
•  » » » 12 months ago, # ^ |   +42 Tbh it gives those t-shirts some prestige right?
•  » » » » 12 months ago, # ^ |   0 yes, definitely, but what is the advantage to give it to the same people again. Either way distributing it among 1000 and 50 shirts is more encouraging to people. Those in top 1000 also have some prestige right ?
•  » » » » » 12 months ago, # ^ |   +6 But after its increased to 1000, someones gonna say why not increase it to 2000 and so on
 » 12 months ago, # |   0 (づ｡◕‿‿◕｡)づ ❤
•  » » 12 months ago, # ^ |   0 :-))
 » 12 months ago, # |   +43 Mangooste orz for authoring two concecutive rounds.
 » 12 months ago, # | ← Rev. 2 →   +43 Why is there no mention of XTX Markets in the announcement? (edit: now added)
 » 12 months ago, # |   +5 I wish everyone to increase their rank)
•  » » 12 months ago, # ^ |   +13 If wishes would've worked this way, I would be a lgm by now.
•  » » 12 months ago, # ^ |   0 which isn't possible by the way
 » 12 months ago, # |   0 Are AI accounts participating? Bet these AI bots did not recover well from the last round Spoiler
 » 12 months ago, # | ← Rev. 2 →   -49 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.How about distributing it last 500 people? lol
 » 12 months ago, # |   0 Auto comment: topic has been updated by Mangooste (previous revision, new revision, compare).
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 DmitryGrigorev for the great coordinating and helping us with preparing probles.typo in problemsEdit: fixed
•  » » » 12 months ago, # ^ |   0 Thank you! Fixed.
 » 12 months ago, # |   -25 (づ｡◕‿‿◕｡)づ ❤ ???
 » 12 months ago, # |   +4 Will it contain any interactive problem?
•  » » 12 months ago, # ^ |   +16 No.
•  » » » 12 months ago, # ^ |   +9 nice
 » 12 months ago, # | ← Rev. 2 →   +41 Good luck everyone!Hope you enjoy the tasks ♡!!!P.S. Actually, it takes a lot of hard work to prepare every task properly, so upvote the initial post as a sign of respect for the contest setters.
 » 12 months ago, # | ← Rev. 2 →   -19 i dont care
 » 12 months ago, # |   0 I add rating every time I join Global Round, hope you so. Really enjoy. :)
 » 12 months ago, # |   -23 Will this round be rated?
•  » » 12 months ago, # ^ |   0 Yes, it is rated for everyone.
•  » » » 12 months ago, # ^ |   -17 ok, thank you
 » 12 months ago, # | ← Rev. 2 →   -17 how to participate in? upd:found it haha
 » 12 months ago, # |   +27 Hoping for a nice round!I will be not able to participate in contests for a long time after this round because of the new term. TAT
 » 12 months ago, # |   0 NANOGrav
 » 12 months ago, # | ← Rev. 2 →   -43 I hope I will enjoy it！
 » 12 months ago, # |   +3 hoping to first time get rank under 1500 in div 2.
 » 12 months ago, # |   0 Best of luck, all
•  » » 12 months ago, # ^ |   0 Thanks, you too
 » 12 months ago, # |   -16 this one goes out to all my fellow noobs:
 » 12 months ago, # |   -97 "The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest."so she doesn't get any result?
 » 12 months ago, # |   -11 My first global round.. hope I will enjoy solving the problems. I enjoy contests!
 » 12 months ago, # |   +1 Is registration during contest not allowed?
 » 12 months ago, # |   0 I wasted too much time on B and C ... overthinking sucks man!
•  » » 12 months ago, # ^ |   -8 I wasted on A. Took less time on B and C than A
 » 12 months ago, # |   -52 Yeah, maybe this contest will make me a pupil
•  » » 12 months ago, # ^ |   +22 What other rules are on Codeforces? Do not use anybody photo except yours. It is uncultured and could confuse Codeforces users.
 » 12 months ago, # |   -65 Solved C in 30 minutes, solved D in 80 minutes, and then solved E in 20 minutes. What a disbalance!! Problem D isn't quite good, because you need just guess, that you have to minimize |sum(a)-sum(b)|. Rest was good, Liked problem E
•  » » 12 months ago, # ^ | ← Rev. 2 →   +4 You don't need to guess, dp[i][sum] = 1..i, sum = sum of a, it's easy to calculate the answer.
•  » » 12 months ago, # ^ |   0 I figured that minimization actually but couldn't able to implement can anyone tell how to minimize |sum(a)-sum(b)|?
•  » » » 12 months ago, # ^ |   0 Find all the possible sum(a) instead (using variation of knapsack algo)
•  » » 12 months ago, # ^ |   +72 "You need to guess".I don't think there is any guesswork to this problem. Expand $(a_i + a_j)^2$ as $a_i^2 + a_j^2 + 2 \cdot a_i \cdot a_j$. Clearly the two square terms will occur regardless of which array you are in. Toying around with equations a bit, we can realize sum $2 \cdot a_i \cdot a_j$ over all $i \lt j$ is just $(\sum{a_i})^2 - \sum{(a_i^2)}$. The second part is again constant regardless of which array we put it in. So now we clearly want to minimize $(\sum{a_i})^2 + (\sum{b_i})^2$ which is identical to your condition.
•  » » » 12 months ago, # ^ |   +8 Simple and clear. Sad that I did not get the equations.
•  » » 12 months ago, # ^ |   +22 you don't have to guess, just $dp[i][sum]$ — min cost of $a[0...i]$ + $b[0...i]$ after doing swaps on first $i$ positions and sum of $a[0...i]$ is $sum$.
•  » » » 12 months ago, # ^ |   0 Could you explain please how does this give us the correct answer? I still don't really get it.
•  » » » » 12 months ago, # ^ |   +7 after going through other people's code and reading the editorial i found out that my solution is pretty retarded, since i did not realize some parts of the cost are independent, but whatever:first let's assume we have just one array, for example $[1, 2, 4]$ and add $x$ to the end of it, how does the cost change?$old cost + (1 + x)^2 + (2 + x)^2 + (4 + x)^2$, which if we rewrite is $old cost + x^2 + 2x + 1 + x^2 + 4x + 4 + x^2 + 8x + 16$. (just $(a + b)^2 = a^2 + 2ab + b^2$, which is what i should have realized earlier, because it means $a^2$ and $b^2$ are independent, but since i solved for one unknown, i did not realize that, anyways)you can generalize that expansion to $i * x^2 + x * 2 * \displaystyle\sum_{j=0}^{i-1} a_j + \displaystyle\sum_{j=0}^{i-1} a_j^2$.now let $dp[i][sum]$ have 3 values, the minimum cost and then $\displaystyle\sum_{j=0}^{i-1} a_j^2$ and $\displaystyle\sum_{j=0}^{i-1} b_j^2$. The last two values are the retarded part, since they could be completely omitted, because each $a_i^2$ is counted $n - i$ times in the final cost. ($0$-indexed and same for all of $b_i$).Anyways, first let's set all the of the states to $\{\infty, \infty, \infty\}$.Base cases are $dp[0][a_0] = dp[0][b_0] = \{0, a_0 * a_0, b_0 * b_0\}$.Now the transition are: $dp[i+1][sum + a_i] = min(dp[i+1][sum + a_i], \{dp[i][sum][0] + f(i, a_i, sum, dp[i][sum][1]), dp[i][sum][1] + a_i * a_i, dp[i][sum][2] + b_i * b_i\})$ $dp[i+1][sum + b_i] = min(dp[i+1][sum + b_i], \{dp[i][sum][0] + f(i, b_i, pref_i - sum, dp[i][sum][2]), dp[i][sum][1] + b_i * b_i, dp[i][sum][2] + a_i * a_i\})$ $pref_i = \displaystyle\sum_{j=0}^{i} a_j + \displaystyle\sum_{j=0}^{i} b_j$ — sum of first $i$ values of $a$ and $b$.$f(i, x, sum, sumOfSquares) = i * x^2 + 2 * x * sum + sumOfSquares + a_i * a_i$ — cost of adding $x$ to the end of an array with length $i$ and sum of it's elements and sum of squares of each of it's elements. (you can see the independent part of the cost being independent in this function too lmao, can't believe i have not noticed this while solving the problem for the first time in contest)answer is then minimum of ${dp[n][sum]}$ for all $sum$ from $0$ to $\displaystyle\sum_{i=0}^{n-1} a_i + b_i$.I know, it's extremely retarded. But that's how i solved it during the contest (i can finally solve harder tasks than before, but most of the time it is this kind of an overkill for some reason) and you asked for it so ¯\_(ツ)_/¯.if you have any questions, feel free to ask. but for your sanity, i recommend simply reading the editorial.
•  » » » » » 12 months ago, # ^ |   0 Thanks a lot!
•  » » » » » 12 months ago, # ^ |   0 Man took his job too seriously
•  » » 12 months ago, # ^ |   0 I solved B really quickly but took an hour on C and had to leave the contest before I had a chance to solve D
 » 12 months ago, # |   +16 Somehow, you can pass pretests in E if you use unordered_map, but not gp_hash_table, is it intended? I thought gp_hash_table should be way faster... Also, my solution seems to be $O(n \log n)$ and is already quite close to the time limit, was it intentional that $O(n \sqrt n)$ doesn't pass? Or did it pass for others?
•  » » 12 months ago, # ^ |   +5 You can solve it in $O(n \sqrt n)$ without unordered sets, though the TL is pretty tight even then.I had to replace a map of vectors with a single vector of pairs to pass pretests since the constant factor difference in iterating over them was too heavy.
•  » » 12 months ago, # ^ |   +8 My $O(n \sqrt n)$ passed pretests in 967/2000 ms
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Mine passed pretests with O(n root(n) ), but i dont use any maps or hash tables for the bottleneck part of the code, e.g. the (n root(n) ) part doesnt use any maps, i map the values to [1 ... n] beforehand.
•  » » 12 months ago, # ^ |   +8 I used map and also passed pretests. Hope I wouldn't fail system test.
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 My $O(n \sqrt n)$ almost got TLE on pretest (1965/2000ms). Why $n \le 3 \times 10^5$ and 2s TL if $O(n \sqrt n)$ is intended?
•  » » 12 months ago, # ^ |   0 My $\mathcal{O}(m\log^2n)$ solution with segment tree gave TLE twice before it passed all the pretests.
•  » » 12 months ago, # ^ |   0 The problem is likely the hash function you are using. See this comment.
•  » » » 12 months ago, # ^ |   0 Yeah... I spent like an hour optimizing my $O(n \sqrt n)$ thinking it's the problem. But just replacing gp_hash_table with unordered_map was enough in the first place and I just wasted a lot of time trying to circumvent it.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 I'm kind of surprised to see that the TL was so tight for others since my $O(n\sqrt{n}\log{(n+m)})$ solution passed in 530 ms.
•  » » » 12 months ago, # ^ |   0 Read -is-this-fft-'s comment. It may be a non-sqrt solution.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 Oh you're right. It's $O(n\log{(n+m)})$. That's really interesting.
 » 12 months ago, # |   0 How to solve G?
 » 12 months ago, # |   0 wxhtzdy orz
 » 12 months ago, # | ← Rev. 3 →   -16 never mind this is trash i had no time to think about it well
 » 12 months ago, # |   +29
 » 12 months ago, # |   0 What's the ideal time complexity to solve E?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 O(n * lg(n) + m * lg(m))
•  » » 12 months ago, # ^ |   0 I solved it in O(N*sqrt(N)) with the ideia that if the sum of elements is equal N the number of different is O(sqrt(N)).
•  » » 12 months ago, # ^ |   0 I solved it in O(nlogn + mlogm) complexity (or something like that) and the "logn" and "logm" factors come from the C++ STL maps and sets I used, as well as the STL sort function. If you really want, you could replace the maps and sets with their hash-based counterparts and the STL sort with a count sort and get a linear time complexity... (I think)
 » 12 months ago, # |   +3 How to solve B?
•  » » 12 months ago, # ^ | ← Rev. 2 →   +6 $dp[i][j][k] :=$ the maximum cost to split $b[i, ..., j]$ into k subsegments minus j-i+1 (which means $dp$ includes only the sum of $MEX$ part).base case: $dp[i][j][1] = MEX(b_i, ..., b_j)$transition: $dp[i][j][k] = \max(dp[i][x][1] + dp[x+1][j][k-1]) \ \ \forall x \in [i, j)$time complexity for calculating $dp$ is $O(n^4)$, then add up the solutions for all subsegments.for a subsegment $[i, j]$ we care about the $k$ s.t. $dp[i][j][k] + j-i+1$ is the max.
•  » » 12 months ago, # ^ |   0 For each a[i], I set its value to 2 if a[i] is 0 else 1. Then for each number, multiply its value by the number of subsegments it is in and add that to your answer. Finally, print your answer.
•  » » 12 months ago, # ^ |   0 Greedy approach: 146089472Time complexity: O(n^3 log(n))
•  » » 12 months ago, # ^ | ← Rev. 2 →   +6 notice that max cost on a subsegment is simply length of subsegment + number of 0's in subsegment. Just sum this value over all subsegments to get answer.
•  » » 12 months ago, # ^ |   +3 (One of) the best way(s) to break each subarray is always to break it into single elements. It brings the length of subarray plus number of zeroes in it. So the result is the sum of lengthes of all possible subarrays plus number of occurencies of zeroes in all of them. With given constraints, it is possible to brute force it.
 » 12 months ago, # | ← Rev. 4 →   -19 Weak and useless samples!
 » 12 months ago, # |   +7 Imagine implementing $O(n \sqrt{n})$ in E (and doing constant factor optimization to get it to pass) only to realize afterwards the easier $O(n \sqrt{n} \log{n})$ solution somehow runs faster — 146115870
•  » » 12 months ago, # ^ |   0 How do you come with the sqrt solution in E? I still don't quite get it. So basically we can just store the frequency of all numbers and bruteforcing each possible pairs?
•  » » » 12 months ago, # ^ |   +1 because there are at most $O(\sqrt{n})$ distinct cnt values.
 » 12 months ago, # |   -11 E was only about realizing we need to keep max 2 elements per count (max O(sqrt(n)) candidates )? Such low number of submissions completely threw me off :/
•  » » 12 months ago, # ^ |   0 Did your solution work? I think you need more than 2 elements per count in case those two elements form a bad pair.
 » 12 months ago, # | ← Rev. 2 →   0 For problem D, it took me a long time to realize that the given cost is $(a_1 + ... + a_n) ^ 2 + (n - 2) * (a_1 ^ 2 + ... + a_n ^ 2)$, and the second part doesn't affect the answer.But if I just guess "minimizing $|sum(a) - sum(b)|$", which is actually intuitive, then I can submit a solution much quicker. However, I don't think guessing is a good way to solve problems.
 » 12 months ago, # |   +143 Feedback on the problems: A: Ok. B: The idea is nice, the way you decided to transform the idea into a problem, so-so. Would have been cleaner with $n=100\,000$ and just asking for the value of the array (instead of the sum over whatever). C: Good problem. The moment I read it, I thought I was going to get stuck and in fact I got stuck (at least I am consistent). For me, this was much harder than D. D: Very standard, solved immediately after reading. E: Very good problem. I had to think and when I noticed that $cnt$ can have at most $\sqrt{n}$ values and this was sufficient to solve the problem, I was somewhat happy. F: Cute problem. This felt easy, most likely because I was lucky and noticed immediately that rooting the tree at the highest vertex is useful. G: (unexpectedly) Cool problem. The first thought reading it is "who cares?". Then, when I saw the point of the problem (which was shown to me by a backtracking), I changed my mind. I solved this in contest apart from the limit on the number of queries (because I was doing something incredibly stupid), solved 3 minutes after the end of the round. I enjoyed solving it. H: Not read. I enjoyed a lot the contest because the problems at "my level" (i.e., E, F, G) were very nice. Thanks to the authors.
•  » » 12 months ago, # ^ |   +11 Agreed. Despite having a solution to G but writing stupid buggy code and not being able to fix it in time, I really liked the round. My favourite problem was F (with my implementation, it was a data structure problem!) but I liked E as well.
•  » » 12 months ago, # ^ |   +11 I got stuck at D for 1.5 hrs... Can I know how you mean by "very standard"? What's the first thought/idea after you read the problem?
•  » » 12 months ago, # ^ |   +12 can you please tell why problem D is very standard. Thanks
•  » » 12 months ago, # ^ |   +10 Thank you for participating and for positive feedback about this round. I am glad you like problem G!
 » 12 months ago, # |   0 After this, I feel so dumb. :(
•  » » 12 months ago, # ^ |   +3 Next time you feel that way, just click through my profile. It will make you feel better about yourself.
•  » » » 12 months ago, # ^ |   0 Please view my profile and you will feel sadder
•  » » » » 12 months ago, # ^ |   0 Youve been on a hot streak lately. In the last 2 contests you jumped from 12,292 up to almost top 500!!You literally cut your overall ranking in half! That's pretty impressive imo.
 » 12 months ago, # |   +5 If we comment via the "ask a question" link during the contest, is it visible to everyone or just the commentor/ judges? I made a mistake where I thought there was a problem flaw where there was none and I didn't know whether or not to apologize because I didn't want to disrupt anyone who was still coding.Also, if it is public, is there a better way to bring things like these up?Thanks to all, and especially to the judges for a wonderful round (and for putting up with the annoyance I may have caused you.)
•  » » 12 months ago, # ^ |   +1 it's only visible to the judges, and if they found that there is actually a mistake they will announce it
•  » » » 12 months ago, # ^ |   +1 Thank goodness!!! I was afraid I had disrupted the competition for no reason. I still looked foolish, I guess, just not in front of quite so many people. XDThank you for reply. +1
 » 12 months ago, # | ← Rev. 2 →   +140 E is interesting in the sense that based con some conversations I bet there are a lot of people who wrote an $O((n + m) \log n)$ or similar non-sqrt solution without realizing it.My solution is basically this: 1 for (int cx = 1; cx <= n; cx++) { 2 for (int x : wcnt[cx]) { // the list of things with cnt[x] = cx 3 for (int cy = 1; cy <= cx; cy++) { 4 // try the best non-forbidden y with cnt[y] = cy 5 } 6 } 7 } Trivia question: how many times is line 4 hit? Answer: it is in fact $O(n)$. For a fixed $x$, the number of times line 4 is executed is the frequency of $x$, so in total we visit line 4 once for every element in the array.I believe this proof can be adapted to several people who proudly claimed to have passed E in $O(n \sqrt n)$ or even $O(n \sqrt n \log n)$ with "no constant optimizations".
•  » » 12 months ago, # ^ |   +26 haha, I was guilty of this, good observation!
•  » » 12 months ago, # ^ |   -32 can u explain me test case 3 2 1 4 5 in problem A ,as it can be sorted by prefix and suffix
•  » » » 12 months ago, # ^ |   +3 You are not asked to find whether you can sort the array, but if you can make the operation so that the array is NOT sorted. Thus, choosing the prefix formed by the first two numbers and the suffix with the last 3 numbers would solve the testcase.
•  » » 12 months ago, # ^ |   0 I figured out the approach but I failed the system test because I had a typo in the break condition where I wrote ans>(cx+cy)(x*y) instead of (cx+cy)*(x+y). My solution when I replaced the * and submitted after the contest.
•  » » 12 months ago, # ^ |   -29 But your program actually is O(n sqrt(n)). I generate a data and your program updates ans 329094649 times.
•  » » » 12 months ago, # ^ |   0 sorry I read the wrong number.It's O(n).
•  » » 12 months ago, # ^ |   0 I have something like for (int x: unique_numbers) { for (int cnt_y: existing_cnts) { // no cnt_y <= cnt[x] check // find first non-forbidden y with cnt[y] = y } } Which works fast-ish as well. Do you understand if it's faster than O(n sqrt(n)) as well?
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +35 I initially thought just this this would be faster too, but it looks like this is still $\Theta(n \sqrt n)$.The complexity is the number of distinct frequencies, multiplied by the number of distinct values. For a given $n$ we can construct a bad case like this. Let $a$ be the number of distinct frequencies. Make a number with frequency 1, a number with frequency 2, ..., a number with frequency $a$, then add numbers with frequency 1 until we have filled the array. The number of distinct numbers is $a + n - \frac12 a(a + 1)$; the complexity will then be Unable to parse markup [type=CF_MATHJAX]Using calculus to maximize it for $a > 0$ shows that we can pick $a$ to get $\Theta(n \sqrt n)$ runtime.EDIT: I tried to hack you and got unexpected verdict. People tell me this is due to a tester (?) solution failing. Maybe tests are indeed weak here?
•  » » » » 12 months ago, # ^ |   0 It got rejudged. Almost 3x from the worst real test, but still passing :)
 » 12 months ago, # |   +11 I enjoyed this contest, it required a lot of observation, and problem C felt like a troll :Dtook many tries and observations to figure it out, but eventually i solved it.
 » 12 months ago, # | ← Rev. 2 →   -8 In problem A. 3 2 1 4 5 can be sorted as 3 2 1 and 4 5 are sorted individually so ans will be no ,but many has written solution as if there is increasing array ans will be yes. can anyone explain me this test case .
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Read the Problem again.
•  » » 12 months ago, # ^ |   0 ... and then sort in non-decreasing order the prefix ...
•  » » 12 months ago, # ^ |   0 I did the same mistake at first and wasted stupidly 1 hour on A. What you should do is find a value len for which the array is not going to be sorted at the end, if found then YES otherwise NO.
•  » » » 12 months ago, # ^ |   +1 solution is to just check if the array is sorted.
•  » » » » 12 months ago, # ^ |   0 Oh I overdid it then. The problem was north I went south I guess haha
•  » » » » » 12 months ago, # ^ |   0 Took me more than a hour to solve A.
 » 12 months ago, # |   0 Nice round! E was cute but I was a bit dumb on it.
 » 12 months ago, # | ← Rev. 2 →   0 For me, Problem C is harder than D and E. But liked the observation in C the most.
 » 12 months ago, # |   +8 did the 700th upvote:) nice problems , loved problem D
 » 12 months ago, # |   +33 pretest in E is so weak...
•  » » 12 months ago, # ^ |   +17 +1 to thisOne would think that a max test would be 1 300000 0 1 1 1 ... 1 1 but that has no solutions. so instead if you had done 1 300000 0 2 1 1 1 ... 1 1 you would have made the simplest max test. and yet not a single test in the pretests had an element occur more than 800 (which was a constant in my code) times.
•  » » » 12 months ago, # ^ |   +1 i find that. I just calc ans like (i+j)*p.w instead of (u+v)*p.w and it passed pretest:(
 » 12 months ago, # |   +64 F is cool, create interesting&fresh task on tree is giga hard nowadays, so thanks to authors :)
 » 12 months ago, # |   -9 Didn't use long long in C. (T_T)
•  » » 12 months ago, # ^ |   0 SameGot two submission wrong for it :)
•  » » 12 months ago, # ^ |   0 Same, I lost my expert for it :)
 » 12 months ago, # |   0 MikeMirzayanov My submission on E got TLE on system test. But the exactly same code passed after the contest.Could you rejudge the submission please? Thanks in advance!
•  » » 12 months ago, # ^ | ← Rev. 2 →   +18 The test case where I TLEed only takes 1871ms. The volatility is more than 129ms, which is a bit huge. I felt really bad about this :(
 » 12 months ago, # |   0 Spent too much time on C but solution is concise and pleasant 146131266
 » 12 months ago, # |   0 As for me, C was easy, but i didn't understand how to solve D. Help me please
 » 12 months ago, # |   0 How to prove that "minimum power of two at least n" is the minimum achievable value in G?
•  » » 12 months ago, # ^ |   +136 If we "undo" two numbers $x,y$ then two numbers become $\frac{x+y}{2},\frac{x-y}{2}$, so we can never get rid of any odd prime factor of the final value.
•  » » » 12 months ago, # ^ |   0 nice proof, thanks
 » 12 months ago, # |   +2 Fast Rating Change!!
•  » » 12 months ago, # ^ |   -15 Apparently, there was no plagiarism in this contest. The ranks during the contest are same as final standings. In the last educational round, Mike said that there would be a recheck and ratings would be updated after removing cheaters, and apparently, ratings never got updated. https://codeforces.com/blog/entry/99483?#comment-883045
 » 12 months ago, # |   -8 Can somebody please point out whats happening? I used modified knapsack in D and here are two submissions Solution 1 AC Solution 2 WA The only difference between them is that I sorted arrays a and b before knapsack in solution 2 but that should not affect the answer. Can somebody point out the reason? Thanks in advance
•  » » 12 months ago, # ^ |   0 You can only swap $a_i$ and $b_i$ for some $1 \le i \le n$, not $a_i$ and $b_j$ for some $1 \le i, \ j \le n$.
•  » » » 12 months ago, # ^ |   -8 oh shoot didn't notice that detail thanks a lot
•  » » » 12 months ago, # ^ |   -8 Can you suggest what changes would have to be made if any index swapping was allowed?
•  » » » » 12 months ago, # ^ |   +8 I did this for half the contest. I solved using 3d dp and bitset to achieve $O(n^3A/64)$ (A = maximum element). Basically finding out all possible sums when you select $n$ out of the $2n$ elements provided.
 » 12 months ago, # |   +98 Very cool round, thanks a lot to authors! Problems F, G were especially cool
•  » » 12 months ago, # ^ |   +11 One of the best rounds I have seen in a while, thanks a lot to the authors! Can't tell about GH, but I just loved how natural most of the problems were. Here's some specific feedback:A: this is the one I liked the least, fits too well into a recently-overused "implement the least complicated solution that passes sample testcases", and understanding the statement somewhat takes more time than coming up with the solution.B: absolutely an amazing problem for its position. Allows a simple mathematical solution, but there is also a straightforward DP if you don't feel like proving anything.. C: an adhoc, but a rather natural one, and the solution is quite neat, too.D: a more standard DP problem that requires some algebraic manipulation. Nice to see some DP in a Global Round.E: cute algorithmic problem, a bit more on the standard side too. This idea has appeared before in some Div1D based on Moscow State Olympiad (or something like that), nonetheless still a nice task!F: woah, this was brilliant! I failed to notice that "root in maximum" makes the life a lot easier, and instead implemented an overcomplicated DP which had a bug in the end. I'm amazed that you managed to find such a simple-statement algorithmic challenge that's fresh. Unlike some other GRs, this one really had a great balance in difficulty and topics. I hope that we will continue seeing more of your rounds! Mangooste et al.
 » 12 months ago, # |   +82 Shout out to kal013 for becoming the highest rated Indian of all time on cf by beating amnesiac_dusk.PS: I've been following both of them since I started cp :)
 » 12 months ago, # |   +22 great round overall :)
 » 12 months ago, # |   +70 If you believe that top-10 by cf rating as of now top-1 at codeforces global round 19 by atcoder penalty rules top-1 at being the most handsome guy in our ICPC team legendary overtrained upsolver Maksim1744 will win the next ICPC WF, then make sure to join his official fan group!
•  » » 12 months ago, # ^ |   +49 Proofpic about being handsome?
•  » » » 12 months ago, # ^ |   +62 Spoiler
•  » » 12 months ago, # ^ |   0 I want to join :D
 » 12 months ago, # |   0 When I take part in global round, it makes me feel sad every time.
 » 12 months ago, # |   -6 The description of this contest's problem is very bad！
 » 12 months ago, # |   -11 Truth be told,really really bad.I have never seen the bad description like this
»
12 months ago, # |
Rev. 10   +112

Unofficial T-shirt winners list

Update 2: It looks like cheaters have been removed, and the standings have been updated. As such, the full list of winning handles has been added.

Going forward, I'll post only the list places of winners (in a compact format) shortly (~12h) after the contest. While not as useful, you can still check to see if you're close to becoming a T-shirt winner. Once the standings have been updated to remove cheaters, I'll post the full list of winning handles.

Update 1: Since cheaters have not been removed yet, the standings is not final and is subject to change. As a result, this list of winners will probably change significantly. The list place of winners won't change, but the winning handles will. For now, I have removed the winning handles outside the top 30, and I will update the list once cheaters have been removed.

Since the official announcement isn't here yet and I'm an impatient person, I've decided to find out who won the t-shirts for myself.

As always, you can do the following steps to get the t-shirts winners of Global Rounds:

1) Download testlib.h from Mike's github repo.

2) Use it to compile randgen.cpp :

randgen.cpp

3) Run the Python script winners.py, replacing the number in contest = [] with the ID of the contest in question (in this case, 1637`):

winners.py

Both of these scripts are taken from the official winners announcements in previous Global Rounds, but if you have any doubts on their legitimacy you can always check these results against the official ones later.

With that out of the way, congratulations to the (unofficial) t-shirt winners:

List place Contest Rank Name
1 1637 1 tourist
2 1637 2 Um_nik
3 1637 3 Maksim1744
4 1637 4 heno239
5 1637 5 ksun48
6 1637 6 Vercingetorix
7 1637 7 jiangly
8 1637 8 SomethingNew
9 1637 9 Laurie
11 1637 11 fantasy
12 1637 12 Petr
13 1637 13 ecnerwala
14 1637 14 Endagorion
15 1637 15 visiteur
16 1637 16 wxhtzdy
17 1637 17 Egor
18 1637 18 antontrygubO_o
19 1637 19 A-SOUL_Bella
20 1637 20 kal013
21 1637 21 kotatsugame
22 1637 22 Y25t
23 1637 23 never_giveup
24 1637 24 hos.lyric
25 1637 25 1004535809
26 1637 26 KrK
27 1637 27 peti1234
28 1637 28 conqueror_of_tourist
29 1637 29 hanbyeol_
30 1637 30 BigBag
87 1637 87 golikovnik
93 1637 93 satashun
105 1637 105 kektus
113 1637 113 olphe
116 1637 116 fanache99
166 1637 166 CaiLiyi
171 1637 171 huangxiaohua
175 1637 175 lucaperju
176 1637 176 magnus.hegdahl
224 1637 224 HoshimiOWO
228 1637 228 anpoli99
255 1637 255 liouzhou_101
279 1637 279 AghaParsa
302 1637 302 Colchoneta
347 1637 347 flowerletter
373 1637 373 MysteryGuy2
383 1637 383 RedMind
401 1637 401 nikgaevoy
425 1637 425 priemniygeniy
449 1637 449 aropan

P.S. If any contest organizer has any issue with early unofficial winners list like this one, feel free to contact me.

•  » » 12 months ago, # ^ | ← Rev. 2 →   +88 Please note that most probably this list will change significantly after cheaters removal.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +13 Yeah that happened last time too, I will update the list when it happens.Next time it's probably best to wait 2-3 days before posting, but then not many people will be checking the thread and see the post.
 » 12 months ago, # |   0 When will be the plagiarism checking?
 » 12 months ago, # |   0 I was accused of cheating, and after i have checked ADO/146139752, ChtotoSlabovato/146145769, 9_shuriken/146152539 i realised that the only thing we have in common is partition function which was found by me on the internet by link https://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/. I was only copypasting from geekforgeeks, not from other contestants
»
10 months ago, # |
+28

Congratulations to tshirts winners! You will be contacted via private messages with instructions to receive your prize. Note that currently tshirts deliveries are significantly delayed due to multiple reasons, but we'll do our best to send the tshirts as soon as we can.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_tshirts.py
randgen.cpp
List place Contest Rank Name
1 1637 1 tourist
2 1637 2 Um_nik
3 1637 3 Maksim1744
4 1637 4 heno239
5 1637 5 ksun48
6 1637 6 Vercingetorix
7 1637 7 jiangly
8 1637 8 SomethingNew
9 1637 9 Laurie
11 1637 11 fantasy
12 1637 12 Petr
13 1637 13 ecnerwala
14 1637 14 Endagorion
15 1637 15 visiteur
16 1637 16 wxhtzdy
17 1637 17 Egor
18 1637 18 antontrygubO_o
19 1637 19 A-SOUL_Bella
20 1637 20 kal013
21 1637 21 kotatsugame
22 1637 22 Y25t
23 1637 23 never_giveup
24 1637 24 hos.lyric
25 1637 25 1004535809
26 1637 26 KrK
27 1637 27 peti1234
28 1637 28 conqueror_of_tourist
29 1637 29 hanbyeol_
30 1637 30 BigBag
87 1637 87 golikovnik
93 1637 93 satashun
105 1637 105 kektus
113 1637 113 olphe
116 1637 116 fanache99
166 1637 166 CaiLiyi
171 1637 171 huangxiaohua
175 1637 175 lucaperju
176 1637 176 magnus.hegdahl
224 1637 224 HoshimiOWO
228 1637 228 anpoli99
255 1637 255 liouzhou_101
279 1637 279 AghaParsa
302 1637 302 Colchoneta
347 1637 347 flowerletter
373 1637 373 MysteryGuy2
383 1637 383 RedMind
401 1637 401 nikgaevoy
425 1637 425 priemniygeniy
449 1637 449 aropan