A quadratic week

Last week had a relatively high density of contests, so much that two of them collided: Codeforces Round 453 and TopCoder SRM 726 took place at the same time on Tuesday. The Codeforces round started 25 minutes earlier, so we'll begin with it (problems, results, top 5 on the left, analysis). dotorya had chosen a seemingly suboptimal order to solve the first four problems, as A and B required disproportionately much time relative to their value, but he was faster than the competition and thus still ended up in first place — well done!

TopCoder SRM 726 at roughly the same time attracted the second half of the community (problems, results, top 5 on the left, my screencast). The hard problem has proved decisive: you are given 2000000 tasks, to be done in 2000 days, at most one task per day (so most of the tasks will end up not being done). For each task you know three numbers: the segment of days when it can be done (from l_i to r_i), and the profit c_i from doing it. You need to pick the task to be done in each day in such a way that the total profit is maximized. This is naturally reduced to a weighted maximum matching problem, but surely it will time out with 2 million vertices in the graph — or will it?

Codeforces ran another round, Round 454, on Saturday (problems, results, top 5 on the left, analysis). All problems were tractable this time for moejy0viiiiiv and Radewoosh, and in case of the former with 30 minutes to spare. Congratulations on the victory!

In my previous summary, I have mentioned an Open Cup problem: you are given an integer n with at most a million digits. You need to determine if it's a perfect square or not. You don't need to actually find the square root.

As is often the case in problems with a Yes/No answer, it suffices to find an algorithm that always finds one of the two answers correctly, and the other with a certain probability that is greater than zero. We can then apply it repeatedly until the probability of not finding the correct answer is exponentiated to become essentially zero.

Let's pick a prime number p. If n is a perfect square, then n mod p is always a quadratic residue. If not, then assuming p is picked randomly the probability of n mod p being a quadratic residue is roughly 0.5, since roughly half of all numbers mod p are quadratic residues (this is merely handwaving; can anyone prove this probability estimation formally?).

So we can pick, say, 30 random prime numbers, and check if n is a quadratic residue modulo each of them. If at least one says no, then the overall answer is no, otherwise it's yes. Checking if a number is a quadratic residue modulo p is done by checking if n^(p-1)/2=1 (mod p).

Thank for reading, and check back for this week's summary!