AtCoder Grand Contest 016 will be held on Sunday (time). The writer is sugim48.
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.
I'll add some quick comments here.
A.
Spoiler
B.
Spoiler
C.
Spoiler
D.
Spoiler
E.
Spoiler
F.
Spoiler
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!
I am out of the loop; could someone please educate me about this meme?
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:
A legend.
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?".)
Here is the ranking of the highest downvotes comments.
1. -688 votes
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.
Link(-688 votes)
2. -600 votes
Thanks everyone who downvoted this comment . I broke a record and became last one in contribituon list . This is a big achievement in my eyes. Start upvoting now !
Link(-600 votes)
3. -332 votes
A true Codeforces fan can not scroll down without upvoting this comment .
Link(-332 votes)
A legend.
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 Len for helping me out... It's here)
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.
Don't worry, even Xellos (current 17th top contributor) got -274 in this comment.
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)
Lmao, thanks.
Off topic, but what are the usual ways to check whether your problem has already been created before?
Having a community of competitive programming addicts to recognize old problems is probably the best way so far.
Is there any feature to filter standings based on countries?
Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
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.
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.
Can you explain how by dsu? And I think u should always try to include xor so that answer decreases by 1
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.
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?
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.
A single testcase is worth 300 performance points ///
RIP rating (
Idea behind B ?
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
Any idea what test case 20 is ? Getting WA on it http://agc016.contest.atcoder.jp/submissions/1364595
How is it possible to consistently hold contests with such good problems :o?
Btw editorial doesn't work.
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.
Just curious, are you using a special extension/another website? (The interface is different)
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.
Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
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?
Omg, I have never thought about nimbers that way, that's clever
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.
I did think of that, it's not what I'm missing. Seems it was a condition for outgoing edges.
I had 883, when forgot, that you can have any edges to vertices of higher layers. Didn't you do the same?
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.
Was I the only one who had issues with problem C?
The checker was kinda strict, because difference between
cout << "No\n";
andcout << "No";
Cost me ~2-3 submissions and huge amount of time wasted
Could you tell the link to your submissions?
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).
For problem C, how do you prove that if H%h == 0 and W%w == 0 then the answer is No?
You can partition the board into h × w disjoint rectangles. Each small rectangle has negative sum, so the total sum cannot be positive.
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:
Can U explain me solution of problem B ?
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.
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)).
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.
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.
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.
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.
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.
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.
Screencast
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.
Pink.
White :|
Btw could you explain why some users have not really expected color? Like semiexp or Um_nik
And my suggestion for new color is rainbow xD
Source
As for dan, maybe "Alpha Go"?
But the colors are in a weird order...
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.
Let x be the internal rating, and y be the displayed rating. We don't want to display negative ratings, so
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.
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.
A safe strategy for tourist:
Looks like this strategy only works at AtCoder? (And he indeed submitted all tasks after 1 hour in this round.)
Works on CSAcademy too.
But what if he makes a mistake and one of the tasks is incorrect? Oh ... right ...
Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
Can someone give a detailed explanation on problem D? Still very confused.
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.
Thank you for your clear explanation! Could you briefly prove that the constuction is optimal?
Sorry for the delay, added proof for the official editorial.
" 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.
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.
Took me the whole day to fully understand problem D's solution. Worth it.
Can you please upload this round's testcases? Thanks in advance
yes, uploaded.
Where are the testcases uploaded?
Here: https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGii3rHX6Fa?dl=0
Thanks!
I am getting verdict "IE" i.e Internal Error on my submission for Problem D. What does this mean?
Internal Error. Fixed now.