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*using binary search in O(log(_{k}*n*)), using hashes to check if*k*is a period length in O(1), therefore we can find all*s*'s in O(_{k}*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!

Hi Petr,

ReplyDeleteHow can you check using hashes whether k is a period length of a string in O(1)?

Thanks

If the length of period is k, we need to check s[0]...s[n-1-k] and s[k]...s[n-1] to be equal. (It's obvious if you write formal definition)

DeleteThis comment has been removed by the author.

ReplyDeletePetr pretends to be a smartass, lol.

ReplyDeleteWhy would he pretend to be smart if he already is?

Deletehi petr

ReplyDeleteIs it possible to check all possible sub-array in linear time

thanks in advance