We will hold AtCoder Grand Contest 057. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc057
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220507T2100&p1=248
- Duration: 180 minutes
- Number of Tasks: 6
- Writer: maspy
- Tester: HIR180, tatyam
- Rated range: 1200 -
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.
Long awaited AGC round and finally the WTF!
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)$$$)
Nice, 57th AGC on May 7. I guess 58th AGC will be the next time May 8 is Saturday?
That is because they have to solve the problems before asking them.
Good luck, and can't wait to see the problems!
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. :/
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)
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.
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
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...
Well,I think it is good of a 1100-Rating player to solve an A int AGC
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 :(
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.
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.
I solved C in quadratic time. It wasn't even super hard, efficiently written loops + AVX optimisation + one extra trick.
It is rated?
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.
It is rated?
very nice task E!
but what a pity for me to solve it 15min after the contest
I thought AGC is unrated for cyans... should've participated