Блог пользователя maroonrk

Автор maroonrk, история, 23 месяца назад, По-английски

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.

  • Проголосовать: нравится
  • +224
  • Проголосовать: не нравится

»
23 месяца назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Long awaited AGC round and finally the WTF!

»
23 месяца назад, # |
Rev. 4   Проголосовать: нравится +183 Проголосовать: не нравится

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)$$$)

»
23 месяца назад, # |
  Проголосовать: нравится +313 Проголосовать: не нравится

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

»
23 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    23 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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. :/

    • »
      »
      »
      23 месяца назад, # ^ |
      Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

      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)

      • »
        »
        »
        »
        23 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          23 месяца назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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

»
23 месяца назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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...

»
23 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :(

  • »
    »
    23 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    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.

  • »
    »
    23 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
23 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
23 месяца назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

It is rated?

»
23 месяца назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

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.

»
23 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

It is rated?

»
23 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

very nice task E!

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

»
23 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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