When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

rng_58's blog

By rng_58, history, 7 years ago, In English

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

Contest Link

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.

I'll add some quick comments here.

A.

Spoiler

B.

Spoiler

C.

Spoiler

D.

Spoiler

E.

Spoiler

F.

Spoiler
  • Vote: I like it
  • +134
  • Vote: I do not like it

»
7 years ago, # |
Rev. 7   Vote: I like it +116 Vote: I do not like it

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!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +82 Vote: I do not like it

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +52 Vote: I do not like it

      I am out of the loop; could someone please educate me about this meme?

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +77 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          Rev. 3   Vote: I like it +43 Vote: I do not like it

          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?".)

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +26 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              Rev. 2   Vote: I like it +20 Vote: I do not like it

              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)

              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                Rev. 2   Vote: I like it +18 Vote: I do not like it

                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.

            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              Rev. 2   Vote: I like it +25 Vote: I do not like it

              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)

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          Lmao, thanks.

          Off topic, but what are the usual ways to check whether your problem has already been created before?

»
7 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Is there any feature to filter standings based on countries?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

»
7 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Can you explain how by dsu? And I think u should always try to include xor so that answer decreases by 1

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      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?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

»
7 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

A single testcase is worth 300 performance points ///

RIP rating (

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Idea behind B ?

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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

»
7 years ago, # |
  Vote: I like it +167 Vote: I do not like it

How is it possible to consistently hold contests with such good problems :o?

Btw editorial doesn't work.

»
7 years ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    Just curious, are you using a special extension/another website? (The interface is different)

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Omg, I have never thought about nimbers that way, that's clever

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did think of that, it's not what I'm missing. Seems it was a condition for outgoing edges.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had 883, when forgot, that you can have any edges to vertices of higher layers. Didn't you do the same?

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you tell the link to your submissions?

»
7 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

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).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, how do you prove that if H%h == 0 and W%w == 0 then the answer is No?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    You can partition the board into h × w disjoint rectangles. Each small rectangle has negative sum, so the total sum cannot be positive.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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
    
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can U explain me solution of problem B ?

»
7 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +34 Vote: I do not like it

    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)).

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      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.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        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.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it
»
7 years ago, # |
  Vote: I like it +133 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Pink.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    White :|

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    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

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      Starting from some rating (I don't actually know threshold) you can choose color if you want to.

      Source

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    rainbow

    As for dan, maybe "Alpha Go"?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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.
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 years ago, # |
  Vote: I like it +81 Vote: I do not like it

A safe strategy for tourist:

  1. Solve each tasks and test them well, but don't submit.
  2. When all tasks are solved, look at scoreboard, make sure no one solved all tasks. Submit all of them to win.
  3. 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.)

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Works on CSAcademy too.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    But what if he makes a mistake and one of the tasks is incorrect? Oh ... right ...

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Can someone give a detailed explanation on problem D? Still very confused.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Thank you for your clear explanation! Could you briefly prove that the constuction is optimal?

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Sorry for the delay, added proof for the official editorial.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      " 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.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        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.

»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Took me the whole day to fully understand problem D's solution. Worth it.

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Can you please upload this round's testcases? Thanks in advance

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I am getting verdict "IE" i.e Internal Error on my submission for Problem D. What does this mean?