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

D

What is solution for B?

How to solve C?

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

How to solve A?

F is K from this year GP of Xian?

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

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

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.

when will the English editorial be released?

[Deleted]