EUC 2026 contest day

ICPC EUC 2026 starts in about two hours (9:30 Warsaw time, photo on the left from the official gallery). Here are some useful links:

• Official website
• Teams
• Scoreboard
• Problems
• Livestream

Note that these problems will be used for the Universal Cup next weekend, so please don't look at them (and don't watch the livestream I guess?) if you are planning to participate there.

In the other case, do tune in!

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!

A digging week

Codeforces Global Round 31 last Friday wrapped up the 2025 Global Round series (problems, results, top 5 on the left, analysis, serie standings that use the "sum all 3" instead of the actual "sum 2 best out of 3" scoring system). I spent way too much time on implementation and debugging once again, solved A-F1 and then decided not to go for even more standard-ish implementation in F2 and instead tried to get H1 in the end, but could not actually solve it. ecnerwala had roughly the same amount of time as myself for H1 after solving A-G (even the strong version of G), and he did solve H1 as well to claim a clear first place. Well done!

Meta Hacker Cup 2025 held its final, this time online, on Saturday (problems, results, top 5 on the left). Gennady has won his 6th Hacker Cup, and it was not easy: he scored 44 out of his 71 points in the last hour, and Yui could still have snatched the first place were her last-second submission in C1 correct. Congratulations to both! Looking at the scoreboard of this contest, it feels sad that all other contests have abandoned the system test concept and no longer reward writing good code and testing it before submission as much.

AtCoder is wrapping up the year with two last chances to qualify for AWTF 2026, the first of which was Grand Contest 075 (problems, results, top 5 on the left, analysis, serie standings). In problem A, I was looking for an algorithmic solution, trying hard to find some sort of knapsack subproblem with slowly increasing weights that can be solved by greedy or backtracking. However, it seems that this was a dead end, and one had to pull the main idea out of thin air, or to print the answers for small n and generalize.

I've then tried to solve problems B and C, but there I actually had an opposite issue: I was digging in the right direction (maintaining a piecewise-constant rolling window of size y in B, going in increasing order of b_i and checking how much we can deviate from the sorted order of a_i in C), but at some point I stopped digging, with the justification that in an AGC problem I should look for a beautiful alternative approach instead, which I could not find. After reading the editorial it turned out that the missing piece was more digging :)

Luckily, in problem D the required digging was not very deep, and I managed to get a non-zero score with a whopping 2 minutes remaining in the round. This did not get me any tour points, but I guess there is still an imaginary chance to qualify if I win the upcoming AGC 076. That is not going to happen, of course :)

tourist did his share of digging faster than others, but as his AWTF qualification was set in stone anyway, these results might be celebrated more by Kevin090228 who has likely guaranteed his AWTF qualification with this second place, and f3e6g4 who has jumped into the magical top 12 for now. Congratulations to all three!

Let me highlight problem C from this round, at a risk of not being able to fully describe a solution next week: 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. 

Thanks for reading, and check back next week.

A 13-10 week

The Universal Cup Grand Prix of Jinan was the only round of last week (problems, results, top 5 on the left). This season is turning out to be the most one-sided to date, with team USA1, which won all previous seasons, winning 8 out of the first 9 Grand Prix. This particular contest was very one-sided as well, with USA1 winning 13 problems to 10, with more than an hour to spare. Well done!

One slightly disappointing thing about the Universal Cup is that the problem discussions happen on Discord, so they are not publicly searchable/discoverable, which I think is quite bad for the overall programming contest ecosystem: most people won't see those discussions, so they are not inspired to solve and create new problems by seeing the greats share their passion for solving, not to mention the (likely inevitable) day in the far future where the Discord server no longer works, and the information is gone or at least no longer discoverable via old links. I'm wondering if the Universal Cup team has considered holding the discussions on Codeforces, or creating their own public forum instead, or maybe making the Discord discussions visible via a public/indexed page?

In my previous summary, I have mentioned a M(IT)^2 problem: you are given a string of length <=10⁵. You can replace any occurrence of MIT with TIM and vice versa, and do that as many times as you want. What is the maximum number of occurrences of MITIT you can get?

If we look only at every second letter in the string, then what happens is that we swap adjacent M and T in that half-string, but this is only possible if the other half-string has an I in the right place. Since the Is never change, this condition is static. So what actually happens is we find the substrings of the original string that satisfy the following criteria:

• It has M/T on positions of one parity.
• It has I on positions of the other parity.
  

Now consider all maximal substrings (ones that cannot be extended) with this property:

• They won't overlap so they can be handled independently, since if two such strings overlap then their union is also such string.
• Each occurrence of MITIT will always be entirely within one of them.
• We can arbitrarily rearrange Ms and Ts within each of them, since adjacent swaps can produce any permutation.
• Therefore the maximum number of occurrences of MITIT is min(m, t/2) where m is the number of Ms and t is the number ot Ts.

Finally, we need to be able to implement this cleanly. I suggest to have an outside loop for the parity (whether odd or even positions have Is), then within this loop every position either has a good letter or not, so we can iterate over the string and maintain the values of m and t for the running substring, resetting both to zero when we see a bad letter for a certain position. Something like this:

int res = 0;

for (int p = 0; p < 2; ++p) {

  int m = 0;

  int t = 0;

  for (int i = 0; i <= s.size(); ++i) {

    bool ok = i < s.size() && ((s[i] == 'I') ^ ((i + p) % 2));

    if (ok) {

      if (s[i] == 'M') ++m;

      if (s[i] == 'T') ++t;

    } else { 

      res += min(m, t / 2);

      m = 0;

      t = 0;

    }

  }

}

Thanks for reading, and check back next week!

A winter week

The last weekend was packed with contests. First off, the Yandex Cup 2025 onsite final took place in Istanbul early on Saturday (results, top 5 on the left). The usual suspects topped the scoreboard, and Kevin got the highest score in each problem and earned the well-deserved first place. Congratulations!

This was already the 10th cphof-worthy contest of 2025, and with the addition of the upcoming Hacker Cup and the completed without published results TopCoder Marathon Match Tournament (yes, TopCoder is still around! But does anybody know what happened to the results?) it could be 12. That is a big improvement over the recent years, and the overall record of 17 per year in 2016 does not look too far away. Huge thanks to all organizers, and I'm looking forward to the 2026 editions!

Codeforces Round 1069, which reused some of the problems of the Yandex final, took place in parallel (problems, results, top 5 on the left, analysis). A Kevin won here as well, solving problem D with just 6 minutes remaining in the round. Kudos for the perseverance!

The Universal Cup Grand Prix of Poland also took place on Saturday (problems, results, top 5 on the left). The first Kevin, together with his teammates, needed less than half of the contest to wrap things up, almost 90 minutes faster than everybody else. The closest pursuers were the other veteran teams Almost Retired Dandelion and Amstelpark, and I am of course partial to seeing veteran teams perform well. Congratulations!

The M(IT)^2 25-26 Winter Contest followed on Sunday, starting with the Individual Round (problems, results, top 5 on the left, analysis). The second Kevin came out ahead this time, but he had to wait anxiously for quite some time since Gennady had a big penalty time advantage after the first four problems, and therefore could afford to solve the fifth problem twenty minutes later but still win. This did not happen, so congratulations on the victory!

The easiest problem turned out to be (relatively) challenging for me, as I used 12 minutes to get it right while some others needed only 3. It went like this: you are given a string of length <=10⁵. You can replace any occurrence of MIT with TIM and vice versa, and do that as many times as you want. What is the maximum number of occurrences of MITIT you can get? Can you see how to solve and implement this without too much casework?

The Team Round followed a few hours later (problems, results, top 5 on the left, analysis, award ceremony stream). Finally, no Kevins in the first place: team T1 had Jaehyun, Gennady and Sunghyeon instead. Congratulations!

Thanks for reading, and check back next week!

A 29 week

Meta Hacker Cup 2025 Round 3 on Saturday narrowed the field down to the 25 finalists (problems, results, top 5 on the left, my screencast). After solving B relatively quickly, I got stuck on A for about 50 minutes. The overall solution plan was relatively clear — k=2 is a special case, in all other cases we can achieve the minimum amount derived from the area by solving greedily with some small backtracking or heuristic to deal with the diagonal. However, I could not figure out that heuristic, neither on paper nor by trying things on the computer. When I decided to give up and switch to other problems, a lot of time had already been wasted.

I've then solved D and C relatively quickly again, and also figured out the overall plan for E on paper: we just need to put two 1s at the end and solve recursively, and to achieve that we can first move two 1s into one of the last 6 positions by big swaps that essentially swap the first and second halves of some suffix, and then do some casework to move them to exactly the last 2 positions. However, I got bogged down in that casework, and only a few minutes before the end I realized that I can just implement any bfs, dfs, or bruteforce to solve the problem for n=3 without manual casework, and it was a bit too late, I have finished debugging only by using 5-10 additional minutes after the end of the round.

It was therefore only place 29 for me, and top 25 qualify for the final round :( It is an improvement over place 42 last year, and unlike the AtCoder WTF qualification, here I felt that the qualification was well within reach, and I had only myself to blame for wasting too much time on A. So, I have big hopes to qualify next year!

What is more disappointing (but maybe expected?) is that I did well on quite standard problems B, C and D that were mostly about quick implementation for me, but poorly on the heuristic/ad-hoc problems A and E. Those problems were set nicely in such a way that many approaches work, without squeezing the constraints so much that only a specific heuristic is required, and I enjoy both solving and setting such problems a lot. I think such problems reward the will and ability to experiment using a computer and practical problem solving skills, which are quite general qualities useful outside of the programming competition world. So please do try to solve problems A and E for practice if the above did not spoil them too much, I think you will find it quite enjoyable!

As usual, the strategy does not matter as much if you can just solve everything :) Congratulations to Yui, Gennady and Kevin on the great performance!

The 4th Universal Cup Stage 7: Grand Prix of Zhengzhou also took place on Saturday (problems, results, top 5 on the left). Gennady and Kevin showed up again to claim the first place together with Andrew, even though Yuhao, Lingyu and Qiwen (with an average Codeforces rating even higher than USA1!) put up a good fight and were trying to solve L and overtake them right until the end. Well done to both teams!

Thanks for reading, and check back next week!