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

- Contest URL: https://atcoder.jp/contests/agc037
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20190817T2100&p1=248
- Duration: TBD (around 2 hours)
- Number of Tasks: 6
- Writer: yutaka1999
- Rated range: All

The point values will be announced later.

We are looking forward to your participation!

I really hope rounds would be announced a bit earlier in the future. Otherwise keep up the great work you are doing :)

Usually I announce it around 24 hours before the match. What time is the best do you think?

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

I think the contest was listed on the website for at least 48 hours now.

And 72 hour notice is a bit too short, that's all I am saying

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.

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

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.

D

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.

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.

D was also on one of the Polish onsite competitions...

What is solution for B?

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

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.

Yikes. Big oof. /twitter

This seems harder than A, C, D or E to me.

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?

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.

How to solve C?

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.

Why is it true ? How can you prove that ? I did the same but I picked any element not largest.

As all the elements are positive your last operation would have made the element largest in his vicinity. Therefore going backwards works.

Ok thanks.

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.It should be just >= a[i].

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

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

Slightly late but D by sufficiently random but sufficiently smart swaps.

How to solve A?

In optimal solution partition can only be of length 1 or 2. Do DP on it.

DP is not necessary actually.

F is K from this year GP of Xian?

It looks similar. But I think the solutions are quite different.

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.

What's the definition from Opencup?

$$$m$$$ in the definition is 2.

English editorial will be posted later, sorry.

I think this is an $$$O(n^2)$$$ solution for C: https://atcoder.jp/contests/agc037/submissions/6965165

Orz

i don't understand a guide for problem A if string is 'aa' then s[i]=s[i+1]

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.

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.

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 smh

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

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

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.

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:

This is the generator:

generator.pyIn my PC it runs in over 40 seconds. This solution just got lucky.

when will the English editorial be released?

Added DEF, I'll add ABC on Tuesday. EDIT: ABC added too.

[Deleted]