Wednesday, February 7, 2007 Match summary
Division 2 saw a very tough hard problem, worth 1100 points. Ultimately the
problem proved too hard, and none of the 30 submitted programs passed.
This meant that there were only three sources of "point income" left:
the easy, the medium, and the challenge round. To place at the top, one had
to use each of them. In the end, the division win went to
janakporwal.
Digibomb came in second
and
fegla followed in third.
The ProblemsBinaryIncrementationUsed as: Division Two  Level One:
Basically, there were three different approaches to this simple task.
public string plusOne (string x) { x = "0" + x; for (int i=x.size()1; i>=0; i) if (x[i]=='1') { x[i]='0'; } else { x[i]='1'; break; } if (x[0]=='0') x = x.substr(1); return x; }Break it into simple steps The main idea of this solution: convert the input to a number, add 1, and convert the number back to a string. C++ code: public string plusOne (string x) { int X = 0; // convert to a number for (unsigned i=0; i<x.size(); i++) { X *= 2; X += (x[i]'0'); } // add 1 X++; // convert back string res = ""; while (X) { res += ('0'+(X%2)); X /= 2; } reverse( res.begin(), res.end() ); return res; }Know your libraries Did you know that Java's BigInteger class can also work with bases other than 10? If yes, you could quickly write a flawless solution: public String plusOne (String x) { BigInteger X = new BigInteger(x,2); return X.add(BigInteger.ONE).toString(2); }ImprovingStatistics Used as: Division Two  Level Two: Used as: Division One  Level One:
Let's start by writing the simplest solution possible.
int display(int played, int won) { return (won * 100) / played; // integer division rounds down } int howManyGames (int played, int won) { if (played == won) return 1; int currentDisplay = display(played,won); for (int g=1; ; g++) if (display(played+g,won+g) > currentDisplay) return g; }The solution above will not pass, and there are three different bugs. Bug 1. The display() function contains an overflow, won * 100 may not fit into an int. The easiest fix is to use 64bit integers: int display(int played, int won) { return (won * 100LL) / played; // integer division rounds down }Bug 2. The solution will time out. The worst possible valid input case: played = 1,000,000,000, won = 980,000,000. In this case we need 1,000,000,000 games to change the displayed value. Bug 3. The solution doesn't work. The tricky case is that once the displayed value is 99%, it will never be 100%, and thus the answer in such a case shall be 1. There is an elegant way how to avoid bug 3 without even realizing that the tricky case is there. The problem statement stated that the answer is always less than 2,000,000,000. Thus at the beginning of our program we simply check whether 2,000,000,000 wins changes anything. If not, we return 1. Fixing bug 2 the hacker's way Is trying 1,000,000,000 values too slow? Then what about trying the possible answers with step 1,000 first, and only when we get close switch to step 1? C++/Java code: int howManyGames (int played, int won) { int currentDisplay = display(played,won); if (currentDisplay >= 99) return 1; int g; for (g=1; ; g+=1000) if (display(played+g,won+g) > currentDisplay) break; // We already crossed the boundary. // Now we return one step back and find its exact position. g=1000; for ( ; ; g++) if (display(played+g,won+g) > currentDisplay) return g; }Fixing bug 2 the programmer's way Whenever we can write a solution similar to the one above, there is always a solution that is faster and more elegant: binary search. There were two variations of this approach. The easier way was to note that 2*10^9 is an upper bound on the value we seek. But even if we didn't know the upper bound, only that it exists, binary search would still be possible. In the first phase, try g=2^0, 2^1, 2^2, ... until you find one that is large enough to serve as an upper bound for the rest of the search. C++/Java code of the second variation: int howManyGames (int played, int won) { int currentDisplay = display(played,won); if (currentDisplay >= 99) return 1; long minG = 0, maxG = 1; while (display(played+maxG,won+maxG) == currentDisplay) maxG *= 2; while (maxG  minG > 1) { long midG = (maxG + minG) / 2; if (display(played+midG,won+midG) == currentDisplay) minG = midG; else maxG = midG; } return maxG; }And finally, the mathematician's way Let Z be the currently displayed value. We have to find the smallest g such that: floor( 100*(won+g) / (played+g) ) ≥ Z+1. As Z is an integer, we may omit the floor function. Solving for g, we get: g*(99Z) ≥ (Z+1)*played  100*won The value on the right side is always positive. Thus for Z ≥ 99 the inequality has no solutions. If Z < 99, we may divide and we find out that the smallest integer solution is: g = ceil( ( (Z+1)*played  100*won ) / (99Z) ) NewOperator Used as: Division Two  Level Three:
First of all, let's find out what values we can get by computing A@B, where A and B are positive 32bit integers. Remember that A@B = 5 * prod3(X) + first(X) * sum(Y) + smallest(Y). We get:
The fact that we can only create less than 5,000 different values suggests that we may generate them all, and then check whether the goal is among them The tricky part is to avoid doing unnecessary work. Let the distance of a number be the smallest count of @s necessary to create it. We will generate the numbers in increasing distance order. Suppose that we already generated all the numbers that could be created using less than K @s. How to generate the numbers that require exactly K @s? When creating such a number, let X and Y be the values combined in the last, Kth step. If the distance of X is d1 and the distance of Y is d2, then the distance of (X@Y) is at most (d1+d2+1). Our program will work as follows: First, we precompute all the unary functions from the problem statement. (This is not really necessary, we could compute them when needed. I chose this way to be able to split my code into smaller parts that are easier to explain.) #define MAXIMUM_INPUT 1012345 #define MAXIMUM_OUTPUT 6000 int sum[MAXIMUM_INPUT], prod3[MAXIMUM_INPUT], smallest[MAXIMUM_INPUT], first[MAXIMUM_INPUT]; int compute(int X, int Y) { return 5 * prod3[X] + first[X] * sum[Y] + smallest[Y]; } void init() { int D[20]; for (int x=1; x<MAXIMUM_INPUT; x++) { int tmp = x, dc = 0; while (tmp) { D[dc++] = tmp%10; tmp /= 10; } first[x] = D[dc1]; sum[x] = 0; for (int i=0; i<dc; i++) sum[x] += D[i]; sort(D,D+dc); smallest[x] = D[0]; prod3[x] = 1; for (int k=1; k<=3 && dck>=0; k++) prod3[x] *= D[dck]; } }Now we will generate the reachable numbers. For each of them the vector "best" contains its distance, and for each k "sequence[k]" contains a list of all the numbers that have the distance exactly equal to k. int minimumCount(int x, int goal) { if (x==goal) return 0; init(); vector<int> best(MAXIMUM_OUTPUT,987654321); vector< vector<int> > sequences( MAXIMUM_OUTPUT ); sequences[0].push_back(x); // try all possible distances for (int distance=1; distance<=MAXIMUM_OUTPUT; distance++) // for each of them, try all possible distances of one element for (int d1=0; d1<distance; d1++) { int d2 = distance  1  d1; // once we fixed the distances, try all possible // pairs X, Y of items having these distances for (unsigned i=0; i<sequences[d1].size(); i++) for (unsigned j=0; j<sequences[d2].size(); j++) { int X = sequences[d1][i]; int Y = sequences[d2][j]; int Z = compute(X,Y); if (best[Z] > distance) { best[Z] = distance; sequences[distance].push_back(Z); } } } if (goal >= MAXIMUM_OUTPUT) return 1; if (best[goal] == 987654321) return 1; return best[goal]; }RandomSwaps Used as: Division One  Level Two:
At first glance, this seems like an ordinary DP problem. Let P(t,a,b) be the probability
that after t swaps the element from index a will move to index b. We can write a
simple recurrence equation and... and then we read the constraints.
It seems that the above solution will be too slow.
Used as: Division One  Level Three:
This problem contained two separate parts. One was plainly in sight, the other
slightly hidden.
Clearly, we may select the cake and the number of pieces independently:
int digits(int x) { return (""+x).length(); } String lexSmallest(int min, int max) { if (digits(min)==digits(max)) return ""+min; String cand1 = ""+min; String cand2 = "1"; for (int i=0; i<digits(min); i++) cand2 += "0"; if (cand1.compareTo(cand2) < 0) return cand1; return cand2; } 
