### rng_58's blog

By rng_58, history, 10 months ago, ,

AtCoder Grand Contest 016 will be held on Sunday (time). The writer is sugim48.

Contest Announcement

The point values will be 300 — 700 — 700 — 1000 — 1400 — 1600.

Let's discuss problems after the contest.

UPD: Now the editorial (check page 5) is ready.

A.

Spoiler

B.

Spoiler

C.

Spoiler

D.

Spoiler

E.

Spoiler

F.

Spoiler

•
• +134
•

 » 10 months ago, # | ← Rev. 7 →   +116 Why the writer is currently flying? The ICPC world final was ended. Is this just copied the blog of AGC015? (Here) UPD: I have more request! There is no upcoming contest!
•  » » 10 months ago, # ^ |   +82
•  » » » 10 months ago, # ^ |   +52 I am out of the loop; could someone please educate me about this meme?
•  » » » » 10 months ago, # ^ |   +77 The guy in the picture copied an old problem exactly and proposed it as his own problem in Codechef SnackDown. When people realized the problem is copied, he said the famous words: Hi , so to me seems like a notorious coincidence. Though I have come across a similar technique in a programming article ( it was in Russian ) way back. A legend.
•  » » » » » 10 months ago, # ^ | ← Rev. 3 →   +43 And his (nssprogrammer) comment votes reached -688, the worst record in entire codeforces. I think even comment that written "Is it rated?" or "Please upvote me!" can't reach this record. (Though I'm not sure if red coder comments "Is it rated?".)
•  » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   +20 And after that big achievement (and a -292 This contest is helpless because it is first of yours, another -110 blog post, and a few more), the author of the second comment in the list now still has quite a positive contribution.A legend.(Btw would you mind sharing how you found out this ranking? – UPD Thanks Diversity for helping me out... It's here)
•  » » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   +18 Another great archievement is tweety. In Codeforces Round #347 Announcement, he gain -260, -268, -165, -122, -79 downvotes at once but his contribution is still +106. I introduce about some of his legend comments. 1. -268 votes: No rated contest today. Stay hungry :P 2. -165 votes: I'm sure now that it's unrated more people will participate, because they will be sure that someone beating them because he has the codes wouldn't affect their rating. A legend. UPD: tweety's contribution became to 107.
•  » » » » » » » » » 10 months ago, # ^ |   +50
•  » » » » » » » » » 10 months ago, # ^ |   +23 Don't worry, even Xellos (current 17th top contributor) got -274 in this comment.
•  » » » » » » » 10 months ago, # ^ | ← Rev. 2 →   +25 Man, you completely messed important piece of codeforces' history, namely history of second comment. Its original version was:"Do you want to win a T-shirt? No , I dont . Do you want to learn how to design tasks for programming contest? No , I dont . Do you want to solve 7 tasks in 2.5 hours? No , I dont. So Codeforces Round #270 is not right for me. Have a nice day.",nobody cares about current version (it was changed to it after it got that many downvotes)
•  » » » » » 10 months ago, # ^ |   +15 Lmao, thanks. Off topic, but what are the usual ways to check whether your problem has already been created before?
•  » » » » » » 10 months ago, # ^ |   +30 Having a community of competitive programming addicts to recognize old problems is probably the best way so far.
 » 10 months ago, # |   +27 Is there any feature to filter standings based on countries?
 » 10 months ago, # |   0 Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
 » 10 months ago, # | ← Rev. 2 →   +15 Does anyone have idea to mininum number of moves in D:XOR Replace?I could find the necessary condition to transform a into b, but couldn't find the minimum number of moves. I guess, the minimum number of moves are either mismatches or mismatches + 1, but couldn't find their corresponding cases.
•  » » 10 months ago, # ^ |   +14 The idea is very similar to that of Google CodeJam 3. The number of mismatches is indeed a lower bound, but you need to find minimum number of cycles to which you can decompose the swaps, and you can do that by union find. I wasted an hour by failing to understand how exactly is the N-th value (xor of all A values) play a role.
•  » » » 10 months ago, # ^ |   +10 Can you explain how by dsu? And I think u should always try to include xor so that answer decreases by 1
•  » » 10 months ago, # ^ |   +11 Sometimes you need more moves. For example '4 1 2 5 6 2 1 6 5' needs 6 moves. Analyze why and you will find how to get the minimum number of moves.
•  » » » 10 months ago, # ^ |   +25 I can solve this problem if both the arrays are some permutation of the first n numbers. But what if one number appearance more than once? How to create a graph in such case?
•  » » 10 months ago, # ^ |   +15 This was what I found in the contest :Reduce the problem to finding the minimum number of moves needed to turn an array a into b, where a move is swapping the last element with any other element of the array.Let the elements of array a be a0, a1, ..., an (an is equal to the xor of a0 to an - 1) and the elements of array b be b0, b1, ..., bn.Add an undirected edge from ai to bi for all i. Let x be the number of mismatches in the array a and b (not counting an and bn). For each component that does not contain an and bn and has size  ≥ 2, add 1 to the x. The answer is x.
 » 10 months ago, # | ← Rev. 2 →   +10 A single testcase is worth 300 performance points ///RIP rating (
 » 10 months ago, # |   +10 Idea behind B ?
•  » » 10 months ago, # ^ | ← Rev. 2 →   +5 Realize that the array has to be such that the difference between maximum and minimum values of the array is at most 1.Now there are two cases, either all the values of the array are same. That is only possible if all people have distinct color hats, or nobody has a distinct color hat.In the other case (when the difference is 1), let's assume the values are x and x+1, then all the people with value x must have a distinct color hat (i.e. each such person must have a color that no other person has). And for all the people with x+1, they should have a hat such that there is at least one other person, with value x + 1, that has the same color hat. Using this logic you will get an inequality. Code
•  » » » 10 months ago, # ^ |   0 Any idea what test case 20 is ? Getting WA on it http://agc016.contest.atcoder.jp/submissions/1364595
 » 10 months ago, # |   +167 How is it possible to consistently hold contests with such good problems :o?Btw editorial doesn't work.
 » 10 months ago, # | ← Rev. 2 →   +28 Now, tourist's rating is 3949, but in today's contest, he got 1st place. I think his rating may become over 4000. UPD: tourist's rating became to 4021. It will be one of the biggest record of AtCoder.
•  » » 10 months ago, # ^ |   +36 Just curious, are you using a special extension/another website? (The interface is different)
•  » » » 10 months ago, # ^ |   +11 I'm using a special extension: AtCoder Custom Standings which made by koyumeishi. But this system has only Japanese version, so I hope that the system will be extended to the English version.
 » 10 months ago, # |   0 Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
 » 10 months ago, # |   +28 I tried F. The graph formulation of Sprague-Grundy is that we need to split the DAG into layers such that from each layer, we have edges to all layers below and vertices 1 and 2 are in the same layer, which can be done using a DP picking whole layers and all edges into them at once in . However, I'm getting a different result on the last test, consistent with checking by hand. Is that the whole right idea or am I forgetting something?
•  » » 10 months ago, # ^ |   0 Omg, I have never thought about nimbers that way, that's clever
•  » » 10 months ago, # ^ |   0 I had the same situation with the following bug: when a certain layer contains one of (1,2), we're certain that we have achieved what we need, so I added 1 to the number of ways. But we need to add 2 to the power of the number of edges connecting yet unassigned vertices.
•  » » » 10 months ago, # ^ |   0 I did think of that, it's not what I'm missing. Seems it was a condition for outgoing edges.
•  » » 10 months ago, # ^ |   0 I had 883, when forgot, that you can have any edges to vertices of higher layers. Didn't you do the same?
•  » » » 10 months ago, # ^ |   0 That's it. I thought "there can't be any edges from the bottom layer because these are losing positions" but didn't realise they can be indirectly losing.
 » 10 months ago, # |   0 Was I the only one who had issues with problem C?The checker was kinda strict, because difference between cout << "No\n";  and  cout << "No"; Cost me ~2-3 submissions and huge amount of time wasted
•  » » 10 months ago, # ^ |   0 Could you tell the link to your submissions?
 » 10 months ago, # | ← Rev. 3 →   +5 On E, a O(N2·M) solution optimized with bitset passed in 400ms. This is a bit sad (I did it this way, but I feel bad and feel like I hacked the problem).
 » 10 months ago, # |   0 For problem C, how do you prove that if H%h == 0 and W%w == 0 then the answer is No?
•  » » 10 months ago, # ^ |   +23 You can partition the board into h × w disjoint rectangles. Each small rectangle has negative sum, so the total sum cannot be positive.
•  » » 10 months ago, # ^ |   +6 Divide the entire board into H/h * W/w submatrices. Sum of each such submatrix must be negative whereas the whole some must be positive, so you get a contradiction. For example, if W=H=4 and w=h=2, you have: a[1][1] + a[1][2] + a[2][1] + a[2][2] < 0 a[1][3] + a[2][3] + a[1][4] + a[2][4] < 0 a[3][1] + a[4][1] + a[3][2] + a[4][2] < 0 a[3][3] + a[4][4] + a[3][4] + a[4][3] < 0 ------------------------------------- add them all and you get sum of all the elements in the matrix is negative and it should be positive 
 » 10 months ago, # |   +3 Can U explain me solution of problem B ?
 » 10 months ago, # |   +38 For F it wasn't clear from limitations that you don't want solution in O(Bell(n - 2)·n2) to pass. Actually, I squeeze it through TL after the contest.
•  » » 10 months ago, # ^ | ← Rev. 2 →   +34 I had O(Bell(n - 2)·n) and it passed easily in 2 seconds out of 5. Increasing n by 2 would disallow my solution, but this would imply setting TL to 10-15 seconds, which is not too great.EDIT: to be exact, my solution is O(Bell(n - 1)).
•  » » » 10 months ago, # ^ |   0 I think, i can optimize my solution to O(3n) from O(3n * n) which works 0.8s. After it, it probably will pass n = 17 within 5 seconds. But i'm not sure, it will make problem better.
•  » » 10 months ago, # ^ |   +8 Our bell solution took more than 20s, and we didn't want to make the constraints too tight for O(3^n * n) solution. But yes, we should have used bigger n.
•  » » 10 months ago, # ^ |   0 The TL was pretty loose IMO. My solution takes less than 200 ms and can be optimised further. It's O(N·3N), but treats vertices 1 and 2 as special, which improves the constant.
•  » » » 10 months ago, # ^ |   +18 Usually I don't like the idea "set constraints as high as possible". One of our solutions worked in 133ms, but at the same time poorly written O(3nn) C++ solution took 2s. And it doesn't look nice if the intended complexity is O(3n * n) and the TL is 1s for n = 15.
•  » » » » 10 months ago, # ^ |   +20 For me, rule of thumb is "set the constraint as low as possible in order to not let slow solutions pass". This seemed to be pretty hard here, especially if you got Bell solution that took 20s.
•  » » » » 10 months ago, # ^ |   0 My rule of thumb is that a theoretically good solution should theoretically pass (if the contestant got lucky and the constant didn't end up too big), so a very poorly (10x) written solution taking 2s means the TL should be 2s like normal.
 » 10 months ago, # |   +15
 » 10 months ago, # |   +133 Our color/dan scheme is very systematic. The range of each color is exactly 400. We added silver crowns for 3200-3600, and gold crowns for 3600-4000. The range of each dan is exactly 200. This is something that never decrease (so we use the peak rating), and is used in Go or Shogi (Japanese chess).I thought I carefully chose parameters such that reaching red in AtCoder is as hard as reaching red in TC or CF, and reaching 4000 is barely impossible for humans. However, tourist beat the rating system today. Congratulations!Does anyone have an idea for new color/dan? Note that usually the highest "dan" is 10.
•  » » 10 months ago, # ^ |   +32 Pink.
•  » » 10 months ago, # ^ |   +33 White :|
•  » » 10 months ago, # ^ |   +43 Btw could you explain why some users have not really expected color? Like semiexp or Um_nikAnd my suggestion for new color is rainbow xD
•  » » » 10 months ago, # ^ |   +28 Starting from some rating (I don't actually know threshold) you can choose color if you want to. Source
•  » » 10 months ago, # ^ |   +11 As for dan, maybe "Alpha Go"?
•  » » » 10 months ago, # ^ |   +23 But the colors are in a weird order...
•  » » 10 months ago, # ^ |   0 By the way, how does "kyu" system work? I checked that rating 1 corresponds to 20 kyu, 2 corresponds to 19 kyu, and 4 corresponds to 18 kyu.I'm sure margin of "kyu" is different from "dan", but I don't know exactly how the system works.
•  » » » 10 months ago, # ^ |   +15 Let x be the internal rating, and y be the displayed rating. We don't want to display negative ratings, so If x ≥ 400, y = x. If x < 400, y = abx. a, b are the only constants that make this function differentiable.
•  » » 10 months ago, # ^ |   +10 You can scale the displayed rating in a fashion similar to ratings <400 to introduce an upper cap. I hope tourist would not object if he converged to 4400.
•  » » 10 months ago, # ^ |   0 I have an idea about Dan: 3800-3999: 10 dan 4000-4199: Legend 4200-4399: Winner 4400-4599: God By the way, the maximum performance in entire AtCoder history is about 4500, so rating won't be exceed 4600.
 » 10 months ago, # |   +81 A safe strategy for tourist: Solve each tasks and test them well, but don't submit. When all tasks are solved, look at scoreboard, make sure no one solved all tasks. Submit all of them to win. If someone already solved all tasks, abandon this round and wait for next one. Looks like this strategy only works at AtCoder? (And he indeed submitted all tasks after 1 hour in this round.)
•  » » 10 months ago, # ^ |   +15 Works on CSAcademy too.
•  » » 10 months ago, # ^ |   +45 But what if he makes a mistake and one of the tasks is incorrect? Oh ... right ...
 » 10 months ago, # |   0 Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
 » 10 months ago, # |   +33 Can someone give a detailed explanation on problem D? Still very confused.
•  » » 10 months ago, # ^ |   +28 Reduce the problem to finding the minimum number of moves needed to turn an array a into b, where a move is swapping the last element with any other element of the array (if you have trouble here, see the current editorial)Let the elements of array a be a0, a1, ..., an (an is equal to the xor of a0 to an - 1) and the elements of array b be b0, b1, ..., bn.Do coordinate compression on these numbers and suppose there are v distinct numbers. Construct a graph on v vertices with the following method :Add an undirected edge from ai to bi for all 0 ≤ i ≤ n with ai ≠ bi. (We allow multiedges here)Each edge of this graph describes a mismatched pair. Note that each vertex has even degree, as if x appears k times in a, then it must appear k times in b. Thus, each component has an Eulerian cycle. Now, we can use these Eulerian cycles to construct the optimal solution. For the component containing an, we can perform the swaps according to the Eulerian cycle and use e - 1 swaps to accomplish the goal (where e is the number of edges in that component). After that, the last element will be bn and if the component containing bn is still unresolved, we can use e moves to resolve it, where e is the number of edges in that component. For every other component that does not contain an or bn, we require e + 1 moves to resolve that component. This summarizes to :Let x be the number of mismatches in the array a and b (not counting an and bn). For each component that does not contain an and bn and has at least one edge, add 1 to the x. The answer is x.
•  » » » 10 months ago, # ^ |   +10 Thank you for your clear explanation! Could you briefly prove that the constuction is optimal?
•  » » » » 10 months ago, # ^ |   +10 Sorry for the delay, added proof for the official editorial.
•  » » » 10 months ago, # ^ |   +13 " For the component containing an, we can perform the swaps according to the Eulerian cycle and use e - 1 swaps to accomplish the goal (where e is the number of edges in that component). After that, the last element will be bn and if the component containing bn is still unresolved, we can use e moves to resolve it". I had some difficulty understanding this part because I was unable to understand why an and bn would be in different components (if an is resolved, then so is bn). If an != bn, they are in the same component as there is an edge between them. If an = bn, they are in the same component as they are the same node. Could you perhaps explain your statement with a small example? :) I got AC adding e if an = bn, and e-1 if an != bn, where e is number of edges in the component of an.
•  » » » » 10 months ago, # ^ |   +15 Ya I didn't realize an and bn are already guaranteed to be in the same component by construction of the graph :P. You're right, we should add e if an = bn and e - 1 if an ≠ bn for the component containing an.
 » 10 months ago, # |   +18 Took me the whole day to fully understand problem D's solution. Worth it.
 » 10 months ago, # |   +10 Can you please upload this round's testcases? Thanks in advance
•  » » 10 months ago, # ^ |   +15 yes, uploaded.
•  » » » 10 months ago, # ^ |   +20 Where are the testcases uploaded?
•  » » » » 10 months ago, # ^ |   +13
•  » » » » » 10 months ago, # ^ |   +10 Thanks!
 » 10 months ago, # |   +10 I am getting verdict "IE" i.e Internal Error on my submission for Problem D. What does this mean?
•  » » 10 months ago, # ^ |   +10 Internal Error. Fixed now.