Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### maroonrk's blog

By maroonrk, history, 19 months 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

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