Saturday, February 4, 2006 Match summary In Division 1 we saw a match dominated by coders from Poland. During the coding phase monsoon took the lead with the fastest submission on the hard problem. However, his solution to the easy problem was successfully challenged and in the end of the challenge phase kedaizd was on the top of the division summary. But the system tests changed the results once again when kedaizd lost his easy problem too. In the end monsoon won the match, with marek.cygan in second and kedaizd in third. Thanks to twelve successful challenges natori was able to take the fourth place without solving the hard problem. Division 2 had a pretty tough round. The medium problem seemed to be much easier than it really was, and the hard problem was... well, hard. In the end, only two coders got the hard problem right, and what's worse, different mistakes claimed all submitted solutions to the medium problem. The final results were determined by the challenge phase. The first two places were safely taken by the two coders who solved the hard problem, zwdant and Rahenri. ZUTI made seven successful challenges and finished third. The ProblemsCustomerStatisticsUsed as: Division Two  Level One:
A straightforward way how to solve this task is to sort the customer list and then in one loop count the number of occurences of each name. See Rahenri's solution for an implementation of this approach. Another possibility is to use some library data structure, such as TreeMap in Java or map in C++. The advantage of this approach is that there are less special cases to consider, and thus less chances to make a mistake. #define FOREACH(it,cont) for (it=(cont).begin(); it!=(cont).end(); ++it) vector<string> reportDuplicates (vector<string> customerNames) { map<string,int> occurs; // count the number of occurences for each customer for (unsigned i=0; i<customerNames.size(); i++) occurs[ customerNames[i] ]++; vector<string> result; // process all records in the map "occurs", each time we have a duplicate, report it FOREACH(it,occurs) { if (it>second > 1) { // more than one occurence stringstream sout; sout << (it>first) << " " << (it>second); result.push_back( sout.str() ); } } return result; }TwoEquations Used as: Division Two  Level Two: Used as: Division One  Level One:
I admit that this problem was nasty. Really nasty. And while it was meant to be a tough lesson that being careful pays off, I didn't expect it to be this hard. Thus I decided that in this case explaining the idea of the solution simply isn't enough. I will start this editorial with some thoughts on how to tackle problems like this one. First and most important, don't reinvent the wheel! If you know that a problem is both classical and tricky, it has been solved correctly oh so many times long before you tried to solve it in the SRM. Don't be afraid to consult online references such as MathWorld, or even use Google to look for a discussion on the topic in question. Only when you are really left "on your own", start working out all the tricky details. Again, don't be afraid. This time, don't be afraid to put away the keyboard and grab a pen and a paper. Work out all the necessary details before you start coding, make sure you didn't forget anything, doublecheck your thoughts. Speed does not help if your solution fails.
If the problem contains different types of work, start with coding the simple, mechanical
parts. In this case, the first step should be parsing the input. The simplest way is to
split the equation as follows: Now we can get to the important part, solving the equations. First of all, note that an equation "0*X + 0*Y = c" has no solutions for c≠0, and for c=0 each pair (X,Y) is a solution. Now suppose that we have an equation "a*X + b*Y = c" such that (a,b)≠(0,0). The set of solutions of each such equation corresponds to a line in the XY plane. (More exactly, if b≠0, the line is the graph of the function Y = (a/b)*X + (c/b), otherwise it is a vertical line with X = c/a.) The first outline of our algorithm:
Hopefully you now noted that we can't swap steps 1 and 2. The second step depends on the first one, we have to be sure that the other equation is solvable. Swapping these two steps was a very common mistake in the SRM. We are left with the case that the solutions correspond to lines. Again, there are three cases:
There are different possibilities how to distinguish between these cases, I prefer vectors. It can be easily seen that the vector [a,b] is perpendicular to the line determined by "a*X + b*Y = c". Thus: (the lines "a*X + b*Y = c" and "d*X + e*Y = f" are parallel) iff (vectors [a,b] and [d,e] are parallel) iff (their vector product aebd is zero). In the case that the lines are not parallel, we can find the one solution, e.g., by elimination: If we multiply the first equation by (d), the second one by a, and add the results together, we get: "Y*(aebd) = (afcd)". Similarly, we can multiply the first equation by e, and the second one by (b), we get: "X*(aebd) = (cebf)". Clearly, as (aebd) is not zero, we just found the unique solution: X=(cebf)/(aebd), Y=(afcd)/(aebd). We only have to simplify it and print it. If the lines are parallel, we have to tell whether they are identical, in other words whether one of the equations is a multiple of the other one. This can be simply done by checking whether the vector product of [a,b,c] and [d,e,f] is zero. (If you are not comfortable with vectors, you can substitute X=0 or Y=0 into the first equation, compute one solution of the first equation, and check whether it satisfies the other equation.) A tricky solutionNote that in the general case when there is one solution, the values of X and Y have (before the reduction) the same denominator. Also, it can be shown that for the allowed input values the magnitude of the denominator and also the magnitudes of both numerators don't exceed 200. Thus, let S = { u/v ; 200≤u≤200, 1≤v≤200 }. We already know that if the system of equations has exactly one solution, both X and Y for the solution lie in S. Also, it can easily be shown that any valid equation other than "0*X + 0*Y = c" for c≠0 has more than one solution in S. It follows that we can simply write three nested loops to check all "candidates", and in the end count the solutions we found. FixedSizeSumsUsed as: Division Two  Level Three:
This was a pretty straightforward dynamic programming problem. With a different (easier) medium problem I would expect that more coders should be able to solve this one. The combinatorial object described in the problem statement is called integer partitions. In this case we are interested in partitions with a fixed number of elements. The common trick in almost all combinatorial problems is to generate the answer sequentially. In this problem, we can start by asking the question: what is the first element of the partition? To answer this question quickly, we have to count the partitions. In this case there are more suitable ways of doing it, we will present one of them. Let C(N,K,L) be the count of partitions that have K elements that sum up to N, and the first (largest) element is L. For example, for N=8 and K=3 we have C(8,3,1)=0, C(8,3,2)=0, C(8,3,3)=1, C(8,3,4)=2, C(8,3,5)=1, C(8,3,6)=1, C(8,3,7)=0, and C(8,3,8)=0. If we knew the values C(N,K,L) for all L, we could easily find the first element of the partition we seek: simply start with L=N and decrease it until you find enough partitions. The rest of the partition can be determined in a very similar way. Note that the rest of the partition is a partition of NL into K1 elements, where the first element can range from 1 to L. Moreover, we can easily compute the new index of this smaller partition. For example, for N=8, K=3 and index=3 we have:
Now we are left in a situation where N=4, K=2, index=1 and the last element was 4.
The remaining question is how to compute the values C(N,K,L). The idea behind the answer will be remarkably similar to the ideas used above. Look at any partition of N into K elements such that the first element is L. If we remove the first element, we get a partition of NL into K1 elements such that the first element is at most L. This gives the general recurrence equation: C(N,K,L) = C(NL,K1,1) + C(NL,K1,2) + ... + C(NL,K1,L) We may use dynamic programming or memoization to compute all the values C(N,K,L). Afterwards, we determine the elements of the sought partition one by one. C++ code follows. int C[160][160][160]; string kthElement(int sum, int count, int index) { memset(C,0,sizeof(C)); // fill in the table, first the base case... for (int i=1; i<=sum; i++) C[i][1][i]=1; // ... then the general case for (int c=2; c<=count; c++) for (int s=c; s<=sum; s++) for (int l=1; l<=sc+1; l++) for (int k=1; k<=l; k++) C[s][c][l] += C[sl][c1][k]; // count all partitions of sum into count parts int all = 0; for (int i=1; i<=sum; i++) all += C[sum][count][i]; // if there are not enough of them, return an empty string if (all <= index) return ""; stringstream sres; sres << sum << "="; int remains = sum, last = sum; for (int i=0; i<count; i++) { // determine the ith element of the partition: // start with the value of the previous element, // decrease it until you find enough partitions int element = last+1, seen = 0; while (seen <= index) { element; seen += C[remains][counti][element]; } // output the new element and update the current state sres << (i?"+":"") << element; index = (seen  C[remains][counti][element]); remains = element; last = element; } return sres.str(); } Exercise. The time complexity of this solution is Theta(sum^3 * count). Find a way to improve it to Theta(sum^2 * count). MooresLawUsed as: Division One  Level Two:
There were essentially two different ways of solving this problem. In both of them, we will start
by formalizing the problem statement. Suppose that we have a task that would take Y years to
complete on a computer bought today. Let
Our goal is to find a nonnegative waiting time w such that the total time of the waiting and
the computation is minimal. This time can be computed as The calculus approach
We want to find the minimum of the function Why almost? First, we should check that this is really a local minimum. This should be clear from the nature of the problem, formally it can be done by computing the second derivative in that point. The second issue is more important. In this problem we are only interested in nonnegative values of t (we can't start the computation sooner than now). If the function g reaches its minimum for a negative value of t, the minimal value for nonnegative values of t will clearly be achieved for t=0. (This could be discovered by carefully testing your solution on boundary cases. If you forgot to check for negative t, for Y=1 you got a result of less than 0.5 years. This is obviously wrong, as even a computer bought after half a year still needs more than 0.5 years to complete the task.) The numeric approachWe will now describe a method of finding the minimum of a function known under the name ternary search. First, we will introduce the method in general. Let [a,b] be a closed interval and let f be a function defined on this interval. Moreover, f must be such that there is a point c in the interval [a,b] such that f is decreasing on [a,c] and increasing on [c,b]. We want to find the values c and f(c), i.e., the minimum of f on the given interval. We will approximate c by repeatedly shrinking the interval in which we search. Each iteration looks as follows:
Why does this method converge on the value we seek? Note that in the third step we drop one third of the search interval. We have to prove that it doesn't contain the point where f is minimal. For the first case: suppose that c<x. But this means that on the whole [x,y] f has to be increasing, and thus we must have f(x)<f(y). As this is not the case, we know that c≥x, and thus we may really drop the interval [a,x) from our search. (If you are not sure whether you understand it correctly, try drawing a picture of the situation, and/or read this thread with a more detailed explanation.) Note that if originally ba=L, then after N iterations we have a search interval of the length L*(2/3)^N. Already for N=60 this is approximately 3*L*10^(11). In our current problem, we want to find the minimum of the function g (defined above) on the interval [0,infinity). Clearly it is enough to search in the interval [0,Y], as we know that waiting for more than Y years won't give us an optimal solution. And we can easily verify (or guess) that the function g satisfies the conditions for ternary search to apply. To find the solution we simply iterate the search until we have a result that's precise enough: double speed(double delay) { return Math.pow(2.0,delay / 1.5); } double necessaryTime(double taskLength, double delay) { return delay + taskLength / speed(delay); } public double shortestComputationTime(int years) { double taskLength = years; double mn = 0, mx = taskLength; for(int i=0; i<1000; i++) { double t1 = mn*2/3 + mx/3; double t2 = mn/3 + mx*2/3; if (necessaryTime(taskLength,t1) < necessaryTime(taskLength,t2)) mx=t2; else mn=t1; } return necessaryTime(taskLength,mn); } The Eryx approachGuess the form of the function g and use the values from the problem statement to find the constants such that g interpolates them. See Eryx's solution. CoinGameUsed as: Division One  Level Three:
Also this problem admitted several different approaches to solving it. We will present some of them. We will concentrate on the main problem: given two sequences, determine the probability that the first one will occur earlier than the second one. The rest of the problem is easy. Clearly we can't afford to repeatedly throw coins and wait for HHTHTHTTTH to appear, we have to think of something more clever. Observation 1. Let L be the length of the given sequences. Suppose that we have a game in progress and that at least L throws were already made. Then the probability that the first player will win depends only on the outcome of the last L1 throws. This observation leads to the conclusion that any allowed game can be in one of roughly 500 different states. This number is still quite large, we have to think of something better. We will start with an example. Observation 2. Suppose that the first player waits for HHTHTHH, and the second one waits for HHHTHHH. Let p be the probability that the first player wins given that the last six throws were TTTTTH. Let q be the probability that the first player wins given that the last six throws were HTTTTH. Then p=q. This is because in the current situation the first throw is useless, no player may use it in his sequence. How to formalize the above observation? Let P be the set containing all prefixes of the two input strings. Then the state of the game is uniquely determined by the longest element of P that is the suffix of the sequence of previous throws. In other words, the state of the game tells us which player may use more previous throws, and how many of them. (For the example in Observation 2, the state of the game corresponds to the string H – no player can use earlier throws to form his sequence. If the last six throws were TTHHHT, the state would be HHHT.) We only have roughly 20 states in the game. Let's look at what happens to the state of the game when we throw a next coin. For any string S let crop(S) be the longest suffix of S that is in P. Thus if S contains enough previous throws, crop(S) is the corresponding state. If we are in the state Z (that doesn't correspond to either player winning the game), after the next throw we will move either to crop(Z+'H'), or to crop(Z+'T'). Using this information we may find the probability that player 1 wins as follows: We will simulate the game and for each state keep the probability that after the current number of throws we are in this state. We can easily build a P times P matrix A such that multiplying the vector of probabilities by A corresponds to one step of our simulation. But then 2^200 steps of the simulation correspond to multiplying by B=A^(2^200). The matrix B can be computed using 200 matrix multiplications using repeated squaring. And 2^200 coin throws is quite a lot. Gaussian eliminationThe above approach alone probably wasn't fast enough to solve the largest inputs, however, with some time spent on optimizing your solution it could be made fast enough to (barely) pass the system tests. However, if you see a simulation like this one, you should always ask: Can I compute the exact solution the simulation converges to? Usually, the answer is positive. For each state (i.e., for each prefix Q in P) let prob(Q) be the probability that from the state Q the first player will win the game. We want to know the value prob(""), and we can get it by computing all the values prob(Q) at the same time. For each state we can write one linear equation that describes what happens when we throw a coin in this state. As an example, consider the situation from Observation 2, the players wait for HHTHTHH and HHHTHHH, respectively. For the state HHH we get the equation: prob("HHH") = 0.5*prob("HHH") + 0.5*prob("HHHT"). For the state H we get: prob("H") = 0.5*prob("HH") + 0.5*prob(""). For the state HHTHTH we get: prob("HHTHTH") = 0.5 + 0.5*prob(""). In this way we construct a set of P linear equations with P variables. These equations have an unique solution that can be found using Gaussian elimination. A (somewhat numerically stable) piece of code follows. // initialize the matrix with C = P rows double A[][] = new double[C][C+1]; for (int i=0; i<C; i++) for (int j=0; j<=C; j++) A[i][j] = 0.0; // fill in the equations for (int i=0; i<C; i++) { if (P[i].equals( firstString )) { A[p][p]=1.0; A[p][C]=1.0; continue; } if (P[i].equals( secondString )) { A[p][p]=1.0; A[p][C]=0.0; continue; } String T1 = crop( P[i]+'H' ), T2 = crop( P[i]+'T' ); int x1 = getIndex( P, T1 ), x2 = getIndex( P, T2 ); A[p][p] += 1.0; A[p][x1] = 0.5; A[p][x2] = 0.5; } // create a triangular matrix for (int col=0; col<C; col++) { double max=1e12; int kde=1; // select a row where the element has the largest magnitude // note that for the first row, the first column will be selected for (int row=col; row<C; row++) { if (A[row][col] > max) { max=A[row][col]; kde=row; } if (A[row][col] > max) { max=A[row][col]; kde=row; } } // won't happen here, we have a regular set of equations if (kde==1) return 47; // swap the selected row into its proper place if (kde>col) for (int c2=col; c2<=C; c2++) { double x=A[col][c2]; A[col][c2]=A[kde][c2]; A[kde][c2]=x; } if (A[col][col]<0) for (int c2=col; c2<=C; c2++) A[col][c2]=A[col][c2]; // subtract a suitable multiple of our row from the other ones for (int row=col+1; row<C; row++) { double mul = A[row][col] / A[col][col]; for (int c2=col; c2<=C; c2++) A[row][c2] = mul * A[col][c2]; } } // substitute the values for (int col=C1; col>=0; col) { A[col][C] /= A[col][col]; for (int row=0; row<col; row++) A[row][C] = A[row][col] * A[col][C]; } Even more mathsThe game is known under the name "Penney ante", and it is described e.g. in chapter 8.4 of the book Concrete Mathematics by Graham, Knuth and Patashnik. The probability that the first player wins can be computed in an even more simple way, by simply examining the patterns. Look at monsoon's solution for a clean implementation of this solution. 
