A week almost forgotten

TopCoder SRM 657 (problems, results, top 5 on the left) happened very early on Tuesday. The hard problem, despite being conceptually harder, was more standard, while the medium problem required more creativity - as a result, I've spent more time on it, and had to resubmit my solution because of a bug I've found through stress-testing against a brute-force solution on random testcases. Here's the tricky problem: what's the maximal integer that always divides the product x^d₀*(x-1)^d₁*...*(x-n)^^d_n, irrespective of value of x (the only thing we know that x is an integer)? You are given n and d_i as inputs, n is up to 10000, each d_i is between 0 and 9, inclusive.

And of course, congratulations to ainu7 on his fourth SRM victory!

Google Code Jam 2015 Round 1B was the Saturday's contest (problems, results, top 5 on the left, analysis). The problems were quite non-standard this time, and one could easily miss an idea and get stuck. However, solving any of them in full plus one other easy input was enough to qualify, so the best strategy was to skip over problems you're stuck in. Congratulations to vepifanov on not getting stuck at all and solving all three in just over an hour!

VK Cup 2015 Round 3 happened exactly 24 hours later (problems, results, online mirror results, top 5 on the left). The rating favorite team Never Sorry faced a strong challenge from team BananaIsBack, and made the deciding challenge just 10 minutes before the end of the contest. Congratulations to both teams on the amazing competition!

It's been a long time since I posted solutions in addition to problem statements, so let me try to repay that debt :) Two weeks ago, I've posted two problem statements, here's the first one. Several duathletes are competing in a swimming+running duathlon. You know the swimming speed and the running speed of each duathlete, but you don’t know the swimming distance nor the running distance. Which duathletes could win or at least share the first place for some combination of swimming and running distances?

Let the r be the running speed of a duathlete, and s be her swimming speed. Let R be the total running distance, and S be the total swimming distance. Then the total time she's going to spend is R/r+S/s. We need to see if there exist R and S such that this value is maximum over all duathletes. Let's rewrite the above expression as R*(1/r)+S*(1/s) - now we see that it's a scalar product of two vectors: (R,S) and (1/r,1/s), which we can recall to be equal to the length of vector (R,S) times the (signed) length of the projection of vector (1/r,1/s) to the line containing vector (R,S). Since the length of the vector (R,S) is going to be the same for all duathletes, we've essentially reduced the problem to the following geometric one: among given points (1/r,1/s) on the plane, does there exist a line such that projecting all points to this line will result in the given point being the first on the line? Now it's not hard to see that we need to find the convex hull of points (1/r,1/s), and then take its part that corresponds to lines where both R and S are positive.

I like the solution for the other problem posted two weeks ago even more. The problem was: you are given n 4-tuples of points on the plane, and m rectangles with sides parallel to coordinate axes. For each rectangle, you need to check if it contains exactly 2 points from each 4-tuple. In other words, if there’s at least one 4-tuple with 0, 1, 3 or 4 points inside this rectangle, then its answer is “No”, otherwise it’s “Yes”.

The statement is a bit unusual. What would be a more usual one? For example, we might be asked to count the number of given points inside each given rectangle - that one is a standard problem solved via iterating over points and rectangle boundaries in increasing order of one coordinate, and using a Fenwick tree over the other coordinate. Even if each point has an associated weight, we can find the sum of weights of the points inside each rectangle using exactly the same approach.

However, we're not interested in the sum of the weights of the points - we need to know almost exactly which points are inside which rectangle in order to tell if the condition from the problem statement is satisfied. Here's the crucial step: let's assign the same weight for the points inside each given 4-tuple, and different weights for the points from different 4-tuples. Then the fact that we need to have exactly 2 points from each 4-tuple corresponds to exactly one sum of weights. But some other sets of points might have the same sum of weights, too, so we might have false positives. But it's not hard to see that if we pick the weight for each 4-tuple randomly, then the probability of an incorrect set having the same sum of weights as the correct set is very small - essentially, a sum of several random numbers should be zero, and that's unlikely. So we can simply pick random integer weights up to 2³², and then look for rectangles with an appropriate sum of weights inside!

Finally, one week ago I've posted the following problem: you're watching a robot that performs a program of given length L in an infinite cycle on a Cartesian plane. Each of the L steps of the program is a move in one of four cardinal directions, and after the last step the robot continues with the first step again. You're given the locations of the robot at different times (more precisely, at most 10⁵ times, each time is at most 10¹⁸), and need to restore at least one possible cyclic program of length L that would lead to the robot appearing in given locations at given times, or report that there isn't any.

The first step in solving this problem is to split the two-dimensional problem into two independent one-dimensional problems. If x, y are the Cartesian coordinates of the robot, let's define p=x+y and q=x-y. It's not hard to see that moving in one of four cardinal directions corresponds to changing both p and q by +1 or -1, and we can achieve any combination of those changes. Because of this, we have to restore a cyclic program for p and a cyclic program for q, and then combine them to get the answer for the problem.

The one-dimensional problem is naturally easier to analyze. Let's say that the value of coordinate p after i-th step of the robot is p_i, and p₀=0. Since the robot's program is periodic, we have p_i+k*L=p_i+k*p_L. That means that we essentially have L+1 variables, each two consecutive variables must differ by exactly 1, and we have a set of equations of form p_i+k*p_L=t. If we know the value of p_L, then each of those equations has just one variable, and we can determine the value of each variable that is present in at least one equation, and reconstruct the values of variables between the known ones by gradually adding or subtracting 1. How to find p_L? Well, if there's at least one variable that appears in two different equations, we can determine p_L from that system of two equations. And when there's no such variable, then the fact that variables p_i and p_j differ by at most |i-j| gives a set of boundaries on p_L. It's not hard to check if a set of boundaries is consistent, and if yes, find any value of p_L that satisfies those boundaries. Having found such p_L, we can reconstruct all variables from equations, and then reconstruct intermediate variables by adding and subtracting 1. It can turn out to be impossible only if some p_i has a different remainder of division by 2 than i - but in that case it's not hard to see that there's no solution.

Thanks for reading, and check back soon for next week's summary - hopefully you won't have to wait until next Saturday :)