antontrygubO_o's blog

By antontrygubO_o, 6 weeks 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
  • +417
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +153 Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +54 Vote: I do not like it

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

»
6 weeks 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?

»
6 weeks 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:

»
6 weeks 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

»
6 weeks ago, # |
  Vote: I like it +61 Vote: I do not like it

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

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

    9, but mostly to fix the difficulty balance

    • »
      »
      »
      6 weeks 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!

      • »
        »
        »
        »
        6 weeks 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.

»
5 weeks 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...

  • »
    »
    5 weeks 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.

»
5 weeks 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!

»
5 weeks 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.

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +173 Vote: I do not like it

Show some mercy, it was so hard ;_;

»
5 weeks ago, # |
  Vote: I like it +80 Vote: I do not like it

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

  • »
    »
    5 weeks 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.

»
5 weeks 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.

  • »
    »
    5 weeks 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 :(

»
5 weeks 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.

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

    How to prove the ternary search?

    • »
      »
      »
      5 weeks 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}|$$$)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B how can we can we say that the weight W is always acheivable after a certain number of operations? Although mathematically it is all fine but can we intuitively deduce that W (equal to xor of all ai's and all bi's as stated in the editorial) can always be acheived?