An exponential week

Before we come to the Nov 4 - Nov 10 week, I've realized that I forgot to cover the Open Cup 2019-20 Grand Prix of Siberia that took place on Nov 3 (problems, results, top 5 on the left). Team USA1 was once again the fastest, but Team Past Glory got their third stage win thanks to solving 11 problems in 11 submissions. Amazing accuracy!

One other very notable thing from the Oct 28 - Nov 3 week that I forgot to mention was this post by ouuan which highlighted this post by min_25. It turns out that the "successive shortest paths" min-cost-max-flow algorithm that I was taught a long time ago and was implementing ever since is actually exponential, and can time out on graphs as small as 50 vertices! Before this post, I have assumed that it's actually polynomial, and even if the power of that polynomial is high, it is fast enough on graphs with thousands of edges. I guess some people in the community already knew this as the original post in Japanese is from 1.5 years ago, but it was news for me and maybe for you as well :)

Coming back to the main topic of this summary, the Nov 4 - Nov 10 week, Codeforces Round 599 took place on Wednesday (problems, results, top 5 on the left, analysis). Problems D and E were both quite hard to get, and Benq got E, which gives more points, reasonably fast. It means that he won the round and jumped to the first place in the rating list — huge congratulations!

The Open Cup returned with the Grand Prix of Poland on Sunday (problems, results, top 5 on the left, analysis in Polish). This time team Past Glory actually had more incorrect attempts than the only other team that solved all problems, but they had enough speed advantage to overcome that. Congratulations to them and to the team japan02!

Problem E used a nice trick that I did not know before. There are n drones (n<=500000), the i-th drone initially in the point (x_i,y_i,0). Some pairs of drones are connected with cables, those cables are straight lines and they do not intersect except at endpoints. We are then performing k moves (k<=500000), in each move we change the z-coordinate of one of the drones (x- and y-coordinates always remain constant). The cables connected to this drone have to change their length correspondingly, and each cable has a known maximum length — in case it needs to become longer than that, it breaks and stays broken for the remainder of the process. Finally, you are given q (q<=500000) queries, each query being a pair of drones. For each query, you need to find the move which caused the two given drones to become disconnected (using the cables), if any.

The time limit is 30 seconds, so some O(n*sqrt(n)) or even O(n*sqrt(n*log(n))) solutions could pass. Can you see a O(n*polylog(n)) approach, though?

In my previous summary, I have mentioned an AtCoder problem: a string of even length of characters A, B and C is called valid if you can reduce it to an empty string by repeating the following operation: take any substring of length 2 that is neither AB nor BA, and erase it (pushing the two remaining parts back together). You are given an even number n up to 10⁷. How many strings of length n are valid, modulo 998244353?

The problem becomes much easier if we make the following substitution: let's take our string, and in every second position (for example, in all even positions) we replace every A with B and vice versa. Each substring that used to be AB or BA will then become AA or BB! Therefore we can now erase any substring of length 2 that is neither AA nor BB, in other words we can erase any substring of length 2 which has at most 1 occurrence of both A and B. It is relatively easy to notice that it is impossible only if more than half of all characters of our string are A, or more than half of all characters of our string are B. Counting such strings of the given length can be done using combination numbers.

Thanks for reading, and check back for more!