A week without paradox

TopCoder SRM 785 took place during the May 4 - May 10 week (problems, results, top 5 on the left, analysis). The hard problem had this feeling of "it's amazing nobody has asked this before", and it turned out that somebody did :) mochalka had seen this problem before and was the only contestant to get it accepted, winning the match — even in such situation it's important to execute well given the chance, so well done! It turned out that the only bug in my solution was that I was iterating up to bit 29 instead of bit 30 in one place, and it passed in the practice room with that one-byte change. It was disappointing to figure out all tricky details correctly to only fail in that manner :)

Open Cup 2019-20 Grand Prix of Bytedance took place on Sunday (results, top 5 on the left). Team japan02 has really aced it this time, finishing 2 problems ahead of the three leaders of the overall standings and winning their second stage this season with a bang. Congratulations!

Our solution to problem B was quite unusual, and was based on intuition a lot more than is typically reasonable. The problem went like this: a string of 0s and 1s is called balanced if the number of 1s in any two its circular substrings of the same length differs by at most 1. A circular substring of a string s is any string with the length not exceeding the length of s that can be read after we write s on a circle; in other words, it's either a normal substring of s, or a suffix of s concatenated with a prefix of s with total length not exceeding the length of s. You are given a string consisting of 0s, 1s and ?s. How many ways are there to replace each ? with a 0 or a 1 such that the resulting string is balanced? The length of the given string is at most 1024.

In my previous summary, I have mentioned another Open Cup problem: we have a string which is initially empty. Then we repeatedly add characters either to the beginning of the string, or to the end of the string, n times (n<=1000000). Then, we need to print n numbers: how many period lengths did the string have after each addition? A string s has a period length k if 1<=k<=length(s) and for each valid i s_i=s_i+k (note that under this definition the last repetition of a period may be incomplete). For example, the string ababa has 3 period lengths: 2, 4 and 5.

The key observation here is that once a certain length k stops being a period, it will never become one again after we add more characters! This is especially clear from the formal definition above, as we just get more constraints of form s_i=s_i+k as the number of possible values of i increases. Therefore for each length k it will be a period from step k (each string has its own length as a period length) to some step s_k. 

We can find each particular s_k using binary search in O(log(n)), using hashes to check if k is a period length in O(1), therefore we can find all s_k's in O(n*log(n)), and the numbers we need to print can then be computed from those in O(n).

It's not particularly important for this problem, but note that we're only doing O(n*log(n)) equality comparisons for the hashes, therefore we're not subject to the birthday paradox, and 32-bit hashes are enough.

Thanks for reading, and check back for more!