A shift week

The Dec 22 - Dec 29 week wrapped up the competitive 2025 on the major platforms. The 4th Universal Cup. Stage 10: Grand Prix of Wrocław took place on Saturday (problems, results, top 5 on the left, onsite results, analysis). Team USA1 were not the first to finish, but they were still the fastest overall, and extended their streak of 8 (!) won rounds in a row. Well done!

Codeforces Good Bye 2025 followed the same day (problems, results, top 5 on the left, analysis). While the round lasted 3 hours, the top three needed just two of those to solve all problems. Similar to the above round, being first to finish did not mean first place, though, as Benq was a bit slower on the medium problems and therefore jiangly could overtake him. Congratulations!

I have enjoyed solving the problems and was making good progress, but it was nowhere near as fast, as problem F by itself took me over an hour of iterations, stress testing etc. 

AtCoder Grand Contest 076 took place on Sunday (problems, results, top 5 on the left, analysis). It turns out that it was indeed possible to qualify for AWTF with a win after a relatively poor season, only it was noimi and not myself who has achieved that feat. Well done!

Quite unsually for an AGC I was able to solve A very quickly, but did not score any points after that. In problem B, I have empirically discovered that the answer is always 1 or 2, but could not figure out a condition to separate those two cases, not to mention the actual sequence of steps to achieve that number. In problem C my incorrect solutions were quite close to the one described in the editorial by the idea, but not close enough by the details. At the end of the contest, I have tried to solve E as a heuristic problem, trying various greedy approaches with local optimizations on top, also without much success. Well, better luck next year!

Here is that heuristic-inviting problem E: you are given at most 250000 vectors, and need to choose a subset that maximizes the value of (squared length of the sum of the chosen vectors) minus three times (sum of squared lengths of the chosen vectors). Can you find an exact solution?

This round wrapped up the race for the 2026 World Tour Finals (results, top 12 on the left). Everyone with >=100 points qualified, but people had wildly different ways to achieve that amount of points, with some qualifying thanks to a round victory, and some never placing higher than fourth in any particular round. I'm looking forward to yet another exciting final in Japan!

It is also notable that some usual suspects did not qualify this time, including zhoukangyang who was first and first in qualification in the previous two seasons, and first and second in the last two World Tour Finals. Better luck next year as well!

In my previous summary, I have mentioned another AtCoder problem: you are given two sequences of integers a_i and b_i of the same length n up to 2*10⁵, 1<=a_i<=10⁹, 0<=b_i<=30. We will permute the sequence a_i arbitrarily, and then compute sum(a_i>>b_i), where >> denotes the bitwise shift right. How many of the n! permutations yield the smallest possible value of that sum? You need to print the answer modulo 998244353.

First, let us sort both arrays, so we can assume they are sorted below. Intuitively, it feels that all permutations of a_i that deliver the minimum must be sorted or almost sorted. To make further progress, we can either implement a brute force approach to find out experimentally what does almost mean exactly, or make the intuitive argument more formal, with the same goal.

Suppose we have only two elements. If a₀ = a₁ or b₀ = b₁, then they can be swapped freely without changing our target value. Now consider the case when they are distinct: a₀ < a₁ and b₀ < b₁. When is it OK to swap them?

Since we're going to shift right by at least b₀, it makes sense to introduce p = a₀ >> b₀, q = a₁ >> b₀, and r = b₁ - b₀. Then we need the following to be true: p + q >> r = q + p >> r, which is equivalent to q - p = q >> r - p >> r.

What happens to the difference of two numbers if we cut their last bit? It is not hard to check that it stays the same in only one case: if the bigger number was even, and exactly 1 higher than the smaller number. In all other cases it becomes smaller. So for the above condition to be true, we need q = p + 1 and q divisible by 2^r. These are the only cases where two distinct numbers can be swapped without increasing our target value.

Now we will consider our arrays in blocks of equal b_i. Consider the first such block: b₀ = b₁ = ... = b_k-1 = 0, b_k > 0.

Denote x = a_k if a_k is even, and a_k + 1 otherwise. Therefore x is always even. From the above argument, the only swaps we can do between this block and the rest of the array is swapping the values x-1 from the block with the values x outside the block.

Let us denote c as the number of i such that a_i = x - 1 and i < k, d as the number of i such that a_i = x - 1 and i >= k, e as the number of i such that a_i = x and i < k, f as the number of i such that a_i = x and i >= k. Note that we always have either d = 0, or e = 0, or both.

Suppose we decided to do g swaps of the above form (x - 1 from the block with x from the rest). Then we have (c + d choose c - g) ways to choose which values x - 1 go inside the block, (e + f choose e + g) ways to choose which values x go inside the block, and (k factorial) ways to permute the values inside the block. We need to multiply those three numbers by the answer for the remaining subproblem, which is considering the arrays starting from the position k, such that g values of x have been replaced with x - 1, and we must make sure that those replaced values all end up in the next r blocks, where r is the number of 0s at the end of the binary representation of x.

Now, what happens when we consider the next block, the one where b_i = 1? We can now shift all values a_i right by 1, and denote y = x >> 1 (remember that x is even), and now we can handle this block in the same way we handled the block with b_i = 0. The only difference is that now we have the additional complexity that g values of y have been replaced with y - 1. Let us define z in the same way as x was defined above, as the "swap value" between this new block and the rest, and suppose we decide to do h swaps of z - 1 from the block with z from the rest.

We now have the following four cases:

• y < z - 1. This means that all values of y - 1 must go in this block, so they are not special anymore, and we can just sum up the number of ways over all values of g to get a single multiplier, and then solve this block exactly like the first block.
• y = z - 1. Here all values of y - 1 also must go in this block, but additionally g of the values of y (= z - 1) are no longer available for swapping forwards since they were already swapped backwards, so we need to subtract g from the number of occurrences of z - 1 in the block before computing the above combination numbers.
• y = z. Here g and h refer to the same swaps (z with z - 1), but done over different block boundaries. The number of occurrences of z and z - 1 within the block (which are again used to compute the above combination numbers) will therefore depend on the difference between g and h (and we need to be careful to make sure h can be smaller than g, too).
• y > z. Initially I thought this was impossible, but then an assertion failed in my solution :) And indeed, if in the first block the first value of the rest was 5, we'd get x = 6 and therefore y = 3; if the next block still had 5 after it, but now after the right shift we get z = 2. After some thinking I realized that this case means that we have no place to put the values of y - 1 without violating the restrictions, therefore we must only consider the value for g = 0 for the previous block.

This finally gives rise to a polynomial dynamic programming solution. The state of this dynamic programming will be the bit number that is being considered (the value that we have already shifted all a_i right by, or alternatively the next value of b_i to consider), and the number g of the swaps through the previous block boundary. Note that the other important values, such as the value of y that participated in those swaps, or the position k of the block, are uniquely determined by the state, and therefore do not need to be part of the state. And if we loop over the bit number on the outside, our dynamic programming array can be just one-dimensional. This solution has O(n) states in total over all bits, but each transition can also be O(n), therefore it is quadratic, and indeed it gets TLE.

However, the dynamic programming transition here is summation after multiplying by a combination number, which when expressed via factorials ends up being a product/fraction of factorials of g, h, and either g + h in the y = z - 1 case, or of g - h in the y = z case, and for that we have a trick that was described in this blog 9+ years ago: we can use fast polynomial multiplication via FFT, while using (const - g) and (g + h) as the monomial degrees in the y = z - 1 case to get (const + h) in the product, and using g and (const + h - g) as the monomial degrees in the y = z case to get (const + h) in the product. This gives us an O(n * log(n) * num_bits) solution, which is fast enough. You can check the linked solution for the implementation details.

Thanks for reading, and check back soon for more catch-up summaries and EUC 2026 reports :)

EUC 2026 first day

Yesterday I have arrived in Warsaw, which will host ICPC EUC 2026 this Sunday. As you can see on the left, Warsaw in Feburary (much like Wijk aan Zee in January) is very conductive for indoor activities, which is perfect to be able to truly focus on a programming competition.

I have arrived too late to get to the opening ceremony, but from the slides that were shared it seems that, among other things, Bill has announced the dates for the upcoming ICPC World Finals: November 15-20, 2026 in Dubai (which was already announced before), and September 14-19, 2027 in a yet undisclosed (but seemingly known to the ICPC organizers) location. The ICPC EUC 2027 location was announced last year to be Eindhoven, Netherlands.

But for now the focus is on the upcoming championship, where 8 teams have already qualified for the Dubai World Finals from the various ERCs and are just competing for fun and glory, while ~8 more teams will qualify tomorrow. Best of luck!