rng_58's blog

AtCoder Grand Contest 024
By rng_58, history, 7 years ago, In English

AtCoder Grand Contest 024 will be held on Sunday (time). The writer is DEGwer. This contest counts for GP30 scores.

Contest Link

Contest Announcement

Contest duration: 130 minutes

The point values will be 300 — 500 — 700 — 1100 — 1200 — 2300.

Let's discuss problems after the contest.

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

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

5 minutes before the contest start :)

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +30 Vote: I do not like it

I'm getting WA on 3 tests out of 107 in D. Seriously?

UPD: tests 17, 19, 49. What are they? And my answer for N=2 is "1 2", which should be correct.

UPD2: It wasn't a corner case. I was editing the representation of the original graph instead of its copy — now I'm surprised that passed 104 tests instead of ~50 out of 107.

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

What happened to khsoo01 at AGC024?

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

Now this is interesting.

jcvb's only submission in the contest, https://beta.atcoder.jp/contests/agc024/submissions/2540895, submitted 9 seconds before the end of the contest, has been WJ for more than 7 minutes now.

This will determine whether he will get 0 points or 2300 points.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +28 Vote: I do not like it

English translation of editorial for D isn't finished yet.

Also, statement for D should be more clear. I thought that I can only add one vertex to the tree and was like "How could such a pointless problem appear in Grand Contest?".

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

    I thought so too, which is why I asked for clarification.

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

    We will construct a new tree T by "repeating" the following operation, but was it unclear?

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

      How many times? N times? N - 1 times? An infinite number of times? Once? Is zero times allowed? Yeah, it's unclear; that's why the standard way to write it is "repeating the operation an arbitrary number of times (including zero)".

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

    You can check last sample, it's impossible to get 12 leafs, after one operation on tree with 8 leafs.

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

Can someone please explain how to do problem C of the contest? The editorial is in Japanese! Thanks :)

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

    Sorry, we'll add English A-D later.

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

      Added full editorial. Sorry for the delay.

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

    How to solve B? Also, are the test cases visible? Sorry, but I am new to the site

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

      You have to find the longest subsequence of consecutive values (values are consecutive, not their location in the array). When you move all the elements that are not in this subsequence to either the beginning or end, they will "bubble" together. For example, say the array was 2 5 3 1 4. Then, 2 _ 3 _ 4 is the longest such sequence. If we move 1 to the beginning and 5 to the end, then the sequence will come together and we will have 1 2 3 4 5.

      We simply find the length of this sequence and subtract the length from n.

      Code
      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Note that if ai > ai - 1 + 1, then it is impossible (this follows from the fact that after any operation on an element, that element can never decrease, and at some point for nonzero ai, ai - 1 needed to be equal to ai - 1. Also, if ai > 0 or generally if ai > i - 1, it is impossible, since those are the maximum values those elements can achieve.

    Then, we see that for any contiguous segment of increasing numbers, the minimum number of operations needed to get that segment is equal to the highest value in the segment (i.e. if your segment is 0 1 2 3, you need 3 operations to get to that. If your segment is 3 4 5, you will have needed 5 operations, regardless of what the values before 3 are). Thus, for each contiguous segment with increasing values, we can add the highest value of the segment to our answer.

    Code
    → Reply
»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Very sad :(

https://beta.atcoder.jp/contests/agc024/submissions?f.Task=agc024_f&f.Language=&f.Status=&f.User=Benq

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

Thanks for another great contest!

Could you also update https://docs.google.com/spreadsheets/d/1T-hKu_vIh8l4EiW6XTWOvP0evzsWj0f45JNNgou21Cc/edit#gid=695896678 with AGC 023 and AGC 024?

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

What is the expected solution for Problem C?

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

Just want to say that AtCoder is quickly becoming one of my favorite platforms because you all manage to make really good problems without a reliance on advanced data structure/algorithm knowledge, but rather with a reliance on thinking cleverly. This contest was obviously quite difficult (as all AGC's are), but I think from reading the editorial that the most advanced algorithm concepts were DP and finding the diameter of a tree, which are covered in like basic algorithm/data structure classes. That is very impressive.

→ Reply