Can you tell who wins and how to play this game without using a computer to analyze all possible positions?
Sunday, November 16, 2008
Sum of 15
Two players are playing a game and take alternating turns. Initially, there are 9 cards with numbers from 1 to 9 on the table. On each turn, a player takes one of the cards. The first player to have exactly 3 cards with numbers that sum to 15 wins. If no one can after all cards are distributed, then it's a draw.
Saturday, November 15, 2008
Some more SRM experiences
This will probably only be interesting for TopCoder players, and they've probably already seen this on the forum, but anyway. Feel free to scroll over.
This was quite an educating experience from two points of view:
1) The coding times for the problems were 3 min, 52 min and 13 min. In other words, I've spent very much time on the medium, and had to write the hard in a hurry that eventually led to it failing systests. This was not the first time for this to happen, and I've always thought "maybe I need to abandon the medium and go for hard now?" many times, and I've always decided to postpone that decision. I would imagine that such a choice appears more frequently for those who don't usually solve all 3 problems - how do you deal with it?
2) The hard failed because of two bugs. The first one was a loop having a "<" instead of "<=" in the boundary condition, which I think is one-off and hard to prevent systematically. But the second one is very common: an int overflow. And I've always knew that C# can check against that, but somehow haven't been using this feature ("/checked+" compiler option, or the corresponding checkbox in Visual Studio). I will now.
Not much to say here. A quite standard hard that led me to a relatively easy win, a very beautiful medium that I was maybe lucky to solve quickly.
A submit with 10 seconds to go that passes systest, which uses a theorem that I've only had a 'heard-about' knowledge of before the SRM, and after rewriting the solution from scratch at least twice — doesn't look like a dull experience, does it? In retrospect, I shouldn't have even tried writing that DP over all splits of 16 numbered items into groups without finding out that there are billions of those; the Internet connection shouldn't have failed for about 5 minutes when I was struggling with the hard. But maybe because of all that I was finally able to invent a correct solution with about 15 minutes to go, and implement and debug it in that quite exciting last 15 minutes.
Tuesday, November 11, 2008
Long time no see
Hiya!
Today, I've got a small tip that has proved useful several times for me in ACM-style competitions. Suppose you have a program that does some calculations with integers. You've coded it using a 32-bit data type (say, 'int' in C++/Java), and then you figure out that the values you get don't fit into that type. No problem! You can easily switch to a 64-bit data type (say, 'long long' in C++ or 'long' in Java), and your program just works with numbers up to 9*10^18! But... It turns out that such numbers are not big enough as well. What to do now? Go for arbitrarily-long integers? But coding those in C++ takes reasonable time, especially if there're negative numbers involved; in Java, you'd have to rewrite all your code to ugly BigInteger syntax.
There's an intermediate solution that can allow you about 30 decimal digits almost without any hassle (it's only applicable when you use only addition, subtraction and multiplication, but not division): do the calculations with doubles AND longs. The basic idea is that imprecise doubles will give you the first, say, 13 digits correctly, and long will give you the last 18 digits, because it will contain the precise answer modulo 2^64.
More precisely: suppose we have the answer computed in a double variable 'x' and in a long variable 'y'. How do we get the full answer in a String? Here's a Java snippet that should mostly work (please don't use it at TopCoder :)):
Basically, lines 1-5 format all digits but the last 18, lines 6-10 convert the number formed by already formatted digits plus 18 zeroes to a long, and then subtracting that number from y gives us exactly the last 18 digits.
Apart from standard possible double precision issues, this approach has one more flaw - when the digits on the border of long and double are ..99999... or ...00000..., it may fail even if the precision error is tiny. For example, the above code won't correctly format 10^30. You can work around that by using BigInteger (which I intentionally didn't because it should be usable in C++ as well), or by manually adjusting for that case, but that brings too much hassle. Usually, for the numbers that you output in ACM-style problems, the above code is enough, and the joy of ACM is that you can submit, and do the more accurate coding only if you get WA :)
Today, I've got a small tip that has proved useful several times for me in ACM-style competitions. Suppose you have a program that does some calculations with integers. You've coded it using a 32-bit data type (say, 'int' in C++/Java), and then you figure out that the values you get don't fit into that type. No problem! You can easily switch to a 64-bit data type (say, 'long long' in C++ or 'long' in Java), and your program just works with numbers up to 9*10^18! But... It turns out that such numbers are not big enough as well. What to do now? Go for arbitrarily-long integers? But coding those in C++ takes reasonable time, especially if there're negative numbers involved; in Java, you'd have to rewrite all your code to ugly BigInteger syntax.
There's an intermediate solution that can allow you about 30 decimal digits almost without any hassle (it's only applicable when you use only addition, subtraction and multiplication, but not division): do the calculations with doubles AND longs. The basic idea is that imprecise doubles will give you the first, say, 13 digits correctly, and long will give you the last 18 digits, because it will contain the precise answer modulo 2^64.
More precisely: suppose we have the answer computed in a double variable 'x' and in a long variable 'y'. How do we get the full answer in a String? Here's a Java snippet that should mostly work (please don't use it at TopCoder :)):
1: public static String build(double x, long y) {
2: String sx = String.format("%.0f", x);
3: if (sx.length() <= 18)
4: return "" + y;
5: sx = sx.substring(0, sx.length() - 18);
6: long sl = 0;
7: for (int i = 0; i < sx.length(); ++i)
8: sl = sl * 10 + sx.charAt(i) - '0';
9: for (int i = 0; i < 18; ++i)
10: sl *= 10;
11: String sy = String.format("%018d", y - sl);
12: return sx + sy;
13: }
Basically, lines 1-5 format all digits but the last 18, lines 6-10 convert the number formed by already formatted digits plus 18 zeroes to a long, and then subtracting that number from y gives us exactly the last 18 digits.
Apart from standard possible double precision issues, this approach has one more flaw - when the digits on the border of long and double are ..99999... or ...00000..., it may fail even if the precision error is tiny. For example, the above code won't correctly format 10^30. You can work around that by using BigInteger (which I intentionally didn't because it should be usable in C++ as well), or by manually adjusting for that case, but that brings too much hassle. Usually, for the numbers that you output in ACM-style problems, the above code is enough, and the joy of ACM is that you can submit, and do the more accurate coding only if you get WA :)
Sunday, November 2, 2008
Burnside's lemma
The last TopCoder SRM (the problem statement is at http://www.topcoder.com/stat?c=problem_statement&pm=9975, but that requires a TopCoder account to view) has inspired me to write about a small and quite easy fact in group theory which I think was the most useful part of group theory for me in programming competitions.
It's called Burnside's lemma and says (citing from Wikipedia): let G be a finite group that acts on a set X. Then the number of orbits is equal to the average number of points fixed by an element of G. What does this all mean and how is this applicable to programming competitions? Let's continue with an example.
A standard problem that is best solved using Burnside's lemma is: consider a circular stripe of n cells. How many ways are there to color these cells with two colors, black and white, up to a rotation? Here, X is a set of all colored stripes (it has 2^n elements), and G is the group of its rotations (it has n elements: rotation by 0 cells, y 1 cell, by 2 cells, etc, by (n-1) cells), and an orbit is exactly the set of all stripes that can be obtained from each other using rotations, so the number of orbits will be the number of distinct stripes up to a rotation. Now let's apply the lemma, and find the number of stripes that are fixed by the rotation by K cells. If a stripe becomes itself after rotating by K cells, then its 1st cell must have the same color as its (1+K modulo n)-th cell, which is in turn the same as its (1+2K modulo n)-th cell, etc, until we get back to the 1st cell when m*K modulo n=0. One may notice that this will happen when m=n/gcd(K,n), and thus we get n/gcd(K,n) cells that must all be of the same color. Analogously, the same amount of cells must be of the same color starting with cell 2, (2+K modulo n), etc. Thus, all cells are separated into gcd(K,n) groups, with each group being of one color, and that yields us 2^gcd(K,n) choices. An by Burnside's lemma, the answer to the original problem is sum(2^gcd(K,n))/n, where the sum is taken over K from 0 to n-1.
That was rather complicated; here's a somewhat simpler example: Consider a square of 2n times 2n cells. How many ways are there to color it into X colors, up to rotations and/or reflections? Here, the group has only 8 elements (rotations by 0, 90, 180 and 270 degrees, reflections over two diagonals, over a vertical line and over a horizontal line). Every coloring stays itself after rotating by 0 degrees, so that rotation has X^(4n^2) fixed points. Rotation by 180 degrees and reflections over a horizonal/vertical line split all cells in pairs that must be of the same color for a coloring to be unaffected by such rotation/reflection, thus there exist X^(2n^2) such colorings for each of them. Rotations by 90 and 270 degrees split cells in groups of four, thus yielding X^(n^2) fixed colorings. Reflections over diagonals split cells into 2n groups of 1 (the diagonal itself) and (2n^2-n) groups of 2 (all remaining cells), thus yielding X^(2n^2-n+2n)=X^(2n^2+n) unaffected colorings. So, the answer is (X^(4n^2)+3*X^(2n^2)+2*X^(n^2)+2*X^(2n^2+n))/8.
I understand that this looks kind of too much formulas for too little gain, but once you get the hang of it, it becomes really simple and easy to use.
And as a plus, you get to verify that you haven't made a bug: the lemma has a division in the end (e.g., the division by 8 in the last formula). If that division produces a remainder, you've miscalculated somewhere. And chances are, if you have made a mistake, feeding the program random testcases will make the formula produce a remainder quite soon.
P.S. The Formula 1 GP at Interlagos starts in 20 minutes! I will be rooting for Massa to win the championship (I don't exactly know why - maybe because he's losing :)). The event is very likely to turn out quite exciting.
It's called Burnside's lemma and says (citing from Wikipedia): let G be a finite group that acts on a set X. Then the number of orbits is equal to the average number of points fixed by an element of G. What does this all mean and how is this applicable to programming competitions? Let's continue with an example.
A standard problem that is best solved using Burnside's lemma is: consider a circular stripe of n cells. How many ways are there to color these cells with two colors, black and white, up to a rotation? Here, X is a set of all colored stripes (it has 2^n elements), and G is the group of its rotations (it has n elements: rotation by 0 cells, y 1 cell, by 2 cells, etc, by (n-1) cells), and an orbit is exactly the set of all stripes that can be obtained from each other using rotations, so the number of orbits will be the number of distinct stripes up to a rotation. Now let's apply the lemma, and find the number of stripes that are fixed by the rotation by K cells. If a stripe becomes itself after rotating by K cells, then its 1st cell must have the same color as its (1+K modulo n)-th cell, which is in turn the same as its (1+2K modulo n)-th cell, etc, until we get back to the 1st cell when m*K modulo n=0. One may notice that this will happen when m=n/gcd(K,n), and thus we get n/gcd(K,n) cells that must all be of the same color. Analogously, the same amount of cells must be of the same color starting with cell 2, (2+K modulo n), etc. Thus, all cells are separated into gcd(K,n) groups, with each group being of one color, and that yields us 2^gcd(K,n) choices. An by Burnside's lemma, the answer to the original problem is sum(2^gcd(K,n))/n, where the sum is taken over K from 0 to n-1.
That was rather complicated; here's a somewhat simpler example: Consider a square of 2n times 2n cells. How many ways are there to color it into X colors, up to rotations and/or reflections? Here, the group has only 8 elements (rotations by 0, 90, 180 and 270 degrees, reflections over two diagonals, over a vertical line and over a horizontal line). Every coloring stays itself after rotating by 0 degrees, so that rotation has X^(4n^2) fixed points. Rotation by 180 degrees and reflections over a horizonal/vertical line split all cells in pairs that must be of the same color for a coloring to be unaffected by such rotation/reflection, thus there exist X^(2n^2) such colorings for each of them. Rotations by 90 and 270 degrees split cells in groups of four, thus yielding X^(n^2) fixed colorings. Reflections over diagonals split cells into 2n groups of 1 (the diagonal itself) and (2n^2-n) groups of 2 (all remaining cells), thus yielding X^(2n^2-n+2n)=X^(2n^2+n) unaffected colorings. So, the answer is (X^(4n^2)+3*X^(2n^2)+2*X^(n^2)+2*X^(2n^2+n))/8.
I understand that this looks kind of too much formulas for too little gain, but once you get the hang of it, it becomes really simple and easy to use.
And as a plus, you get to verify that you haven't made a bug: the lemma has a division in the end (e.g., the division by 8 in the last formula). If that division produces a remainder, you've miscalculated somewhere. And chances are, if you have made a mistake, feeding the program random testcases will make the formula produce a remainder quite soon.
P.S. The Formula 1 GP at Interlagos starts in 20 minutes! I will be rooting for Massa to win the championship (I don't exactly know why - maybe because he's losing :)). The event is very likely to turn out quite exciting.