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!

A double prix week

Before I cover the last week, I need to mention the 4th Universal Cup Stage 5: Nanjing, which happened the week before and which I forgot to cover (problems, results, top 5 on the left, analysis in Chinese). Even having only 2 out of 3 teammates did not stop team USA1 from winning by a whole problem. Congratulations!

The Universal Cup can't stick to the plan of having rounds only every other week, so Stage 6: Shenyang took place last week (problems, results, top 5 on the left, analysis in Chinese). The first two places look suspiciously similar to the previous round, but for the veteran teams Polish Mafia and Almost Retired Dandelion who also solved everything this was the best result of the season. Well done!

Codeforces Round 1066 wrapped up the week (problems, results, top 5 on the left, analysis). Some of the Universal Cup stars were also strong this time, but they were complemented in the top 5 by jiangbowen and PEIMUDA who were not at the very top in the team rounds. Congratulations on the nice individual performance!

Thanks for reading, and check back next week for a more meaningful summary!

An array week

Meta Hacker Cup 2025 Round 2 was the first event of the Nov 10 — Nov 16 week (problems, results, top 5 on the left, analysis, my screencast). Once again getting the problems right was more important than solving them fast, but it is still more impressive to do both at the same time. Congratulations to Benq and Um_nik who got quite a margin in penalty time compared to the rest of the full scorers!

In problem D, my solution (like all other solutions) was exponential in k. When I ran it on the validation input, it turned out that one case with k=25 (the maximum) takes about 30 seconds, so I was not sure if 80 such cases would run in time, even with the multithreaded template. But then I realized that the exponential part of the solution depends only on k, so we can precompute it once for all possible values of k, and then solve the 80 testcases in polynomial time. The precomputation only took about 40 seconds for all values of k (since the running time is exponential, k=24 is already much faster than k=25 and so on), and I was able to comfortably submit within the 6 minute window.

What I did not realize is that even if the precomputation took 10 minutes, I would still be able to submit, because one can run the precomputation before downloading the input! And unlike regular contests where the result of the precomputation in such cases must fit into the source limit, here we can just keep it in memory (in case we trust that the program will not crash on the first run) or save it to disk. I never had to do something like this in the Hacker Cup, but will definitely keep this trick in mind!

Codeforces Round 1064 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis). maroonrk was done with 42 minutes to go, but only JDScript0117 was able to join him with 5 problems, and only with 5 minutes remaining in the round. Congratulations to both on solving everything!

In my previous summary, I have mentioned my search for a nice and simple templated treap. I have decided to try building one myself, and you can see the result in action in this submission to problem F2 from Global Round 30 (treap class itself at the top, its usage at the bottom).

The API is modeled on lazysegtree, and it is parametrized with exactly the same types S and F and operations on them, with the same requirements on the composition of operations. A treap contains zero or more blocks, where each block represents an array of values of type S. We support the following operations:

• t.prod(block) -> S: computes op(...(op(op(e(), a), b), ...) if the given block has elements (a, b, ...). Runs in O(1).
• t.apply(f, block): replaces each element x of the given block with f(x). Runs in O(1).
• t.single(s) -> block: creates a new block with a single element with the given value. Runs in O(1).
• t.destroy(block): destroys a block so that its memory can be reused. Runs in O(block_size).
• t.concat(block1, block2) -> block: concatenates two blocks into one. The old blocks are consumed by this operation and are no longer valid after it. Runs in O(log(block_size)).
• t.split_left(block, g) -> (block, block): splits a block into a prefix and a suffix, given a predicate g. The split point is chosen in such a way that both of the following are true: either prefix is empty or g(prod(prefix)) is true; either suffix is empty or g(prod(concat(prefix, first_element(suffix)))) is false. If g is monotonic on prod(prefix), then this will find the point where it changes from true to false. Runs in O(log(block_size)).
• t.interleave_left(block1, block2, g) -> block: interleaves two blocks into one. The predicate g tells, given the products of a prefix of block1 and a prefix of block2, whether the last element of that prefix of block1 should come before the last element of that prefix of block2. Runs in O(smaller_block_size*log^2(block_size)) maybe?

This API tries to unify and generalize the two common cases of splitting by index and splitting by key. Splitting by index can be achieved by adding a 1 as one of the elements of struct S, implementing op as addition for that element, and using a predicate on that sum for splitting. Splitting by key can be achieved by storing the key as one of the elements of struct S, and implementing op(k1, k2)=k2 (this is what the submission linked above does).

I've also tried to make the API harder to misuse by making the block type moveable but non-copyable, so that the compiler helps make sure that we don't use a block after it has been consumed by an operation. This requires some std::move's in user code, but hopefully that is not too big of a burden.

We can also add more operations that can be expressed using the above ones, but allow a dedicated implementation with a better constant factor, such as insert (instead of single+interleave) or a product on a range (instead of two splits, product, then two concats back). However, I wanted to start with a small API to be able to iterate faster.

It is certainly not as powerful as a fully custom treap, but I think it can express most of the operations from BYOT, with the exception of range reverse and segment tree beats. And for me it is much more convenient to think in terms of concatenating and splitting arrays and applying associative operations on them, rather than directly in terms of treap implementation. What do you think, and do you have improvement suggestions?

Thanks for reading, and check back soon for last week's summary!

A treap week

Codeforces Global Round 30 was the main event of last week (problems, results, top 5 on the left, analysis, my screencast). I was doing quite well on the first six problems, but got bogged down with implementing treaps with some additional accounting for problem F2, spending more than an hour on that. Right after the contest ended, I had two thoughts:

1. Wow, the people at the top of the scoreboard are so much better than me at implementation, how did they dig themselves out of this treap mess so fast?
2. I should implement some kind of templated treap and have it available for the next rounds. Currently I do not have a library of my own, and rely on the AtCoder library which has very nice templated segment trees and other algorithms, but not treaps.

Well, it turns out that the first thought was wrong. Out of the top 9 contestants (those that solved 8 problems), exactly the first three did not have treaps or splay trees in their solution for F2, but only segment trees plus standard STL data structures (while the next 6 had treaps or splay trees)! So these results clearly show that thinking some more to simplify the implementation beats just jumping into the first tedious simplementation approach one comes up with :) Well done to Otomachi_Una, Kevin114514 and dXqwq!

The second thought still stands though. However, it is not obvious to me what is the best templated abstraction for a treap. From the 9 contestants mentioned above, it seems that only hos.lyric has a templated splay tree, but even in her case the abstraction seems to leak the implementation details (push/pull), and the function splitAt might have been added specifically for this problem since it is not aligned with the rest of the abstraction, relying on the custom field "size" of the node that no other methods use. Compare this to AtCoder's lazysegtree, which is defined in abstract mathematical terms of applying two operations on ranges of data.

So, does somebody know a templated treap/splay tree abstraction that expresses the operations in abstract mathematical terms, and yet is as fast and powerful as tinkering with treap's implementation details?

In my previous summary, I have mentioned another Codeforces problem: you are given a tree with n<=5000 vertices. Consider the 2ⁿ ways to choose a subset S of its vertices, and for each subset S build a complete graph where S is the vertex set, and every two vertices are connected by an edge with a weight equal to the length of the tree path connecting them. What is the sum of weights of minimum spanning trees of those 2ⁿ graphs?

A natural question to ask is: given a particular pair of vertices a and b, in how many of the 2ⁿ subsets will they be directly connected by an edge of the minimum spanning tree? If we can answer that question, then we can just add up those answers multiplied by the distance between a and b to obtain the answer to the problem.

The first difficulty on that path is that "the minimum spanning tree" is not well defined, there might be multiple spanning trees of the same minimum weight. To deal with that, we can choose a particular minimum spanning tree, say, the one found by the Kruskal's algorithm that processes the edges in the order of weights, breaking ties in the lexicographical order of the edge ends.

In order for an edge between a and b to be chosen by the algorithm, it is necessary and sufficient that there is no path connecting a and b using the previous edges in the aforementioned order, namely using all edges of a smaller weight, and edges of the same weight that come before in the lexicographical order. Let us check how this path might go along the tree. Let us draw the tree in the following manner: the path from a to b is at the top, and a subtree grows from each of its vertices. We need to get from a to b, stopping only in vertices in the chosen subset S, such that each jump satisfies the above criteria.

Suppose there is a vertex c in S, hanging somewhere from the middle of the path, such that d(a,c)<d(a,b) and d(b,c)<d(a,b), then we can just go from a to c to b, so in those cases the edge between a and b will not be chosen. Suppose c hangs from the vertex x on the path (x might not be in S, so we cannot stop there). Then d(a,c)=d(a,x)+d(x,c), d(a,b)=d(a,x)+d(b,x), d(b,c)=d(b,x)+d(x,c), so the above inequalities translate to d(x,c)<d(b,x) and d(x,c)<d(a,x), in other words d(x,c)<min(d(a,x),d(b,x)). So in order for the edge between a and b to be chosen, we must have d(x,c)>=min(d(a,x),d(b,x)) for all c in S.

Now, suppose that inequality is strict: d(x,c)>min(d(a,x),d(b,x)). Then it's not hard to see that instead of going to/from c when passing through x, we can go directly to/from a or b, therefore such vertices are not useful to construct the path we are looking for. So the existence or nonexistence of the path depends only on the vertices c with d(x,c)<=min(d(a,x),d(b,x)). Since we already know that the path will exist when there is c such that d(x,c)<min(d(a,x),d(b,x)), the only interesting remaining case is where there is one or more vertices c such that d(x,c)=min(d(a,x),d(b,x)).

The distances between such vertices can be equal to d(a,b), so this is where the lexicographical ordering of the edges comes into play. It is possible to carefully consider it and solve the problem, but we can also make another small observation instead: vertices c such that d(x,c)=min(d(a,x),d(b,x)) are exactly those vertices that are at the distance of d(a,b)/2 from point z that is the middle of the path between a and b (note that z is either a vertex or a midpoint of an edge)!

This raises a natural question: what if, instead of focusing on the edge between a and b, we focus on all edges of the spanning tree with the given middle point z? If d is the smallest distance between z and a vertex in S, then from the above argument we can see that only edges of length 2d can exist in the spanning tree. If we root the original tree at z, and count the number m of subtrees of the root that contain a vertex at depth d (none of them will have a vertex at depth less than d by the definition of d), then it's not hard to observe that we will have exactly m-1 edges with length 2d and middle point z in the spanning tree. Note that in case z is a midpoint of an edge, then m<=2.

So we just need to count for each subtree how many ways are there to choose S in this subtree such that the smallest depth is d, and then we can combine those values to obtain the answer using the above observation, and then sum up those answers over all choices of z.

It was not strictly necessary to go through the Kruskal's algorithm and the lexicographical order part. Instead, we can immediately start with the "consider all edges of the spanning tree with the given middle point z" argument, and the solution will be short and beautiful. However, I also wanted to demonstrate how one can arrive at this idea analytically.

Thanks for reading, and check back next week!