A perfectly balanced week

Codeforces Global Round 5 started the Oct 14 - Oct 20 week (problems, results, top 5 on the left, analysis). Radewoosh solved 8 problems with almost an hour left in the round, and since nobody was able to get all 9, his first place was quite clear. Well done!

I was stuck trying to squeeze my solution for problem H into the constraints for quite some time, and as the round was coming to its end I've decided to make it do multiple passes with some randomization until it fits and submitted. It turns out that this approach worked, and I think it's likely impossible to create a counter-test.

Here's what the problem was about: you are given two strings of even length, a and b, consisting of characters 0 and 1. You start with the string a. In one step, you can choose any prefix of the current string that has even length and reverse it. Your goal is to obtain the string b in at most n+1 steps. You don't need to minimize the number of steps. The length of each string is even and at most 4000.

Can you see a deterministic, or at least a randomized solution?

TopCoder SRM 769 followed on Saturday (problems, results, top 5 on the left). Unlike the previous round, the hard problem in this round had only 1000 possible inputs, so this time I went for a randomized solution intentionally as I could verify that it works on all inputs before submitting. This turned out to be the right approach :)

Here's the problem: you are given a number n between 1 and 1000, and need to construct any tree with n vertices that has at least 2.62ⁿ colorings of the following kind: each vertex is colored red, green or blue in such a way that the distance between any two red vertices is at least 3 (there are no constraints on green and blue vertices).

Open Cup 2019-20 Grand Prix of Southeastern Europe took place on Sunday (problems, results, top 5 on the left, onsite results, analysis). Team USA1 needed just half of the contest to solve all problems,  amazing performance! The stage win counts for the 3 strongest veteran teams are now at 2-2-2.

Solving the interactive problem C was a lot of fun. There is a hidden array a with at most 250 elements, and you need to determine its contents after asking at most 30 queries. Initially, you just know that size of a and that each element of a is an integer between 1 and 10⁹, inclusive. In one query, you can either ask for the value of a particular element of a, or choose a set of indices of elements of a, and get back the multiset of k*(k-1)/2 absolute values of pairwise differences between elements with those indices (where k is the number of indices you've chosen). Note that for a query of the second type you get back a multiset, in other words there is no order and you don't know which difference corresponds to which pair.

Finally, Codeforces Round 594 happened right in the middle of the Open Cup round (problems, results, top 5 on the left, analysis). tlwpdus was able to claim the first place even though they solved one problem less than rhrnald, thanks to the fast solutions for D and E and having no incorrect attempts compared to rhrnald's five. Congratulations to both!

Thanks for reading, and check back for more.