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!