## Thursday, April 18, 2024

### ICPC World Finals Luxor mirror stream

## Thursday, February 15, 2024

### A NWERC week

Team "nwerc is bad" from the Univerity of Oxford also reminded that they are one of the favorites for one of the upcoming World Finals in Luxor by earning an excellent fourth place and being the best ICPC-active team this time. Well done!

Thanks for reading, and check back next week for more meaningful content :)

## Wednesday, February 7, 2024

### A Delft week

## Wednesday, January 31, 2024

### A stable denominator week

*k*-th roots of a specific permutation, and it took the winner SSRS_ just 3.5 minutes since they reused their submission for a more general problem about counting

*k*-th roots of any permutation. More generally this problem did not present as much of a challenge for the top participants as the 500-pointer, which saw many solutions fail and therefore offered a lot of challenge opportunities. Of the three contestants who managed to solve everything, kotatsugame was behind after the coding phase but managed to recover to the second place thanks to 200 challenge points. Congratulations to all three on the great performance!The 2nd Universal Cup. Stage 20: Ōokayama followed, as usual, on Saturday (problems, results, top 5 on the left, analysis). 16 problems in a round is still a lot even by today's standards, but this still did not stop team HoMaMaOvO from solving all of them with 6 minutes to spare :) Well done! This is their 7th win of the season compared to 9 for USA1, and they are definitely still in contention for the overall first place.Finally, Codeforces Round 921 wrapped up the competitive week also on Saturday (problems, results, top 5 on the left, analysis). Having dealt with the four easier problems in the first hour, I've decided to focus on problem F since there it seemed that we just need to solve the

*n*=3 case and the rest will easily follow, while problem E gave some generating function vibes :) Unfortunately even the

*n*=3 case in F turned out too hard for me. I have even implemented a brute force that tried different random strategies and it still could not solve

*n*=3. The reason for that was probably the fact that the strategies I tried were non-adaptive: they asked the same questions irrespective of the answers.

*x*,

*y*) or not, the number of choices affecting this outcome is always

*x*+

*y*, no matter the current state, so we can compute the probability of such visit happening very nicely.

*n*

^{2}) to O(

*n**log

*n*), and luckily I managed to do it before the end of the round. This was of course still not enough to compete with jiangly and others who focused on problem E earlier. Congratulations on the win!

## Sunday, January 21, 2024

### A Frobenius week

## Friday, January 19, 2024

### A HoMaMaOvO week

^{5}.

The key observation in this problem is to imagine that we are building our tree step by step. Initially, we have only the root, which is also a leaf, so the sequence printed will be just 0. Now we add two children to the root, using edges with weights 0 and 1, and the depth-first search traverses them in some order. Depending on this order, the sequence we get will become either 0 1 or 1 0. We continue by repeatedly taking a leaf and adding two children to it, and the sequence always changes in the following manner: if the number corresponding to this leaf was *x*, then we insert *x*+1 into this sequence either directly to the left or directly to the right of it. And we can apply this operation to any number in the sequence, so we just need to check if the sequence we are given can be obtained starting from just the number 0 using this operation repeatedly.

Now let us look at the process in reverse, in other words we will repeatedly remove numbers that are adjacent to a number smaller by 1 until only 0 is left. What should we remove first? All numbers in this sequence that are adjacent to a number smaller by 1 are candidates. Now consider what happens when we remove number *x* that was adjacent to *x*-1: now *x*-1 becomes adjacent to some other number *y*. When *y*=*x*-2, the number *x*-1 become a candidate. When *y*=*x*, the number *y* becomes a candidate. In all other cases, no new candidates appear. This means that the new appearing candidates are never bigger than the number being removed.

Therefore we can safely remove any of the candidates with the highest value: we will never get candidates with even higher value in the future because of the previous argument, therefore those numbers themselves will never be useful to support removal of another number. So we can just keep removing one of the remaining highest values while it is possible, and we either reach a single 0, in which case we have found a solution, or we get stuck when all remaining highest values cannot be removed, in which case there is no solution.

Thanks for reading, and check back for more!

## Sunday, January 7, 2024

### A 1:1 week

^{5}.

*n*=1000 (note that it is not

*n*<=1000, but exactly

*n*=1000) vertices, and 2000<=

*m*<=5000 edges. It is guaranteed that this graph was generated randomly by adding a uniformly random non-existing edge

*m*times. You can make at most 5 changes to this graph, where one change is adding an edge between two vertices not connected by an edge, or removing an edge. The first run of your program ends there. The graph with your changes applied is then shuffled (randomly permute vertices, edges, and ends of an edge), and is given as input to the second run of your program. The trick is that your program is not told whether it is the first run or the second run, and instead needs to detect it itself. In other words, you need to apply such changes in the first run that you'd be able to detect that the graph was changed from a random one in the second run.

*m*), and this will incorrectly work on the first run with probability one in 10000, which is tolerable as the problem likely has on the order of 100 testcases.