### rng_58's blog

By rng_58, history, 22 months ago,

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

The point values will be announced later.

We are looking forward to your participation!

• +142

 » 22 months ago, # |   +90 I really hope rounds would be announced a bit earlier in the future. Otherwise keep up the great work you are doing :)
•  » » 22 months ago, # ^ |   +18 Usually I announce it around 24 hours before the match. What time is the best do you think?
•  » » » 22 months ago, # ^ |   +52 I mean not announcement per se. This match was not on the calendar right until today, I think, and I like to play my week in advance
•  » » » » 22 months ago, # ^ |   +9 I think the contest was listed on the website for at least 48 hours now.
•  » » » » » 22 months ago, # ^ |   +73 And 72 hour notice is a bit too short, that's all I am saying
•  » » » » » 22 months ago, # ^ |   0 I know I checked the website "a few days ago" and there was nothing. Very different timeframes can feel like a few days. People are sometimes very busy during the week and don't think about checking if there will be a contest on the weekend, it's happened to me a few times.Something like a 6-day notice is reasonable. Not an announcement, but just having the contest on the calendar, so if you check it approximately once per week, you can always take it into consideration.It doesn't matter when contests are frequent enough that you can always expect one, but Beginner Contests don't count.
•  » » » » » » 22 months ago, # ^ |   +34 Sorry for slow notification... There will be an ARC-equivalent round next Saturday (for sure), and then two AGCs on September I hope (but not quite sure now).
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   0 I dunno if you use the calendars from clist.by (I do), but they were down (not updating for either Atcoder or Codeforces) for the past couple days until today.
 » 22 months ago, # |   +15
•  » » 22 months ago, # ^ |   +23 I struggled for some years now with that problem on Timus and did managed to solve it now. I even skipped it on the round because I recognized it.
•  » » 22 months ago, # ^ |   0 Task on Timus seems much harder, as simple finding matchings one by one does not work. But yes, if you solved that task before it would not be hard to solve D.
•  » » 22 months ago, # ^ |   0 D was also on one of the Polish onsite competitions...
 » 22 months ago, # |   +50 What is solution for B?
•  » » 22 months ago, # ^ | ← Rev. 2 →   +37 greedy i would say. just keep track of 7 states.. count of people having no color, R, G, B, RG, RB and GB. Then if you encounter a color give it to someone who can complete his set.. if not possible then to someone who already has a ball of different color... if still not then give it to a person who is empty.. keep multiplying your answer with the number of people. https://atcoder.jp/contests/agc037/submissions/6957970
•  » » 22 months ago, # ^ |   +25 Consider all subsets of the string "RGB", let's call "RGB" a closed group, and other subsets open, if you loop from left to right and construct the groups, for each letter you will have at most one group of each size where you can add it. If there is a group of size 2 that needs this letter, it is clear that you should add it there and close that group.You can't have two open groups of the same length, like "RG" and "RB", because either "G" or "B" came second and you could have closed one of the groups using it. Also you can't have two groups with a single letter as you could have joined them and minimized the difference, since you will open the second group later.So try to close a group using the current letter, if that's not possible, try to add it to a group with a single letter, if no open group needs this letter, create a new group with it.To count the number of ways, multiply the answer with the frequency of the optimal group, and update the frequencies.
•  » » » 22 months ago, # ^ |   +52 Yikes. Big oof. /twitterThis seems harder than A, C, D or E to me.
•  » » » 22 months ago, # ^ |   +19 this greedy approach gives us the optimal answer, but what is the proof that this covers all the distributions where the final answer comes out to be optimal?
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +3 The way we construct the solution can cover all distributions (non-optimal too) if we try adding each letter to all groups that need it and print all combinations. The fact that each time during the construction we have one optimal option makes our solution cover all optimal distributions. Adding a letter to a different group than the optimal one will result in one of the following: Delaying the end of a group, by opening a new group early or extending another group. Having two open groups while they can be merged into one. In both cases, we have more contribution to the cost than necessary.
 » 22 months ago, # |   +27 How to solve C?
•  » » 22 months ago, # ^ |   +40 Just do reverse process. In each step decrease largest one with two neighbours as much as you can. In one moment you will get first array or it is impossible.
•  » » » 22 months ago, # ^ |   +16 Why is it true ? How can you prove that ? I did the same but I picked any element not largest.
•  » » » » 22 months ago, # ^ |   0 As all the elements are positive your last operation would have made the element largest in his vicinity. Therefore going backwards works.
•  » » » » » 22 months ago, # ^ |   0 Ok thanks.
•  » » » 22 months ago, # ^ |   0 Can you elaborate "as much as you can"? I have decreased it while it is still bigger than max(a[i], b[i - 1], b[i + 1]), but this takes WA.
•  » » » » 22 months ago, # ^ |   0 It should be just >= a[i].
•  » » » » » 22 months ago, # ^ | ← Rev. 3 →   0 Why should this work? (Actually, it doesn't work, If I understood what you said sumbission)And the brute force solution, will be to pick ALWAYS the biggest element in the array. What if we can decrease an element 5 times, but after the first decrease it is not the biggest on the array anymore? Is it still ok to decrease it? This is what I don't understand
•  » » » » » » 22 months ago, # ^ | ← Rev. 3 →   +11 In the reverse process if you decrease B[i] it becomes B[i] — B[i — 1] — B[i + 1] and since all the numbers are positive B[i] > B[i — 1] + B[i + 1]. Since B[i] > B[i — 1] and B[i] > B[i + 1], you can't perform an operation on (i — 1) or (i + 1) so you should decrease B[i] till it becomes equal to A[i] or <= B[i — 1] + B[i + 1].
 » 22 months ago, # |   +10 Slightly late but D by sufficiently random but sufficiently smart swaps.
 » 22 months ago, # | ← Rev. 2 →   +5 How to solve A?
•  » » 22 months ago, # ^ |   0 In optimal solution partition can only be of length 1 or 2. Do DP on it.
•  » » » 22 months ago, # ^ |   +18 DP is not necessary actually.
 » 22 months ago, # |   0 Can anyone please explain solution of A . I couldn't even solved A.
 » 22 months ago, # |   0 F is K from this year GP of Xian?
•  » » 22 months ago, # ^ |   +20 It looks similar. But I think the solutions are quite different.
•  » » » 22 months ago, # ^ |   +18 Actually, the definition of level was originally the same as that problem from opencup :D The admin taught me that it could be solved easily, but I had a different solution, so I changed the definition into the current one.
•  » » » » 22 months ago, # ^ |   0 What's the definition from Opencup?
•  » » » » » 22 months ago, # ^ |   0 $m$ in the definition is 2.
 » 22 months ago, # |   +41 English editorial will be posted later, sorry.
 » 22 months ago, # |   +11 I think this is an $O(n^2)$ solution for C: https://atcoder.jp/contests/agc037/submissions/6965165
•  » » 22 months ago, # ^ |   0 Orz
 » 22 months ago, # |   +6 i don't understand a guide for problem A if string is 'aa' then s[i]=s[i+1]
•  » » 22 months ago, # ^ | ← Rev. 3 →   +9 To my stupidity, I didn't read the problem statement properly. And directly jumped to solving the problem. A life lesson today learnt that never jump to code directly without understanding the problem in hand very clearly and having a working solution in mind.I thought the problem is about finding the maximum partition size of unique substrings of s. And I solved this problem using DP. Only later to realize that is not the case. The actual problem asked is to partition input string into a sequence of substrings such that TWO consecutive partitioned substring should not be equal.So if two consecutive characters are not equal in the input string (you can check with s[i] == s[i+1]) then you can safely partition those two consecutive characters into two substrings of 1 character each, else you have to merge them or count the two as 1.
•  » » » 22 months ago, # ^ |   -8 untill reading ur post , i was in the same illusion...couldn't make the problem in the contest ... now did it.YES it's a life lesson indeed.
 » 22 months ago, # | ← Rev. 4 →   +5 Solution for D:UPD: Lol just realized I've done more work than necessary and I think we can just do the matching thing directly smhMy idea is to solve recursively for subrectangles. First, replace the numbers $a_{i,j}$ by $\lfloor\frac{a_{i,j}-1}{m}\rfloor$. Now, we want to rearrange each row such that each column contains all numbers from $0$ to $n - 1$.WLOG, the top-left corner is 0. Now, move all the 0s to the left of the top row. If all 0s are already present in the top row, recurse on the remaining rows. Otherwise, suppose there are $A$ 0s on the top row. We claim that we can always find $A$ elements from each of the remaining rows such that their union contains $A$ copies of $1, 2, ..., n-1$ each. If we can do that, then we can move all of them to the left and recurse on the left and right part.Construct a bipartite graph with parts $L, R$. $L$ contain $A$ copies of vertices labelled $2$ to $N$, denoting the rows while $R$ contain $c_{i}$ copies of the vertex $i (1 \le i \le N - 1)$, where $c_{i}$ is the number of times $i$ appears among the last $N - 1$ rows. Note that $c_{i} \ge A$ for all $i$ (or else > M — A of them will be in the first row, a contradiction).For each cell from the $i \ge 2$-th row that contains $x \neq 0$, draw an edge from $i$ to $x$ from left to right (for every possible pairs of copies). We can easily see that the condition for Hall's Theorem is satisfied in this graph, so a matching that saturates the left hand side exists. It remains to find this matching using Dinic (we can compress the graph to make it only contain $N - 1$ vertices on each side) and we're done.
 » 22 months ago, # |   +10 My solution to D:In the array after we first order rows, we need to have every column contain exactly one number from every row in the final array. To achieve this, build the columns left to right. Note that if we have chosen which numbers to sort into the first $k$ columns, the remaining subproblem is still the same as it originally was, just with width $w - k$. Therefore, since the problem statement claims the problem can always be solved, it is still solvable. Therefore, we can pick any values for the column such that the column contains at most one value from every row in the original and final array.Selecting some values for the column can be done with a simple bipartite matching, which is guaranteed to have a solution, since otherwise the problem would not be solvable. Let nodes $1, \dots, h$ represent the $h$ different rows we want the values to be from in the final solution, and nodes $h+1, \dots, 2h$ represent the current rows. Add an edge between nodes $i$ and $j + h$ if some value $v$ is currently in row $j$ (and not used up in the first k columns), and in row $i$ in the final solution. Then find the matching, and swap the pairs found to the column you just constructed.Code
 » 22 months ago, # |   +5 I have found a submission of problem C: https://atcoder.jp/contests/agc037/submissions/6962412 This code only uses brute force and it has nothing to do with finding the maximum value.Can anyone explain the strategy behind this code? Thanks.
•  » » 22 months ago, # ^ | ← Rev. 3 →   0 Solutions finding maximum value are equivalent to finding some value $b_i$ that is greater than its neighbors and $a_i$. Maximum value is just an easy way to satisfy such criteria. This solution indeed does that, but it finds such values in $O(n)$. I guess it fails in time the following TC: 100000 1 1 1 ... (100000 ones) ... 1 1 1 1 3 5 ... (first 100000 odd numbers) ... 199995 199997 19999 This is the generator: generator.pyn = 10**5 print(n) print(' '.join(["1"] * n)) print(' '.join(map(str, range(1, 2 * n + 1, 2)))) In my PC it runs in over 40 seconds. This solution just got lucky.
 » 22 months ago, # |   +71 when will the English editorial be released?
•  » » 22 months ago, # ^ | ← Rev. 2 →   +36 Added DEF, I'll add ABC on Tuesday. EDIT: ABC added too.
 » 22 months ago, # | ← Rev. 3 →   +11 [Deleted]