A Kevin week

Codeforces Round 1048 on Monday was the first competition of this week (problems, results, top 5 on the left, analysis). The round was unrated, which has delayed my inevitable downfall: I solved A+B(in the same wrong way as the problemsetters)+C1+C2 in 32 minutes, but could not solve anything else in the remaining 2.5 hours, even though I tried my hand at all remaining problems.

In D, I came up with a cubic solution first, then optimized it to quadratic, and then tried to optimize it to linear for a long time with no success, even though it always felt so close. Imagine my surprise when I reread the problem statement after the contest and learned that n<=5*10³, so I could have just submitted my quadratic solution :) I did submit the solution in upsolving and it passed after fixing two small bugs.

In E, I was trying some randomized approaches, but they were not sophisticated enough to pass. Somehow it was hard to think constructively about determinants, although in retrospect choosing a tridiagonal matrix so that the determinant can be computed in one pass makes perfect sense.

In F, I only opened it in the last hour, and it turns out I almost managed to solve it in time — the code was almost ready during the round, and my solution passed in upsolving after writing just a few more lines and some debugging. I have then uphacked my solution with the case "141 9940 19882", but that won't have mattered during the round :) I am surprised nevertheless that such an extreme case (the case where there is no rounding in the computation of the number of allowed moves and that has the highest polar angle) was not in the system tests.

Kevin, on the other hand, has managed to solve all of those problems (except the proper B :)) during the round. Well done and congratulations on the clear first place!

Wincent DragonByte 2025 Onsite Finals in Bratislava wrapped up the week (problems and analysis, results, top 5 on the left). The top 2 places did not change from the Codeforces round :) Congratulations to all finalists and prize winners!

In my previous summary, I have mentioned an ICPC problem: you are given a graph with 2n vertices and m edges (n<=2*10⁵, m<=4*10⁵), the vertices are split into n pairs that we will call blocks, let us call one vertex in a block red and another blue. Every edge connects a red vertex with a blue vertex. The m edges are added to the initially empty graph one by one. After each edge is added, you need to print the number of pairs of blocks (out of n*(n-1)/2 possibilities) that are connected (there exists a path connecting one of the four possiblities: between the red or the blue vertex in the first block and the red or the blue vertex in the second block).

First, consider the following naive approach. Let us maintain the connected components in the graph, and for each component remember the set of blocks represented in it, which we can update via small-to-large merging. To compute the answer after adding every edge, we will just add up b*(b-1)/2 for each component, where b is the number of different blocks represented in it.

Why is this approach naive? It will overcount in case two blocks are connected in two different connected components. But since each block has only two vertices, the only way this can really happen is that there are two components, each containing one vertex from each of the blocks. And moreover, we will overcount by exactly 1 for each pair of blocks with this property.

So let us also store the inverse mapping: for every block, we store the set of components it has representatives in. We can maintain those together with the above sets. Those sets will always have 1 or 2 elements. For those that have 2 elements, for each group of c equal such sets we need to just subtract c*(c-1)/2 from the answer. We can maintain the current answer and update it when those sets change.

This solution, by the way, is also by Kevin. Thanks for reading, and check back next week!