Petr is the new Algorithm Champion!
Discuss this match
Friday, November 2, 2007
Introduction by Olexiy
Petr finished strongly as the winner of the 2007 TopCoder Collegiate Challenge Algorithm competition, taking home the top prize of $25,000. krijgertje came in second, and gawry took home the third.
RandomRide
This problem can be solved by a simple emulation of the movement process. Nevertheless, the solution contains two tricky parts. Firstly, for each moment of time we need to know which road should be chosen for each flip (or flips) result. Secondly, we should somehow realize that we will never get back home.
The first problem can be resolved by storing the map in a proper way. The easiest way to do this is to store for each intersection all its neighbors in a clockwise order. Using this information we can easily determine the type of the intersection (three-roads or four-roads) and an appropriate road for the flip (or flips) result.
The second problem is not a problem at all if we trust the statement "if we ride for a rather long time, we will never get back home". Let's show that this statement is true and will find a better approximation for the "rather long time" part. Each moment of time is characterized by a current intersection, a current directing and a current shift in the flips. Multiplying the quantities of distinct values for each of the listed parameters we will get that 15*4*50 = 3000 steps (at most 4 flips each step) are enough to report the infinite ride.
You can take someone's solution as a reference.
Factorer
First of all, we need to solve a "ax^2 + bx + c = 0" equation. As we know from the algebra course the solutions for it are (-b-sqrt(det))/(2*a) and (-b+sqrt(det))/(2*a), where det is equal to b*b-4*a*c. If the solutions are x1 and x2, the desired factorization is a(x-x1)(x-x2). The only task that remains is to move the a coefficient inside the brackets in order to make all parameters be integers and choose the best result according to the tie-breaking rules.
Let's look at the det value. If it is not a perfect square, we can not factorize the polynomial because x1 and x2 will be irrational. Otherwise x1 and x2 are rational, i.e. can be presented in a form of a proper fractions p1/q1 and p2/q2, respectively (where p1, p2, q1 and q2 are all integers). So, to get an integer factorization we must multiply the expression in the first brackets by q1 and the expression in the second brackets by q2.
The last thing left is to find where to place the remaining part of a coefficient (it is now equal to a1 = a / (q1 * q2)) inside the brackets in order to achieve the best result according to the tie-breaking rules. Since we want the coefficient in the first brackets to be as big as possible, there are exactly two options left. We choose one of the brackets to be the first one in the final factorization, multiply both numbers inside it by a1, multiply it by -1 when needed (to make the first coefficient to be positive) and compare the two results. The best of those should be formatted and returned.
FactoryEmulation
First of all, let's assume that we want to fill all orders. This assumption will make us try all possible subsets of the given orders and choose one with the maximum profit. Let's also assume that orders are sorted by the time parameter.
Each second we are either increasing productivity ('I' second) or producing goods ('P' second). Increasing productivity is good for perspective, producing goods is good for current needs. We will fulfill orders step-by-step starting with the earliest one.
Initially, all seconds are 'I' seconds. If an order at time T arrives and there are not enough of goods for it, the best way to obtain the required amount of goods is converting some 'I' seconds right before time T into 'P' seconds. So, we convert each latest 'I' second preceding T into 'P' second until it is enough of goods to fulfill the order.
It is not very hard to show that the described algorithm is correct. But it has a defect - it is too slow to get into the time limit. The solution is to perform batch updates from 'I' seconds into 'P' seconds instead of updating them one-by-one. The idea is to estimate the required amount of such updates using the number of missing goods.