Wednesday, July 26, 2006 Match summary
Twenty minutes ago I started trying to think up a joke to open this editorial and couldn't think of
anything clever, so I'll just paste
a link to the previous one I wrote
– for the next SRM I'll remember to make something go wrong in the match,
so it will be easier to write funny introductions. SRM 313 attracted 928 participants from 62 different countries. Division 1 featured a surprisingly difficult medium problem that got the drop on almost 400 of the competitors, while the other two problems in that division were pretty standard. In division 2, the problem set turned out to be pretty balanced, leaving a final table with a surprising continuity in scores that almost had no big holes. Division 1 was dominated by dmytro, thanks to that tricky medium problem and his solid performance in the other two. He was followed by Petr, who was the only other coder to finish all three problems correctly. lovro took the third spot in the podium by having almost the fastest submissions in the easy and hard problems as well as a successful challenge. In division 2, hohosky started his TopCoder experience with a victory, thanks to the fastest submission in the medium and hard and a second fastest in the easy problem.bdbyrne was second and the third spot almost deserves to be shared between fhoward, Perseph0ne and Rainault, all packed whithin less than 2.5 points. The ProblemsCyclesInPermutationsUsed as: Division Two  Level One:
This problem was a fairly simple simulation. For each possible starting square you could simulate the behavior while counting the number of squares visited and keeping track of the maximum length found. This can easily be done with two loops, one inside the other. Since in each square you can do at most 50 steps to get back, and there are at most 50 squares, the inner part of the program does a maximum of 50*50 repetitions, which is way under the time limit. You can see jmadsen's code for a perfectly clear implementation in English. PrefixFreeSetsUsed as: Division Two  Level Two: Used as: Division One  Level One:
Prefix free sets are a useful thing in many computer science applications. For example a prefix free set as an alphabet is good because it can be parsed in an easy and deterministic manner. This idea is used in huffman coding for compression. This made this problem particularly natural and therefore good (at least in my not so humble opinion). To solve it, the main idea was to see that if you have a forbidden pair (s,t) where s is a prefix of t, it was always better (or equal) to remove s. Many people found this clear enough to solve the problem pretty quickly, but if you need a formal proof, here goes: Let S be the set of words, let (s,t) be a pair belonging to S such that s is a prefix of t. We want to prove that the largest subset of S  {s} that is prefixfree has a less or equal number of elements that the largest subset of S  {t} that is prefix free. Let A be a prefixfree subset of S  {s} that has maximum number of elements. Let A' be (A  {s}) U {t}. We want to show that:
1. A' is a subset of S  {t}. This follows clearly from construction of A'. With 1, 2 and 3 proved, the initial proposition is demonstrated. The straightforward implementation was following this pseudocode: for each i in 0 .. words  1 for each j in i+1 .. words1 if words[i] is a prefix of words[j] remove words[i] and start again. return the size of words For a clear implementation of this idea see Petr's code. There were also many optimizations that could be done, but this is perfectly within the time limits. For a discussion of those optimizations see this thread in the forums. ParallelProgrammingUsed as: Division Two  Level Three:
There were many different solutions for this problem, all relying on the same idea. I'll examine two similar approaches, one using a prewritten graph algorithm and the other without it, for people who are not familiar with graphs. Finally, I'll point out the simplest code I've seen that only simulates the situation. The idea using some graph theoryThe first step is running a topological sort on the dependencies graph given. If you do not know what is this, simply follow the link to a brief and clear explanation of its meaning and implementation. This could lead to two possible outcomes:
1. There is a cycle, and no topological sort is possible: In this case, our
program simply returns 1, because if there are cyclic dependencies neither
process in the cycle will ever be able to start, so it's impossible to
finish them all. set N = number of processes set startTime = an array of N integer elements set endTime = an array of N integer elements for i = 0 to N1 set p = A[i] startTime[p] = 0 for each x such that p depends on x startTime[p] = max(startTime[p], endTime[x]) endTime[p] = startTime[p] + time[p] return the maximum element of endTime The idea is simple, start each process as soon as possible. Since they are calculated in the order given by the topological sort, when a process is processed to calculate it's starting time, all it's dependencies are calculated (because topological sort gives an order such that each edge goes forward, so dependencies are always before in the order). When all starting and ending times are calculated, simply return the latest end time. The idea without using some graph theoryHere is the pseudocode: set N = number of processes endTime = array of N integer elements canWork = array of N boolean elements for i = 0 to N1 canWork[i] = process i has any dependencies? if canWork[i] endTime[i] = time[i] do set changes = false for i = 0 to N1 if canWork[i] is false set canStart = true set startTime = 0 for each x such that i depends on x if canWork[x] is false, set canStart = false startTime = max(startTime, endTime[x]) if canStart changes = true canWork[i] = true endTime[i] = startTime + time[i] while changes if every element of canWork is true return the maximum element of endtime else return 1The idea here is the same as before, but we don't precalculate the order in which we have to process the processes – instead, we simply process each item we can until we can't process anything. If everything was processed, the latest end time is the answer, and if some processes were left unprocessed (ironically), we return 1. The simulation idea (if you prefer looking at code to reading)See fhoward. A tip to understand the code, that is simple and selfexplanatory: time[i] = 0 means process i is already terminated. CrazyRunningUsed as: Division One  Level Two:
Picture yourself as an average division 1 coder. You have just quickly finishedy quickly the easy problem and think that there's enough time left to take the medium slow. The 50 extra points contribute to this impression. After reading the problem statement, you write down some numbers and mathematical expressions, maybe think about a dynammic programming approach, but nothing convinces you. After 15 minutes of doing this, you are mad at yourself and take a look at the division summary: Nobody has submitted! Not even one of the many coders that have several hundred rating points more than you. Now you are not mad at yourself anymore – you are mad at John and his inability to develop a decent running strategy. Solving this problem required imagination and either faith or a good proof. The strange thing in this case is that almost everybody solved it differently, but the idea behind all solutions is the same: Any input has the same answer as having 1 corridor of length corridors[0] and N1 of length average(corridors[1],...,corridors[N1]). At this point, I could invoke faith and keep writing the rest of the problem, but I won't, because I want you all to keep being mad at John and not mad at me. I also won't give a mathematical proof because it would be too long and annoying. I will, instead, give an informal proof or idea.
After John finished running, he can make a list of the corridors he visited in order.
This list is finite and starts with 0. One way to express the expected
length is to calculate the probability of such a sequence happening and
then calculate the infinite sum of all sequence probabilities multiplied
by the length of the path in each case: In this summation, all terms can be divided in groups of (N1)! lists such that:
Of course, all these lists have equal probability, so we can take the common factor out and
Now we have a problem with 3 parameters: Let f(n) be the expected length of a path when you are in the center, coming from a corridor that is not the first one, and having n corridors left to visit. At the beginning you run to the center, then run to the outer end of some corridor that is not the c0, and the run back to the center, so the solution to the problem is c0 + cr * 2 + f(N2). The only thing left is to see how to calculate f. When you are in the situation described, exactly one of these 4 things can happen:
f(n) = p1*(cr*2+f(n)) + p2*(2*c0+2*cr+f(n)) + p3*(2*cr+f(n1)) + p4*(2*c0+2*cr+f(n1)) where p1, p2, p3 and p4 are the probabilities of each case and each one appears multiplied by the expected length to finish if that's the case. Note that the number of "moves" of each case is not the same for all of them, but that's not important as long as all cover disjoint cases. Let's calculate the probabilities:
Now, to calculate f, we can do it with great precision with the following code: f(n) if n is 0 return cr rec = f(n1) p = 1 r = p3*(2*cr+rec) + p4*(2*c0+2*cr+rec) //time to finish while p > reallySmallEpsilon r = r + p*p1*2*cr + p*p3*2*cr p = p * (p1 + p3) //probability of remaining unfinished return r It's good to calculate any recursive function dependent only on itself and smaller terms. In this case memoization is not needed because there is only one call to f(n1), but it may be needed if f(n) is dependant on more than one term apart from itself. I think its a good idea to implement this, to have the idea clear for further use in future competitions. BasketballStrategyUsed as: Division One  Level Three:
This problem is pretty straightforward if you know a little about many aspects of programming. You needed some, but not much, of:
To make everything simpler it is better to have a point structure or class defined that has two double precision (double) floating point members: x and y. Also have the + and  operators as applying the operator to both x and y. Since the only nongiven variables of the formulas are ls and dr, we will calculate them and then apply the corresponding formula with the corresponding given constant. double length(point from, point to) set relTo = to  from return sqrt(relTo.x^{2}+relTo.y^{2}) double probability(bool isShot, point from, point to, point[] rivals) double ls,dr; set ls=length(from, to) set dr = calculateDr(from, to, rivals) if isShot return applyShotFormula(ls, dr) else return applyPassFormula(ls, dr)Now we need the calculation of dr function: double calculateDr(point from, point to, point[] rivals) double dr = 10^{200} //note here that making dr really big by default //makes the dr/(dr+1) term practically equal to 1 //if no rival can intercept for each r in rivals if canIntercept(from, to, r) dr = min(dr, perpendicularDistance(from, to, r)) return dr
Up to this point everything is easy and intuitive. Let's get to
the first problem: how far is a rival that we know we can intercept? double perpendicularDistance(pint from, point to, point r) set area = triangleArea(from, to, r) set base = length(from, to) return area * 2 / base double triangleArea(point p1, point p2, point p3) return abs(crossProduct(p2p1,p3p1))/2 double crossProduct(point p, point q) return p.x*q.yq.x*p.y About testing for ability of each rival to intercept the trajectory, as was discussed in the forums, it can be done with pure integer arithmetic, avoiding small precision errors. In general, when you need to test a boolean condition it's almost a must to use only integers; a small precision error can easily change true to false or false to true and that could further lead to much bigger precision errors (see the linked thread in the forums with a better explanation and discussion of this point). Let's see the triangle formed again. For a rival to be in position to intercept the trajectory, the two angles formed by the trajectory line and each of the lines that connect the rival with each of your players have to be less than or equal to 90 degrees. Testing this is equivalent to say that the dot product of the relative vectors is greater than 0 (this follows from algebraic definition of angle, that can be found in the link above). Following this reasoning, the code for this part is: //for this part we need the points to have integer coordinates or use //different points structures boolean canIntercept(point from, point to, point r) return dotProduct(fromto,rto) >= 0 and dotProduct(tofrom,rfrom) >= 0 int dotProduct(point p, point q) return p.x*q.x+p.y*q.y At this point we have left geometry behind and can easily build a lovely graph that has one node for each of our players and one node for the scoring place. Each pair of nodes has a connecting edge that is labeled with the probability of that pass or shot being succesful. What we need now is a path in that graph that goes from the starting player to the scoring place such that the product of the labels each traversed edge (the probability of the strategy represented by that path) is maximum. For some people its obvious that you can easily adapt any shortest path algorithm to solve this, simply changing minimum for maximum and adding for mutliplying. If you are not part of that group, or would like to reuse your prewritten Dijkstra, FloydWarshall or BellmanFord without modifying anything inside, see the following magical idea. First step: Build the minus logarithm graph. This graph is the same but each label l is transformed to log(l) (the base of the logarithm is not important).Second step: Find the shortest path from player 0 to scoring place in this new graph. Since this starts to sound too crazy, let's explain and continue after that. Shortest path in this new graph is a path in which the sum of the new labels is minimum. This sum, in terms of old labels, can be written as: (log(l_{1})) + (log(l_{2})) + ... + (log(l_{n})) where l_{i} are the labels in the original graph of each corresponding edge. From that expression we can derive the following: (log(l_{1})) + (log(l_{2})) + ... + (log(l_{n})) =  ((log(l_{1}) + log(l_{2}) + ... + log(l_{n})) = log( l_{1} * l_{2} * ... * l_{n}) Since this last expression was minimized (because we looked for a shortest path), that means that the opposite expression was maximized. And since the logarithm is an strictly monothonic increasing function the inside expression l_{1} * l_{2} * ... * l_{n} is maximal. To find it's value, simply take L = the length of the shortest path found, and calculate b^{L}, where b was the base used for logarithms (any positive base is ok). To see any shortest path algorithm work, think that since oringal labels lie on (0;1] interval, the logarithm is always nonpositive and the minus logarithm is therefore always nonnegative. After seeing this "magical" approach, maybe you are convinced that the initially mentioned approach of simply changing < for > and + for * works. If you are not, maybe you should. And if you don't think you should, come discuss in the forums. For an implementation you can see zhuzeyuan's code, its similarly modularized to this presentation (he uses Dijkstra and generates the labels of the graph on demand). To see the integer arithmetic in intercept ability test, see dskloet's code. 
