A postponed week

The Apr 8 - Apr 14 week was light on contests from the usual suspects, but Google Code Jam Round 1A filled the void (problems, results, top 5 on the left). Gennady.Korotkevich required just 26 minutes to wrap things up, with others following in approximately 5-minute increments. Congratulations to everybody who made it to Round 2!

In my previous summary, I have mentioned two problems. The first once came from ICPC World Finals: you are given a street with n<=500 traffic lights on it arranged from left to right. The i-th traffic light stays red for r_i seconds, then green for g_i seconds, then repeats this cycle infinitely. The cycles for all traffic lights start at the same time 0, r_i and g_i are integers, and r_i+g_i does not exceed 100. Suppose you approach this street from the left at a random moment in time, and drive until you encounter a red light for the first time, or until you pass the entire street. What is the probability that you see red for the first time on 1st, 2nd, ..., n-th traffic light?

The solutions gives a whole new meaning to the "meet in the middle" term. First of all, suppose all periods r_i+g_i are relatively prime. In this case seeing red on each of the traffic lights are independent random events, and therefore our answers are r₁/(r₁+g₁), g₁/(r₁+g₁)*r₂/(r₂+g₂), ...

Moreover, only slightly more complex solution exists in case any two periods are either relatively prime, or one divides the other. In each group of periods where one divides the other we'll pick the largest one, and go from left to right which units of time modulo that largest period have already seen red, and the probabilities for different groups can still be simply multiplied since they're independent.

However, we have arbitrary periods up to 100 in this problem, so the above condition does not hold. In order to overcome this, let's split the time into m parts: first part will have units 0, m, 2m, ..., the second part will have units 1, m+1, 2m+1, ..., and so on. Each of the parts can be "compressed" m times to obtain an instance of the same problem, but a period of p gets replaced by a period of p/gcd(p,m).

The only remaining task is to find which value of m will guarantee that for any two numbers p and q up to 100, the numbers p'=p/gcd(p,m) and q'=q/gcd(p,m) are always relatively prime or one divides the other. We can write a small program for that, and it turns out that m can be as small as 2520=2³*3²*5*7.

More generally, if the numbers were up to x instead of 100, m could be equal to the product of largest powers of primes not exceeding sqrt(x). For p' and q' to have a non-trivial greatest common divisor means for them to have two different primes in their factorization, which would mean that original numbers p and q were a product of two prime powers each exceeding sqrt(x), which is a contradiction.

We have essentially decomposed the problem m times from the top, and that allowed to split it into independent problems of size at most x at the bottom, hence the "meet in the middle" mention above. The running time of this solution is O(n*m*x), which is fast enough.

The second problem I mentioned came from Codeforces: you have n game units, each capable of causing 1 unit of damage per second. You need to merge them into m bigger game units, and if a_i units were merged into the i-th bigger unit, it will cause a_i units of damage per second. The m bigger units will then attack an enemy army also consisting of m units, with the j-th enemy unit having b_j hit points. The attack will happen second-by-second, and in each second each of your big units attacks one enemy unit. It is allowed for multiple units to attack one enemy unit in one second. What is the fastest way to decrease the hit points of all enemy units to zero or negative? You can choose the way you merge the n units into m big units, but you can do it only once, before all attacks.

The key idea in solving this problem is to postpone the choice of a_i. Let's imagine we start with a single big unit of size n. Let it keep attacking the first enemy unit, until at some second its hit points drop to zero or below. If they dropped below zero, it means that we have wasted some attacking power; to avoid that, let us split this big unit into two now, one that can exactly finish the first enemy unit, and the other can now attack the second enemy unit during that second. In the following seconds, both units would keep attacking the second enemy unit, and when its hit points drop below zero, we will split one of our units again to avoid wasting attacking power.

We will end up with at most m+1 units after all splitting is done, since we split once per enemy unit, but we can notice that the last split was not necessary, so we can skip doing it and end up with m units as required. And we have clearly spent the smallest possible time, since we never wasted a single unit of damage during all seconds except the last one.

In some sense, the main obstacle in solving this problem is not realizing that it is actually easy :)

Thanks for reading, and check back for more!