A Berlekamp-Massey week

TopCoder SRM 824 was the first event of this week (problems, results, top 5 on the left, my screencast, TCO race standings). I had some kind of blackout and could not solve the medium, which in retrospect was quite standard. However, the hard was also quite standard and straightforward for me, while many others failed to get all details correctly, so the end result was not so bad. Still, I could not really compete with Um_nik and mhq who solved all three problems. Well done!

Open Cup has returned from its winter break with the Grand Prix of Kyoto on Sunday (results, top 5 on the left). Team USA1 continued their domination of this Open Cup season, finishing all problems a good hour before any other team, and with just one incorrect attempt to boot. Very impressive!

Our team struggled quite a bit with the two mathy problems H and M, until Google and OEIS came to the rescue. In problem M, I found the answers to a simplified problem in OEIS, noticed a linear recurrence as one of the methods to compute it, and then hypothesized that the answers to the full problem can also be determined using a linear recurrence :) And in problem H, I had to do a quick dive into some mathematical concepts that were new to me.

I have found problem J the most beautiful in this round: you are given a string of length n (n<=200000) with characters +, - and ?, and two numbers a and b. You can replace each ? character with either + or -. Then you need to find a balanced substring of the string, which means a substring of length a+b that has exactly a + characters and b - characters, in any order, and remove it from the string (the parts before and after the substring being removed become adjacent to each other). Then you need to find a balanced substring in the remaining string, and remove it from the string, and so on. You goal is to replace the ? characters in such a way that the number of times you can remove a balanced substring is maximum possible (this number of times will never exceed n/(a+b) since we would run out of characters). How to find this maximum number of times?

In my previous summary, I have mentioned a Codeforces problem: you are given a single integer n. You start with a sequence of numbers 1, 2, 3, ..., n. In one step, you can take any two numbers x and y, and replace them with x+y and |x-y|. Your goal is to make all numbers equal, and you also need to make those equal final numbers as small as possible, and you need to do all this in at most 20n steps.

I was not sure how to even approach this problem, so I started by implementing a brute force solution that found me the answers for all values of n up to 15. The brute force returns that for n=3,4 we can make all numbers equal to 4, for n=5,6,7,8 we can make all numbers equal to 8, and for n=9,10,11,12,13,14,15 we can make all numbers equal to 16. This naturally suggests that we need to target the smallest power of two that is at least n. I did not prove this fact during the contest, but there exists a very simple proof.

Apart from this observation, looking at the way the brute force achieved the goal helped me learn a couple of tricks that are useful for the solution. First of all, when we have a 0, then we can double any number: (0,x)->(x,x)->(0,2x). Second, the solution often makes many smaller powers of two, and then makes them all equal using this trick.

So now we need to convert all numbers into powers of two, not necessarily equal ones. Suppose 2^k is the smallest power of two bigger than n (we assume n is not a power of two, as for that case we can just use the solution for n-1 without touching the number n at all). We can apply the operation to n and 2^k-n, n-1 and 2^k-(n-1), and so on, 2^k-1+1 and 2^k-1-1. This way, we will get many copies of 2^k as sums, and from the differences we will get numbers 2n-2^k, 2n-2^k-2, ..., 6, 4, 2. And we also have the remaining numbers which we did not touch, those are 2^k-1 and 1, 2, ..., 2^k-n-1. 2^k and 2^k-1 are already powers of two so we don't need to do anything. And for the two chains 1, 2, ..., 2^k-n-1 and 2, 4, 6, ..., 2n-2^k-2, 2n-2^k we can just apply the same algorithm recursively: directly for the first chain, and doing a recursive call for 1, 2, 3, ..., n-2^k-1 and multiplying all results by two for the second chain.

This way we will convert all numbers into powers of two not exceeding 2^k. It turns out that for n>=3 at least two of those powers will be equal and less than 2^k, which allows us to use the (x,x)->(0,2x) step to get a zero, and then use this zero to keep multiplying all numbers by two until we have only one zero and many 2^k, and finally use the (0,x)->(x,x) step to get rid of the zero.

Thanks for reading, and check back next week!