antontrygubO_o's blog

AtCoder Grand Contest 052 Announcement
By antontrygubO_o, 4 years ago, In English

I am glad to invite you to AtCoder Grand Contest 052. This contest counts for GP30 scores.

I would like to thank:

Statements are very short, and I really hope you will like the problems.

We are looking forward to your participation!

UPD 1: The point values will be 400-800-1000-1000-1500-2000, and the duration is decided to be 160 minutes

UPD 2: Congratulations to the winners!

  1. ksun48
  2. mnbvmar
  3. tourist
  4. Benq
  5. Radewoosh

Thanks for your participation :P

  • Vote: I like it
  • +407
  • Vote: I do not like it

Comments Comments (27)
| Write comment?
»
4 years ago, # |
  Vote: I like it +153 Vote: I do not like it

→ Reply
»
4 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Can we say "All hail our emperor anton" here?

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Why is it 1200+ rated , I am new to atcoder and currently brown , I was waiting for this for a week until I came to knew that it is 1200+ rated (Today) . I know I can participate unofficially but still rated contest have their own charm , This is not right to make them rated for 1200+ according to me . Y have a lower threshold?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +43 Vote: I do not like it

Finally our emperor created a round on his favourate website with his favourate problems. :qq:

→ Reply
»
4 years ago, # |
  Vote: I like it +113 Vote: I do not like it

As a tester (my only comment as tester so far, despite having tested other rounds), this round seems inspired and I'm amazed at the quality of problems. I would highly recommend participating to have your mind blown.

P.S. All hail our emperor Anton

→ Reply
»
4 years ago, # |
  Vote: I like it +61 Vote: I do not like it

How many problems did you propose in order to get 6 accepted?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

    9, but mostly to fix the difficulty balance

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it -41 Vote: I do not like it

      It was meant to be joke. I would like to sincerely apologize to Anton. You are among the people whose name is enough in announcement to keep me awake at 1am during some contests. Sorry!

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +74 Vote: I do not like it

        The coordinator rejects bad problems. If you propose $$$100$$$ bad problems, most of them will be rejected. If you propose $$$6$$$ good problems, most of them will be accepted.

        → Reply
»
4 years ago, # |
  Vote: I like it +293 Vote: I do not like it

Every time I read problem A of any AGC, I question my existence...

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Every time i read your name, it answers all my doubts about me.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +46 Vote: I do not like it

I can stare at a problem only for so long. someone pls tell how to solve B after contest ends

Edit: Editorial out right after contest. Thanks!

→ Reply
»
4 years ago, # |
  Vote: I like it +78 Vote: I do not like it

This contest was genius and it was 100% worth destroying my sleep schedule to fail on it. All hail our emperor Anton.

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

tfw you know how to solve C but are just a bit too slow because you thought you could squeeze in a slower solution

Also fun fact: I figured out B when I thought about what happens if the tree is a star — if we consider everything XOR'd by $$$X$$$, then $$$(w_1 \oplus X, w_2 \oplus X, \ldots, w_k \oplus X)$$$ changes to $$$(w_1 \oplus X \oplus (w_2 \oplus X), 0 \oplus w_2 \oplus X, \ldots, w_k \oplus X \oplus (w_2 \oplus X))$$$, which is $$$(w_1 \oplus w_2, X \oplus w_2, \ldots, w_k \oplus w_2)$$$, so $$$w_2$$$ and $$$X$$$ only swap places. From that, I intuited that we must be able to add a variable and convert the problem to swapping, and what's a better extra variable than a vertex weight! Kinda roundabout, but a natural way to look at a problem — look at a specific case and generalise.

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

    I have a question how can we prove that W can be generated after doing the operation any number of times

    → Reply
»
4 years ago, # |
  Vote: I like it +173 Vote: I do not like it

Show some mercy, it was so hard ;_;

→ Reply
»
4 years ago, # |
  Vote: I like it +80 Vote: I do not like it

After solving A, I was like: "Thanks for cyberbulling"

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Can't agree more. I was only able to solve it coz I saw jiangly solved it under 4 min, so thought of some constructive approach.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

After reading the editorial, I realize that I completely misread problem B during the contest. I thought it was $$$w := w_1 \oplus w$$$ instead of $$$w_1 := w_1 \oplus w$$$. In hindsight I forgot to apply the rule of thumb that pronouns are usually intended to have the most recent possible referent, or could have noticed the potential ambiguity and asked for clarification. But the wording of this problem could definitely have been improved to avoid this issue.

Still, nice contest! C, D, E were all very nice problems, and I might well have liked B if I understood it. F seems above my pay grade (but that's not a bad thing), and I would have liked if A's solution was more interesting (but it's not a bad problem).

Hopefully your next contest will be rated for me.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    I also misread problem B exactly like you.

    And I have a very short solution for that problem.

    Let $$$f_u$$$ be sum xor of all edge's weight that is incident to u. We can see that after operation $$$(u, v)$$$, $$$f_u$$$ and $$$f_v$$$ are swapped.

    So we can prepare multiset of $$$ms_1$$$ of all $$$f_u$$$ in the beginning, and $$$ms_2$$$ of all $$$f_u$$$ in the end. It's "YES" if $$$ms_1 == ms_2$$$ and "NO" otherwise.

    It took me 20 minutes :(

    → Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I have a different approach for task E :

Consider $$$a_i=[(s_{i+1}-s_i)\bmod 3 = 1]$$$. Changing a letter in the middle is equivalent to swapping two consecutive elements in $$$a$$$, and changing the first or the last letter is equivalent to changing the first of the last element in $$$a$$$. It's easy to see that if you changed $$$a_1$$$ from $$$0$$$ to $$$1$$$, you will never change $$$a_1$$$ from $$$1$$$ to $$$0$$$. (However, it could be moved to the end and changed as $$$a_{n-1}$$$, but it seems this could happen only when $$$n\le 3$$$ or all $$$a_i$$$ are equal, though I didn't prove it)

Iterate how many times you changed $$$a_0$$$ from $$$0$$$ to $$$1$$$ (or from $$$1$$$ to $$$0$$$), suppose the number is $$$x$$$. $$$x$$$ should be equal to $$$t_0-s_0$$$ modulo $$$3$$$. For each $$$x$$$ you could calculate the answer in $$$O(n)$$$. It turns out the answer is a convex function of $$$x$$$, thus the minimum can be calculated in $$$O(n\log n)$$$ using ternary search.

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

    How to prove the ternary search?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +17 Vote: I do not like it

      Suppose you got the arrays $$$a$$$ from $$$s$$$ and $$$b$$$ from $$$t$$$, let $$$p_i$$$ is the $$$i$$$-th $$$1$$$ in $$$a$$$, and $$$q_i$$$ is the $$$i$$$-th $$$1$$$ in $$$b$$$. Add infinite $$$0$$$ to at the beginning of $$$p$$$ and $$$q$$$ and infinite $$$n$$$ at the end, then the answer for a given $$$x$$$ is

      $$$ \sum_{i=-\infty}^\infty |p_{i+x}-q_i| $$$

      which is convex. ($$$|x-y|=\sum_v |[x>v]-[y>v]|$$$, so you only need to consider a special case where all numbers are $$$0$$$ or $$$1$$$, where the answer is $$$|x-\mathrm{Constant}|$$$)

      → Reply
»
18 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

In the proof of sufficiency of max limit of number of 1's in Problem C's editorial, I think the claim that if $$$y$$$ was the most frequent at some time then at any later time for any element $$$z$$$ (number of $$$z$$$'s)<=(number of $$$y$$$'s+1) is not correct. Here's an example of the algorithm applied on the array $$$[1,1,2,2,4,4]$$$ with $$$P=5$$$.

Pick any $$$x$$$ having max frequency so I pick $$$1$$$ in the first move. In the second move max frequency occurs for both $$$2$$$ and $$$4$$$ but I choose to let $$$x=4$$$. However $$$1+4$$$ is divisible by $$$5$$$, so I pick $$$y=1$$$ and thus the elements picked by me are $$$1$$$ $$$1$$$ $$$4$$$ in that order.

However now I observe that elements left with me are $$$[2,2,4]$$$, the frequency of $$$2$$$ is $$$2$$$, while frequency of $$$1$$$ is $$$0$$$. But I had picked $$$1$$$ in the first move so the frequency of $$$2$$$($$$=2$$$) should not have exceeded frequency of $$$1+1$$$($$$=1$$$). But this is a contradiction.

If I have understood anything incorrectly in editorial please let me know. I think letting $$$y$$$ to be random if $$$cur+x$$$ is divisible by $$$P$$$ is causing problem.

→ Reply