rng_58's blog

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

AtCoder Grand Contest 012 will be held on Saturday (time). The writer is camypaper.

Contest Link

Contest Announcement

The point values are 300 — 700(200) — 1000 — 1000 — 1000 — 2000.

Let's discuss problems after the contest.

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

Comments Comments (35)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry, but what does 700(200) mean? Is it partial score?

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

    Yes

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

    I actually forget every time what it means. It means 700+200 or 500+200?

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

      It is 200+500, aka you get a total of 200 for solving the subtask, and a total of 700 for solving the whole task.

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

Do you get time penalty (for a wrong submission) towards 700 if you solve only 200?

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

Will we have editorials in english this time ?

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

    There has always been English editorials for all Atcoder Grand Contests.

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

gonna participate this one after months of blank

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

Wow! japan server near my country which is Philippines, meaning I dont have to stay up late at night when participating in contests :)

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

I give up... I know Grand Contests are usually very difficult, but today contest seems only made for red guy on Codeforces...

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

    Tasks weren't that hard in my opinion, at least implementation was easy. They required more thinking instead of coding.

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

      That's kind of how most Atcoder problems are; not tedious to implement but hard to solve.

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

      After I read the editorial for problem B to E, problem seems easier than I thought.

      I think I need to practice more on contest like this to improve my thinking skill.

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

That moment when you're ~2 minutes from getting AC (on D) T_T

Never forget the line 

if(u == v) return ;

in the merge function of DSU again T_T

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

Thanks for the fun problemset! I thought today had some interesting challenges. Even though I only solved A,C,D I think the solution to problem B and E are also very nice and are my favorite problems today.

Personally, I am still kicking myself for not seeing the solution to C quickly enough, but what can you do.

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

why e 1000pt TTTT

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

    It is because of all the silly people like me who do not know how to use bitmask dp. (for example, IOI p2 subtask 2)

    EDIT: Oops. Since you solved E I assumed you meant it was easy.

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

      Well I thought it deserved more points :p I had both hard time figuring it out and implementing it. I think problem D is super easier than E (I read it after contest)

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

Don't miss square869120Contest #4 on April 9th on atcoder!!!
https://s8pc-4.contest.atcoder.jp/

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

    Is there any reason why you don't make these rounds part of atcoder regular/grand contests?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. This contest's concept is "Enjoyable for every people", so there are many partial points (JOI / IOI — style) for easy or medium-level competitive programmers for avoding "only sitting last 3-hours and can't do anything".
      2. This contest has a marathon / approximate (?) problem in the last problem, so it is not usual for ARC / AGC.
      → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I thought it was the most difficult AGC ever. (but with really nice problems)

Maybe it's because I'm so naive

and my rating -= 1

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

Is there anyone who solved B for full points in other way than mentioned in the editorial???

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

    I did (well upsolved, I couldn't participate in the contest). I know your question is pretty old but I thought that you might find the answer useful in some way. I just kept some sort of dp: lst[i][j] = the id of the last operation that affected the node j in such a way that j, at its turn, would affect the nodes at distance i from itself. The recurrence is something like update for each (i, u), lst[i — 1][v] for each v such that v is a neighbour of u with lst[i][u]. You could check out my source for more details: http://agc012.contest.atcoder.jp/submissions/1452611

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

      Thanks I still had not upsolved the question .Editorial was tough for me. I will try to solve with the help of your approach :)

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

Thank you for your participation! We're sorry for score of problem E (we thought this problem was easier than other AGC E).

Could you enjoy my problems? I strongly recommend to try problem F. I think it's REALLY interesting and beautiful problem!!

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

    Thanks for the very nice problem set. I tried to solve F, understood the part in the editorial saying "there is no (i, j) pair with i < j, and bj < bi < bj + 1", but I am stuck at how to go from there to the dynamic programming solution dp[i][j][k], where i is the number of values filled from the end, j is the number of candidates, and the k-th candidate is chosen. Could someone elaborate on this part ?

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

      Ok, finally got it: j is the number of candidates for the next element.
      ainta's submission matches the explanation of the editorial.

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

Can anyone explain why in the editorial of D, we are taking two minimums a1 and a2. Thanks.

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

    It is the critical point that a1's color is different from a2's color.

    Basically, we can use a1 to change the position of balls. However we have to use a2 to change the position of balls which color are the same of a1. We don't need to use the other balls in operation2. Because the other balls' weight are heavyier than a1 and a2.

    Could you got it?

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

    Here is an alternative solution, which also explains that:

    1. For each color, get the minimum value and replace every weight with minimum if min + original_weight <= X (it means that you can replace the balls within the same color).
    2. Sort such pairs (new_weight, color).
    3. Generally you should be able to permute all the balls such that: new_weight_i + min_new_weight <= Y. The rest stays the same. The only exception are such balls where color_i == color_of_min_new_weight, which can't be replaced because sum of their weights > X. The only way to move such a ball is to use the smallest new_weight with a different color. That's why you need second_min_new_weight and if sum of their weights <= Y, you can move such a ball, otherwise it must stay at original position.
    4. You get all movable balls of size n, you count n! and divide it by factorial of the count of the colors included in movable balls set: n!/(k1!k2!..ki!)
    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the intuition behind the trick used in the solution to problem C ?

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

    When I started to think this problem, the definition of good string is different from current definition. The condition is like this: x can be represented as yyzz (not yy).

    Under this constraints, it is tough to use a character three times. Thus, I came up with this approach.

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

. Ignore — understood from the image.

→ Reply