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!