A cyclotomic week

TopCoder SRM 776 was the main event of this week (problems, results, top 5 on the left, analysis). After the coding phase it seemed as if bqi343 would catch up with me in the TCO20 race, but I was quite lucky twice: first, since my incorrect solution for the 1000 passed the system tests; second, since bqi343's 250 has failed. As a bonus, now I have learned about cyclotomic polynomials (I guess it's more like re-learned — surely my mathematician degree should have got me covered here).

The medium problem was very nice as well. There are n=2*a+b pieces of string, out of which a have both ends red, a have both ends green, and b have one red and one green end, so we have n red ends and n green ends in total. We will randomly pair the red and green ends in one of n! possible ways, and tie the corresponding ends together. What is the expected number of cycles we will get? a and b are up to a million.

In my previous summary, I have mentioned a sub-problem of another TopCoder problem: for which pairs of positive integers a <= b can we split all integers from the set {a, a+1, a+2, ..., b-1, b} into two parts with equal sum?

First of all, the sum of all numbers (a+b)*(b-a+1)/2 must be even. Since the two parts in the product (a+b)*(b-a+1) have different parity, one of the parts must be divisible by 4 for the sum to be even. In case the size of the set (b-a+1) is divisible by 4, we can always make such a split: for each four consecutive numbers, we can split them independently as x+(x+3)=(x+1)+(x+2).

Now, what happens when (a+b) is divisible by 4? The size of the set is odd in this case, so we must split into two unequal parts, the smaller part will have at most (b-a)/2 elements, and the bigger part at least (b-a)/2+1 elements. The sum of (b-a)/2 biggest elements in the set is equal to (b-a)/2*(b+b-(b-a)/2+1)/2=(b-a)*(3b+a+2)/8. The sum of (b-a)/2+1 smallest elements in the set is equal to ((b-a)/2+1)*(a+a+(b-a)/2)/2=(b-a+2)*(3a+b)/8. If the former is smaller than the latter, clearly there's no good split as the smaller part will always have the smaller sum.

It turns out that this condition is not just necessary but also sufficient: if we can somehow get the smaller part to have bigger or equal sum, we can make it have equal sum because we can always repeatedly decrease the sum by 1: find two numbers x and x+1 such that x is in the bigger part and x+1 is in the smaller part, and swap them. This argument is the most beautiful part of the solution in my opinion.

The condition (b-a)*(3b+a+2)/8>=(b-a+2)*(3a+b)/8 can be simplified as b>=a+2*sqrt(a), thus our final answer looks like:

• either b-a+1 is divisible by 4, or
• a+b is divisible by 4 and b>=a+2*sqrt(a).

Thanks for reading, and check back next week (hopefully for the best problem of 2019 vote as well)!