maroonrk's blog

AtCoder Grand Contest 077 Announcement
By maroonrk, history, 2 months ago, In English

We will hold AtCoder Grand Contest 077. This contest counts for GP30 scores.

Starting with this AGC, submitting a recording will be required in order to earn a GP30 score. Click here for details.

The point values will be 800-900-1000-1000-1000-1800.

We are looking forward to your participation!

UPD: GP30 Ranking was updated (link).

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

»
2 months ago, hide # |
 
Vote: I like it +62 Vote: I do not like it

We can see that C seems easier than B for Chinese participants, since most Chinese participants recently met such a problem: Given a undirected complete graph with 0/1 on each edge, you can choose a subset with size $$$k(2\le k\le n-2)$$$ and flip all the number on edges inside the subset, find the max number of 1s you can get. If solved that problem, determing whether a graph is reachable in this problem will be easy.

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +94 Vote: I do not like it

Thank you for participating!

I was the writer for Problems B, D, and E.

My favorite is Problem E. The intended solution for E is very interesting.

I’m looking forward to your upsolving!

→ Reply
  • »
    »
    2 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +31 Vote: I do not like it

    I really liked problem E (a bit sad the contest was unrated for me). Even though my construction isn't as beautiful as the one in the editorial, it still felt rather simple.

    At first, I was struggling with constructions similar to this:

    111...1111
111...1111
100...0000
000...0000

    I couldn't get the $$$n = 499$$$ solution to be a cycle, it always turned out as a path. Then, I added four 1s so that the path could link back into a cycle:

    111...1111
111...1111
100...0011
000...0011

    I wonder if $$$999975$$$ is the upper bound for $$$N$$$.

    → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +5 Vote: I do not like it

      I had the same construction and was not able to solve the $$$N=499$$$ case (the fix with the four extra 1s is very nice).

      I brute forced this construction for $$$W \leq 11$$$:

      111...111
111...111
100...000
000000000

      and for $$$5 \leq W \leq 11$$$ it is possible possible to achieve all values $$$0 \leq N \leq (2W-1)(2W+1)$$$, so i think that for $$$W=500$$$ all values $$$0 \leq N \leq 999\,999$$$ are possible, but I don't know how.

      → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
       
      Vote: I like it +5 Vote: I do not like it

      Congrats! Really glad you solved my problem during the contest!

      → Reply
»
2 months ago, hide # |
 
Vote: I like it +76 Vote: I do not like it

Thanks for participating, hope you enjoyed the round! I'm the setter for A, C, and F. E and F are my absolute favorites, so I highly recommend checking them out!

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply