An unexpected verdict week

Codeforces Round 658 was the first event of the Jul 20 - Jul 26 week (problems, results, top 5 on the left, my screencast, analysis). Benq has managed to finish all six problems in time, even though the first five would be enough for the first place anyway. Congratulations on the confident victory!

I have managed to dig myself out of the piecewise quadratic function world with just 8 minutes to go, which was still quite satisfying even though competing with Benq was completely out of question :)

TopCoder SRM 788 started the race for the first TCO21 spot (problems, results, top 5 on the left, my screencast, analysis). My easy-hard-medium strategy has hurt me this time, as after submitting the hard I saw others get 500+ points for the medium and submitted it without enough thinking, leading to a resubmit later. On the other hand, I could submit, stress-test, debug, fix and resubmit it without the pressure of "should I switch to the hard instead?" :) It was hard to fight for the top places with the resubmission. Even though the medium problem was much harder than the other two for lyrically as well, she got it right from the first attempt and earned 5 TCO21 points. Congratulations!

Here is the problem that caused all this mess: you are given an H times W grid (H*W<=500), with some of the boundaries between cells being passable, and some being walls. All outside boundaries are walls. Your goal is to remove some more non-outside walls in such a way that the remaining walls split the entire grid into rectangular areas without internal walls. What is the maximum number of such rectangles one can get?

Codeforces Round 659 then revealed the origin of "Polish Mafia" team name (problems, results, top 5 on the left, analysis). I could not solve problem C (neither could I solve problem F, but I did not spend much time on it), and I was not alone. That makes the performance of tourist, Benq and Radewoosh who solved all six problems even more impressive, well done! Even they have solved problem C as their last or next-to-last problem, suggesting it was also quite tricky for them.

Here is that problem: you are given a string of length up to 10⁵, consisting of the first 20 lowercase English letters. In one step, you can pick any set of characters in this string that are all equal (not necessarily all occurrences of that character), and change all of them to some other character (the same for all replacements in this step). What is the smallest number of steps needed to obtain the other given string of the same length?

I would also like to highlight the excellent investigation by maroonrk on the practical performance of modern flow algorithms :)

Thanks for reading, and check back for more!

An Eggheads week

The Jul 13 - Jul 19 week was the second TopCoder-only week in a row, with TopCoder Open 2020 Round 2B (problems, results, top 5 on the left, parallel round results, my screencast, analysis). 203 more contestants advanced to Round 3, and DmitryGrigorev was on the first place thanks to going for easy+hard. Congratulations! Nobody was able to solve all three problems, and the score from easy+medium was only good enough for the 5th place.

Check back for more :)

A stable bubble week

TopCoder Open 2020 Round 2A was the main event of Jul 6 - Jul 12 week (problems, results, top 5 on the left, parallel round results, analysis). Four contestants solved all three problems in the main round, which is even more impressive given that nobody managed to do that in the parallel round, despite that fact that the strongest contestants who qualified directly to Round 4 were competing there. Congratulations to all four, and especially to Kriii on the win!

In my previous summary, I have mentioned a Codeforces problem: you are given an array a with at most 1000 elements. Then we write down all pairs of positions that form an inversion: pairs (u,v) such that u<v and a_u>a_v, getting a long list of all those pairs. Now we want to treat this list as a sorting program: for every pair in the list, we will swap the elements on the corresponding positions. Our goal is to make this program actually sort our array. We are allowed to put the elements of the list in arbitrary order (but we must have all pairs that form an inversion in the starting array exactly once).

If we were allowed to swap any pair that forms an inversion in the current state of the array, then the bubble sort algorithm would work, as it only swaps adjacent elements that form an inversion. However, we can only use the inversions from the initial array (and must use them all).

In order to achieve this, we need to find an algorithm that tries to keep most existing inversions unchanged. Let's do the following: first, we find the maximum number. Then, we find the second highest number, and sort them (within their places). Then, we add the third highest number and sort the three numbers within their places, using up all their inversions, and so on. This way, whenever we process a new number, the only thing that happened to the array is that the higher numbers got reordered, so the inversions involving the new number stay unchanged!

The only remaining step is to learn how to put the new number into its correct place using all its inversions. This is equivalent to putting 1 into the correct place given the array 2 3 4 ... k 1 (k+1) ... n. The following sequence of swaps does the job: swap 2 and 1, then swap 3 and 2 (which is in the original position of 1 now), then swap 4 and 3, and so on until swapping k and k-1.

Thanks for reading, and check back for more!