Saturday, February 19, 2005 Match summary
SRM 231 gave division 2 coders a welcome reprieve from the
difficulties of the last few matches. chrbanx, in his
10^{th} SRM beat out second place Mojito1 by a comfortable
margin, and solved all three problems in a little over 26 minutes.
The best newcomer was masti who took 8^{th} place. The ProblemsGolfScoreUsed as: Division Two  Level One:
Given the par values of an 18hole golf course and the score obtained on each hole, expressed in relative terms such as "bogey" and "birdie", we are to compute the total score achieved by a player. There is one scoring phrase that is not relative, namely "hole in one". Coding a successful solution depends partly on dealing with this special case.
The other challenge is to find a way of translating the scoring
phrases into their numerical values. The simplest approach is to use
Consider, instead, that we can look up the scoring phrase in an array and use its position to directly calculate a numerical value. In this array, the scoring phrases should be listed in order, say from lowest to highest as below. We then initialize the total score to zero. When iterating over the holes, we single out the "hole in one" case and immediately increment the score by one. public int tally(int[] parValues, String[] scoreSheet) { String[] scores = {"triple bogey", "double bogey", "bogey", "par", "birdie", "eagle", "albatross"}; int tot = 0; for (int i = 0, j; i <18; i++) { if (scoreSheet[i].equals("hole in one")) { tot++; continue; }
There are predefined functions in most languages to quickly find an
element in a sorted array, but a for (j = 0; j <7; j++) if (scoreSheet[i].equals(scores[j])) break; tot += parValues[i]j+3; } return tot; } If the scoring phrases were not mapped in arithmetic progression to their values, we would probably want to use an associative array of some kind, such as a map or a hash, to look up the integer corresponding to each string. StitchUsed as: Division Two  Level Two: Used as: Division One  Level One:
In reality, stitching two images together is a bit more complicated than this problem might
suggest. If you were to use the algorithm it outlines, the stitched
region would probably look rather blurry, especially in the middle
part where it was closest to an even average. That said, the problem
was pretty straightforward, and relied mostly on your ability to
handle the indexes. Used as: Division Two  Level Three:
This is a classic sort of greedy problem. The answer, which many coders found, is to simply sort the programs by elements of B in descending order. That way the ones that have to run longest get started earliest. To prove that this is optimal, imagine a different ordering. In that ordering there must be an inversion  a pair of programs in the ordering that are adjacent and whose times in B are not ordered as the sorting method would order them. It is easy to prove that swapping these two programs will not make the total time any longer. Therefore, whenever there is an inversion, you can always swap the inverted programs, and the time will get no worse. Since swapping things that are out of order is one way to sort them (bubble sort), we know that by repeatedly swapping inverted elements, we will eventually get to the sorted list, and the total time will be no more than it was when we started. Hence, the other ordering is no better, and the sorted order is optimal. LargeSignTestUsed as: Division One  Level Two:
Finding the summation is pretty trivial for small inputs. But with N
up to 1,000,000, the naive algorithm using doubles will run into all
sorts of problems, as doubles can only go up to about 10^{300}
 much less than 2^{1,000,000}. Hence, Most coders solved
this problem in one of two ways. They either used logarithms, or else
cleverly scaled things as they went.
log((N choose i) / 2^{N}) = log(N choose i)  log(2^{N}) = log(fact(N))  log(fact(i))  log(fact(Ni))  N * log(2)Each of those values is relatively small, but not so small that it will underflow, and will fit easily within a double, with a reasonable degree of accuracy. The largest is log(fact(N)), but even it is pretty small, compared to 10^{300}. So, now that we've calculated the log of the term, all that remains is to take exp(x), where x is the above equation. This gives you the term in the summation with enough accuracy to solve the problem by simply adding up all the terms. The other approach requires a bit less math, but a bit more cleverness, in my opinion. Since the denominator is a constant, we can factor it out, and take the summation of just the numerator, and then divide at the end. We can also divide as we are calculating the summation, provided we are careful about how we do it. One important observation to this approach is that a term in the summation is related to the previous term. Working out a bit of simple algebra, we find the following recurrence, where f(i) is the i^{th} numerator: f(i) = f(i1) * (Ni+1) / iNow, we know that we have to divide by 2 a total of N times (the 2^{N}). So, lets simply start taking the summation of the numerator, and when the numbers start to get very big, divide by 2 to keep things reasonable. When we divide the current sum by 2, we also divide f(i) by 2, so that everything has been divided by 2 the same number of times. Once we are done with the summation, we will probably have to divide by 2 some more, so that we have done so N time in total: double f = 1, ret = 1, k = 0; for (int i = 1; i <= Math.min(K,NK); i++) { ret += f = f * (Ni+1) / i; while( ret > 2) { ret /= 2; f /= 2; k++; } } while ( k++ < N1 ) ret /= 2;Mixture Used as: Division One  Level Three:
If you know what linear programming is, this problem was a rather
elementary application of that. However, solving a
linear programming problem is quite hard, and the algorithm is pretty
complicated. Luckily, there is another way that only requires you
know how to solve a system of linear equations. Ax+By+Cz+... = Dwhere A, B, C, and D are constants, and x, y and z are variables. A system of linear equations is just a bunch of these. If you have enough linear equations, you can often solve them and find the values of the variables. For example, consider the following two equations: 5x + 3y = 13 (1) 7x + 2y = 16 (2)The only values of x and y that satisfy both equalities are 2 and 1, respectively. But how do we find these values programatically? First off, notice that you can always multiply both sides of an equality by a constant, and it will not change the equality. Furthermore, you can subtract one equation from another equation. 5x + 3y = 13 (1) 7x + 2y = 16 (2) x + (3/5) y = 13/5 (3) divide both sides of (1) by 5 (7x  7x) + (2y  (21/5)y) = 16  (91/5) (4) multiply both sides of (1) by 7 and subtract the result from (2) (11/5)y = (11/5) (5) simply (4) y = 1 (6) divide boh sides of (5) by 11/5 x + (3/5) y  (3/5) y = 13/5  3/5 (7) subtract 3/5 times (6) from (3) x = 2 (8) simplify (7)You can apply the same basic technique to an arbitrary number of linear equations. The idea is that you are iteratively removing a single variable from every equation except one. Typically, this is done by storing the equations in a matrix, where each row in the matrix represents a single equation. For example, the above system would be stored in the matrix as: 5 3 13 7 2 16Once the equations are in a matrix, you can solve them like this: for(int i = 0; i<min(ROWS,COLS1); i++){ select a row j where M[j][i] != 0 for(int k = COLS1; k>=i; k)M[j][k] = M[j][k] / M[j][i]; for(int k = 0; k<ROWS; k++){ if(k!=j){ for(int m = COLS; m>=i; m){ M[k][m] = M[k][m]  M[j][m] * M[k][i]; } } } } sort the rows in the order they were selected the answer is in the last column of M, if using it as the answer gives the correct resultNote that if we fail to find a value of j during an iteration of our loop it means that if the equation can be solved, it may be solved with any value of the j^{th} variable, and so there is more than one solution. Also, when there are less variables than rows, we can not be sure that the above steps will yield a solution, as there may be no solution. Hence, you need to double check the answer (the last column) before assuming it is correct. In our problem, the set of linear equations follow easily from the text. For each chemical there is an equation, and each variable represents the amount of a mixture to purchase. However, this doesn't quite solve our problem. Very often, some of the values of the variables are negative when you solve the system of equations, and we can't purchase a negative amount of a mixture. Furthermore, it is likely that there is more than one way to solve the problem, and we want to find the cheapest. To solve both of these problems at once, you need to think about the form of all the possible solutions. Every solution to the system of equations can be found by starting with the solution that you need to return, and then increasing the amount of some of the mixtures, while decreasing the amount of some of the other mixtures. We can represent this with vectors. For example, if there are 3 mixtures and we could increase the amount of the first mixture by 1 while decreasing the amount of the second mixture by 2, and obtain the same result, this would be represented as a vector [1 2 0]. If one solution to the problem were [2 3 1], then the general solution would have the form [2 3 1] + x*[1 2 0], for some x. In fact, the solution will always by of the from C + x_{1}*v_{1} + x_{2}*v_{2} + ... where C represents one solution, and each v_{i} is a vector, while x_{i} is an arbitrary variable. How does all this help us find the right solution? Well, associated with each of the v_{i}'s above is a cost, cost_{i}. This cost is positive if a positive value of x_{1} will increase the cost in relation to the solution C, and negative (or 0) otherwise. Notice that if cost_{i} is positive, we want to make x_{i} as negative as possible. On the other hand, if cost_{i} is negative, we want to make x_{i} as large as possible. However, once we have a valid solution where the amounts of each mixture are nonnegative, we can only increase the values of x_{i} so far before increasing them any further would result in negative amounts of mixtures. The point at which we must stop increasing (or decreasing) x_{i} is when we are no longer purchasing any of one of the mixtures, whose quantity we would have to decrease. So, in general, the optimal solution will be found when changing any of the x_{i} values would either increase the cost or make the purchase amount of a mixture negative. Finally, this brings us to our algorithm. Rather than worrying about all the x_{i}s and v_{i}s, we can just try all possible subsets of mixtures, and start solving our system of equations using just those mixtures. We know that if an x_{i} is important to the solution, then it will completely eliminate at least one mixture from the solution. By doing this elimination ourselves, in an outer loop, we no longer need to bother with x_{i}, as the x_{i} is not part of the solution when the zeroed mixture is not part of the subset. So, the final algorithm is: cost = INF foreach subset of mixtures construct system of linear equations from subset solve system if there is exactly one solution cost = min(cost, cost of that solution) end end return costAs far as the runtime goes, there are at most 2^N subsets, and the algorithm to solve the systems of equations takes N^3, so the total runtime is O(2^N*N^3), plenty small for N=10. One final note about precision: you don't need to do anything fancy, as the terms in the matrix start out small enough that using an epsilon of around 1E11 for all your calculations will make things work out fine. If you were really concerned, you could use a fraction class, and the numerator and denominator would never overflow a 64 bit integer. 
