|
Match Editorial |
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.
In the stronger division the challenge phase brought down almost
half of the submissions, but this didn't really affect
the top of the division ranklist. In the end the equation was
clear: to finish on top, you had to solve all three tasks.
Twenty-one coders were able to solve all three problems, and
they all deserve congratulations for doing so. The top three
contained some of the usual suspects:
Petr won, followed by
andrewzta in second
and
Eryx in third.
The Problems
BinaryIncrementation
Used as: Division Two - Level One:
Value 250 Submission Rate 490 / 540 (90.74%) Success Rate 467 / 490 (95.31%) High Score wongiseng for 248.82 points (1 mins 57 secs) Average Score 209.28 (for 467 correct submissions)
Basically, there were three different approaches to this simple task.
Straightforward
To increase the number, we need to change all the trailing '1's into '0's,
and the preceding '0' into a '1'. This could be done using a simple loop --
if not for the case when the input string contains only '1's. In this case
the result will have one more character.
A simple way to handle this: Take the string representing a number N.
Add a leading zero. Change the string to represent N+1. If we still have a leading zero, remove
it.
Here's this approach in C++ code:
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 stepsThe 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 librariesDid 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:
Value 500 Submission Rate 380 / 540 (70.37%) Success Rate 75 / 380 (19.74%) High Score cax for 461.23 points (8 mins 22 secs) Average Score 291.60 (for 75 correct submissions)
Value 250 Submission Rate 402 / 413 (97.34%) Success Rate 230 / 402 (57.21%) High Score Petr for 247.03 points (3 mins 7 secs) Average Score 191.94 (for 230 correct submissions)
Let's start by writing the simplest solution possible.
Naive solution
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 64-bit 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 wayWhenever 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 wayLet 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*(99-Z) ≥ (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 ) / (99-Z) )
NewOperator
Used as: Division Two - Level Three:
Value 1100 Submission Rate 30 / 540 (5.56%) Success Rate 0 / 30 (0.00%) High Score null for null points (NONE) Average Score No correct submissions
First of all, let's find out what values we can get by computing A@B, where A and B are positive 32-bit integers. Remember that A@B = 5 * prod3(X) + first(X) * sum(Y) + smallest(Y). We get:
- prod3(X) is between 0 and 9*9*9, inclusive.
- smallest(Y) is between 0 and 9, inclusive.
- first(X) is between 1 and 9, inclusive.
- sum(Y) is positive and always less than 90.
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, K-th 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 pre-compute 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[dc-1];
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 && dc-k>=0; k++) prod3[x] *= D[dc-k];
}
}
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:
Value 500 Submission Rate 295 / 413 (71.43%) Success Rate 255 / 295 (86.44%) High Score Eryx for 487.64 points (4 mins 32 secs) Average Score 330.36 (for 255 correct submissions)
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.
However, there is a simple observation that will save us. The entire situation
is really quite symmetric. The probability of moving an element from one place
to some other place must always be the same, regardless of the indices assigned
to those places.
In other words, consider some fixed element. After t swaps it is enough to
distinguish between two cases: either the element is on its original place
or not. If it is not, than all possible places have to be equally likely.
Moreover, the probability that an element is on its original place
does not depend on the choice of the element.
Suddenly, instead of keeping arrayLength^2 probabilities for each step,
we see that it is enough to store a single probability.
Formally, let P(t) be the probability that the element from the place 0
is at the place 0 after t swaps. Clearly, for any other place the probability
that this element is there equals to Q(t) = (1 - P(t)) / (arrayLength - 1).
We are interested in the values P(swapCount) and Q(swapCount). How to compute them?
There are S = (arrayLength)*(arrayLength-1)/2 possible swaps in each step.
Out of them, T = (arrayLength-1)*(arrayLength-2)/2 leave the element 0 on its place,
and U = arrayLength-1 move it.
The event "after t swaps, our element is on the place 0" can be split into two
events: either it was there after t-1 swaps and remained there, or it came there
in the t-th swap.
The probability of the first event is (T/S) * P(t-1), the probability of the
second event is U * Q(t) * (1/t).
This was already enough to solve the problem. However, note that the recurrence
equation has a closed form solution.
Used as: Division One - Level Three:
Value 1000 Submission Rate 52 / 413 (12.59%) Success Rate 23 / 52 (44.23%) High Score andrewzta for 761.17 points (17 mins 4 secs) Average Score 519.05 (for 23 correct submissions)
This problem contained two separate parts. One was plainly in sight, the other
slightly hidden.
The obvious part is solving the game.
Playing around with small cases, analyzing the examples, or even writing a brute
force solution to compute some winning positions -- these are some of the ways you could discover the optimal strategy.
Once you get the right idea, the game is unbelievably simple: Let P be a position,
M the maximal number of pieces of one cake, and let C be the number of cakes
that have exactly M pieces left. The position P is winning if and only if
C is odd.
To prove this, we need to show two things:
-
From any losing position, all moves lead to a winning position.
This is clearly true. The player will eat from exactly one of the maximal cakes, thus their count changes from even to odd.
-
From any winning position, there is a move that leads to a losing position.
If we have 3 or more maximal cakes, this is similar to the previous case. The interesting situation is when there is exactly one maximal cake. If this happens, we count the second largest cakes. If their count is odd, reduce the maximal cake to this count of pieces. If their count is even, reduce the maximal cake to a smaller count. (Note that there may be many valid moves here.)
Clearly, we may select the cake and the number of pieces independently:
- The cake is always the lexicograpically smallest of the maximal cakes.
- For a losing position the number of pieces is 1.
- For a winning positition with more than one maximal cake the number of pieces is 1, again.
- For a winning position with one maximal cake and an odd count of second largest cakes, there is a unique correct number of pieces.
- Finally, for a winning position with one maximal cake and an even count of second largest cakes, the winning moves correspond to some interval [A,B].
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;
}
