An apiad week

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 a_i is zero, and the sum of all b_j is zero, and we can place the n² negated sums -(a_i+b_j) in the matrix in such a way that every column and row has exactly one of each a_i and b_j, 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 a_i+b_j. I've then realized that if the sum of all a_i plus the sum of all b_j 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 n²-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 n² negated sums -(a_i+b_j) in the matrix in such a way that every column and row has exactly one of each a_i and b_j. 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!