maroonrk's blog

AtCoder Grand Contest 057 Announcement
By maroonrk, history, 3 years ago, In English

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

The point values will be 400-700-1100-1100-1400-1800.

We are looking forward to your participation!

This is the first contest in the 2022 season that counts for the GP30 race. We are planning to invite top runners of the race to WTF 2023, but we still haven't decided on the details of the Finals. We will closely watch the domestic and international situations and consider when and how to hold the Finals. We are also trying to find a way to hold unfinished WTF 2020, 2021, and 2022.

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

»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Long awaited AGC round and finally the WTF!

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

As a 2800-rated on CF, I have never solved any C of AGC during contest.

upd: This time I went for D. I think editorial of D is not detailed enough :( I have come up with everything in the editorial during the contest, but failed to find an $$$O(d^3)$$$ per testcase solution with it (My solution runs in $$$O(d^4\log n)$$$)

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

Nice, 57th AGC on May 7. I guess 58th AGC will be the next time May 8 is Saturday?

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

    That is because they have to solve the problems before asking them.

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

Good luck, and can't wait to see the problems!

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

    Well, no luck for me.

    Giving up after fiddling two hours on A... and even dont find a counterexample for my code, but still have only 1/42 green. :/

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

      Probably you did not break into cases where first digit of upper bound is 1 and it is not. After you do that the problem becomes trivial

      (I say trivial but I still spent forever solving it, so don't listen to my difficulty estimations)

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

        After reading the editorial: Actually I got the right idea, and implemented that binary search.

        But I did not get the formular for f() right, considering that the case prefix and postfix. I somehow tried to mix them up, or ignored the half of it.

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

          I didn't use binary search — instead choosing to approach the problem the other way. After noting that for any [l,r] we can always pick some suffix, I noticed that for r, if the first digit is 1 then the lower bound is max(l,r%(10^digits of r — 1) + 1, r/10 + 1).

          Otherwise the lower bound is just max(l, 10^(digits in r — 1) + 1).

          https://atcoder.jp/contests/agc057/submissions/31492475

          → Reply
»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

O.M.G. It has been my first time to take part in AGC (only a 1100-rating on Atcoder). I just wanna take it easy because i've imagined how difficult the AGC would be. But actually more difficult than I thought! I only solved A of AGC and still came up with no ideas to solve B. SOS...

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

    Well,I think it is good of a 1100-Rating player to solve an A int AGC

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

About problem B, I have noticed that if the initial state has max-min<x, then the answer is 0.

Next, I keep the maximum value unchanged, and do as the editorial says, "When there is a term on which no operation is performed", and obtain the value Y, and just output Y as the final answer.

Now I have realized that I missed "[2]The full solution" part. But I still don't understand why it is Y if Y >= X holds.

By the way, during the contest, I contributed about 16 WA to this problem :(

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

    Suppose you change every value, and $$$\text{max} - \text{min} \geq x$$$. Then, if you undo exactly one operation for each value, $$$\text{max} - \text{min}$$$ doesn't increase. So it's optimal to never change one of the values. That value is the maximum.

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

    My understanding for the editorial:

    Let's define a bulk operation to be an operation which changes each value at most once. If in a bulk operation the maximum value ($$$max$$$) is changed, it does not make sense to fix any other value, e.g., changing the other value $$$v$$$ to $$$2\cdot v$$$ will never make the answer worse.

    On the other hand, changing all the values in a bulk operation can decrease the answer only if $$$max - min$$$ is $$$< X$$$.

    So, our goal is to decrease $$$max - min$$$ as much as we can through the bulk operations where $$$max$$$ is not changed.

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

I solved C in quadratic time. It wasn't even super hard, efficiently written loops + AVX optimisation + one extra trick.

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

It is rated?

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

I used another idea for problem $$$B$$$ — two pointers. The complexity is $$$O(n \cdot log{n} \cdot log{C})$$$.

Look at element $$$y$$$ of array. Let $$$S_i$$$ are sets of values, that can have this element after $$$i$$$ operations. That is $$$S_0 = {y}, S_1 = [2 \cdot y, 2 \cdot y + x]$$$. We can prove by induction, that it is always some segment $$$[l_i, r_i] \forall i$$$. Let's calculate all these segments up to $$$10^{18}$$$.

Now we have the problem: for all $$$i \in [1, n]$$$ we have set of segments, they can overlap. We have to find the smallest segment $$$[l, r]$$$ such that for any $$$i \in [1, n]$$$ at least one corresponding segment intersects with it. This can be done using two pointers in linear time.

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

It is rated?

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

very nice task E!

but what a pity for me to solve it 15min after the contest

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

I thought AGC is unrated for cyans... should've participated

→ Reply