### maroonrk's blog

By maroonrk, history, 11 days ago,

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

 » 11 days ago, # |   +29 Long awaited AGC round and finally the WTF!
 » 11 days ago, # | ← 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)$)
 » 11 days ago, # |   +313 Nice, 57th AGC on May 7. I guess 58th AGC will be the next time May 8 is Saturday?
•  » » 10 days ago, # ^ |   +123 That is because they have to solve the problems before asking them.
 » 10 days ago, # |   0 Good luck, and can't wait to see the problems!
•  » » 10 days ago, # ^ |   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. :/
•  » » » 10 days ago, # ^ | ← 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)
•  » » » » 10 days ago, # ^ |   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.
•  » » » » » 9 days ago, # ^ | ← 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
 » 10 days ago, # |   -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...
•  » » 8 days ago, # ^ |   +16 Well,I think it is good of a 1100-Rating player to solve an A int AGC
 » 10 days ago, # |   0 About problem B, I have noticed that if the initial state has max-min= X holds.By the way, during the contest, I contributed about 16 WA to this problem :(
•  » » 10 days ago, # ^ | ← 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.
•  » » 9 days ago, # ^ | ← 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.
 » 10 days ago, # |   0 I solved C in quadratic time. It wasn't even super hard, efficiently written loops + AVX optimisation + one extra trick.
 » 9 days ago, # |   +25 It is rated?
 » 9 days ago, # |   +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.
 » 9 days ago, # |   +8 It is rated?
 » 9 days ago, # |   +10 very nice task E!but what a pity for me to solve it 15min after the contest
 » 9 days ago, # |   0 I thought AGC is unrated for cyans... should've participated