## Sunday, August 13, 2023

AtCoder Grand Contest 064 was the main event of the week (problems, results, top 5 on the left, analysis, my screencast, race standings). apiad's usual strategy worked spectacularly well this time, as after spending two hours on E he was able to solve just enough easier problems to win the round, while those who started with the four easier problems did not have two hours remaining for E and could not figure out all details. Congratulatons on the victory!

I was one of those starting with the four easier problems. Somewhat unexpectedly, I did not get stuck in them and did actually have a bit more than an hour remaining for E, and made some significant progress on paper: I realized that if the sum of all ai is zero, and the sum of all bj is zero, and we can place the n2 negated sums -(ai+bj) in the matrix in such a way that every column and row has exactly one of each ai and bj, then the sum of the 2n-1 cells in a cross, which is the sum of the row plus the sum of the column minus the middle cell, will be exactly ai+bj. I've then realized that if the sum of all ai plus the sum of all bj is divisible by 2n-1, then we can get both of those sums equal to zero with some constant shifts. Finally, I've correctly hypothesized that in case it's not divisible by 2n-1, then we can only achieve score n2-1, and figured out how to do so with some more constant shifts for the first row and the first column.

Therefore the only remaining step was to place the n2 negated sums -(ai+bj) in the matrix in such a way that every column and row has exactly one of each ai and bj. This does not depend on the values of a and b, so this simply needs to be done once for every n. It seemed quite doable as it felt like a more advanced derangement, and derangements are quite dense. I've tried some random placements and noticed that I can find such a placement for odd n, but not for even n. And this is pretty much how far I've got in an hour :)

Judging from the editorial (which I do not understand), it seems that for even n we need to use more degrees of freedom, therefore while I enjoyed coming up with my approach, I needed another huge step to finish the solution, and therefore needed at least another hour.

I found problem B to be a cute test of how well one understands the spanning tree mechanics (it is amazing how many nice problems can be derived from a relatively simple concept of a spanning tree, and the fact that it can be found greedily!): you are given a connected graph where each edge is either red or blue, and each vertex is also either red or blue. You need to find a spanning tree in this graph such that for each vertex it has at least one adjacent edge of the same color as the vertex, or report that there isn't any. Can you see a way to do it?

Thanks for reading, and check back next week!

1. Haha I was a little surprised to see the title.

For problem E, it is called Euler square, or orthogonal Latin square, and I have some knowledge about them. But it didn't help me too much, since for n=6, it is impossible to construct.

I've noticed some key points in the editorial, but I implemented a heuristic algo during the contest. I construct a Latin square with the correct row sum and randomly swap two elements in the same row to make more correct col sum. And it worked very well. I think it will not be too hard for experienced solvers like you to come up with that if more time is given haha.

1. Well, I try to not repeat the titles, so I had a dilemma: is "A too difficult week" (https://petr-mitrichev.blogspot.com/2018/11/a-too-difficult-week.html) a repeat? Once again congrats! :)

Could you elaborate a bit on your approach? What does correct col sum mean in the context of this problem - do you still reduce the problem to making all row and column sums equal to zero?

2. Looking at your code (https://atcoder.jp/contests/agc064/submissions/44567159), it seems that divisibility by n-1 is involved in some way, which is also what the editorial does for even n, so it seems I still needed to figure that out in addition to coming up with the random swaps :)

3. In my approach, since the equation system is full rank. So if you fixed the cross sum of each cell, it has a unique solution. You can write down these equations and do some arithmetic manipulations, you can reduce the problem to the following problem.

Assign a[i] + b[j] (1 ≤ i, j ≤ n) into a n x n square such that for each row, and each column, the sum mod (n - 1) = sum(a[i] + b[i]). (The main reason is we need to divide n - 1 in the formula, we need these conditions to ensure an integer solution. )

So the direct approach is to construct an Euler square I mentioned. But I can't find an easy approach for 4k+2, and it's impossible to construct for n = 6. The key point I noticed is there must be two elements a[i], a[j] that are equal mod (n - 1). But I didn't come up with a clever construction.

But in my approach, I construct a square f[i][j] = a[i] + b[(i + j) mod n]. So for each column, it's just two permutations of a and b. It meets the condition. But for each row, it's incorrect. So we can randomly swap two elements in one column to make more and more rows satisfy the condition.