JOIN
Get Time
statistics_w  Match Editorial
Archive
Printable view
 Discuss this match
SRM 313
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.

*Note for the admins: This was a joke. Please let me keep doing SRMs, I won't ruin them on purpose. I promise.

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 Problems

CyclesInPermutations rate it discuss it
Used as: Division Two - Level One:
Value 250
Submission Rate 414 / 469 (88.27%)
Success Rate 364 / 414 (87.92%)
High Score wilan for 248.24 points (2 mins 23 secs)
Average Score 196.95 (for 364 correct submissions)

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.

PrefixFreeSets rate it discuss it
Used as: Division Two - Level Two:
Value 500
Submission Rate 301 / 469 (64.18%)
Success Rate 196 / 301 (65.12%)
High Score hohosky for 485.93 points (4 mins 51 secs)
Average Score 345.27 (for 196 correct submissions)
Used as: Division One - Level One:
Value 250
Submission Rate 385 / 397 (96.98%)
Success Rate 344 / 385 (89.35%)
High Score gevak for 249.60 points (1 mins 8 secs)
Average Score 211.08 (for 344 correct submissions)

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 prefix-free has a less or equal number of elements that the largest subset of S - {t} that is prefix free. Let A be a prefix-free 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'.
2. A' has at least the same number of elements of A. This also follows clearly from construction because you substract at most one element and add exactly one element (because since A is a subset of S - {t}, A - {s} cannot already contain t).
3. A' is prefix free. Since A is prefix-free, there is no pair of distinct elements (x,y) such that x is a prefix of y. In A' the only pairs (x,y) that could be forbidden are the ones of the form (t,y) for some y (because all other pairs are not forbidden because both elements appear in A too). If a pair of the form (t,y) is forbidden, (s,y) is forbidden too, because being a prefix is a transitive relation. And (s,y) is in A, therefore is not forbidden, so (t,y) is not forbidden. In conclusion, A' has no forbidden pairs and therefore is prefix-free.

With 1, 2 and 3 proved, the initial proposition is demonstrated.

The straightforward implementation was following this pseudo-code: 

for each i in 0 .. words - 1
   for each j in i+1 .. words-1
      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.

ParallelProgramming rate it discuss it
Used as: Division Two - Level Three:
Value 1000
Submission Rate 119 / 469 (25.37%)
Success Rate 66 / 119 (55.46%)
High Score hohosky for 829.14 points (13 mins 29 secs)
Average Score 621.78 (for 66 correct submissions)

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 theory

The 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.
2. There is no cycle, in this case, we have a topological sort of the graph as output.
Let A[0], A[1], ... , A[N-1] be an array where A[i] is the number of the ith process in the topological ordering. The following pseudocode solves the problem: 

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 N-1
   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 theory

Here is the pseudocode: 

set N = number of processes
endTime = array of N integer elements
canWork = array of N boolean elements
for i = 0 to N-1
   canWork[i] = process i has any dependencies?
   if canWork[i]
      endTime[i] = time[i]

do
   set changes = false

   for i = 0 to N-1
      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 -1
The 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 self-explanatory: time[i] = 0 means process i is already terminated.

CrazyRunning rate it discuss it
Used as: Division One - Level Two:
Value 550
Submission Rate 19 / 397 (4.79%)
Success Rate 17 / 19 (89.47%)
High Score dmytro for 413.27 points (17 mins 36 secs)
Average Score 258.40 (for 17 correct submissions)

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 N-1 of length average(corridors[1],...,corridors[N-1]).

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:
sum over each list : prob(list)*length(list)

Here the length is the sum of twice the length of each mention of each corridor, with the exception of the first and last, which are added only once.

In this summation, all terms can be divided in groups of (N-1)! lists such that:

  • All have the same length
  • For any pair (p,q), there exists a permutation of N in which perm[0]=0 and all other elements can be in any order, such that if the permutation is applied to all elements of p, the resulting list is q.
This last property means that in each case the list is basically the same but each corridor is playing the part of some other corridor, with the special case of 0 (since all lists start with 0, we cannot make another corridor take its place because it will result in a list starting with a non-zero element).

Of course, all these lists have equal probability, so we can take the common factor out and
sum over each of the groups:
prob(anyListInTheGroup)*(sum over each member of the group: length(member))

Now, suppose we write all members of a group one below the other. Some columns contain pure 0s (because it is never transformed). The rest of the columns have (N-2)! times each of the N-1 other corridors. It's clear now than when summing the length of each member of the group, each corridor except corridor 0 contributes the same number of times, and therefore, as long as the sum of them is maintained constant, the actual values can be changed without changing the result. Replacing each one for the average, of course, maintains the sum constant.

Now we have a problem with 3 parameters:
N = size(corridors), c0 = corridors[0] and cr = average(corridors[1], corridors[N-1]).
From here on there are many different approaches, and using some math tricks can greatly reduce the coding. That depends on what you do better, coding or solving equations. I'll explain one intermediate approach.

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(N-2). 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:

  • Enter a visited corridor that is not corridor 0
  • Enter corridor 0 and then a different already visited corridor
  • Enter an unvisited corridor
  • Enter corridor 0 and then an unvisited corridor (both times getting back to the center)
Is easy to see that the 4 cases cover every possibility. In the first 2 you are in the same situation and in the last 2 you are in situation n-1, so the general expression for f is:
f(n) = p1*(cr*2+f(n)) + p2*(2*c0+2*cr+f(n)) + p3*(2*cr+f(n-1)) + p4*(2*c0+2*cr+f(n-1))
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:

  • p1 = (N-n-2)/(N-1), because there are N-n visited corridors, one is forbidden (the one we just came from) and one is corridor 0.
  • p2 = 1/(N-1) * (N-n)/N-1, because there is 1/(N-1) probability of entering corridor 0 and after doing that we have any of the visited nonzero corridors available.
  • p3 = n/(N-1), because John can enter any of the unvisited corridors.
  • p4 = 1/(N-1) * n/N-1, the same as p2 for corridor 0 and then it's possible to enter any unvisited corridor.
At this point, it's easy to check that p1+p2+p3+p4=1. If n=1 the "+f(n-1)" have to be replaced by a "-cr" because in those two cases John runs to the outer end of that last corridor and stops. This can be done by setting f(0) = -cr.

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(n-1)
   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(n-1), 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.

BasketballStrategy rate it discuss it
Used as: Division One - Level Three:
Value 950
Submission Rate 66 / 397 (16.62%)
Success Rate 47 / 66 (71.21%)
High Score ACRush for 658.42 points (20 mins 57 secs)
Average Score 452.23 (for 47 correct submissions)

This problem is pretty straightforward if you know a little about many aspects of programming. You needed some, but not much, of:

  • Probabilities
  • Graph theory
  • Math
  • Integer or algebraic geometry
  • Floating point or euclidian geometry
Let's take it one step at a time, first what was obviously needed was to know the exact probability of an arbitrary pass between two of your players or an arbitrary shot. This two things were similar, with the only difference of the final formula.

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 non-given 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.x2+relTo.y2)

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 = 10200
   //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?
If we see the 3 points as a triangle, the perpendicular line that passes through the rival point is one height, and since we can easily calculate the base corresponding to that height (because is the distance of the pass) and also the area of the triangle (using cross product), we have it all: 

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(p2-p1,p3-p1))/2

double crossProduct(point p, point q)
   return p.x*q.y-q.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(from-to,r-to) >= 0 and dotProduct(to-from,r-from) >= 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, Floyd-Warshall or Bellman-Ford 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(l1)) + (-log(l2)) + ... + (-log(ln))
where li are the labels in the original graph of each corresponding edge. From that expression we can derive the following:
(-log(l1)) + (-log(l2)) + ... + (-log(ln)) =
- ((log(l1) + log(l2) + ... + log(ln)) =
-log( l1 * l2 * ... * ln)
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
l1 * l2 * ... * ln
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 non-positive and the minus logarithm is therefore always non-negative.

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.

Author
By soul-net
TopCoder Member