Qualification Round 1 Tuesday, February 5, 2008 Match summaryFormula One has got its light signals, Soccer World Cup has the first whistle, for Olympic Games there is a great opening ceremony. The Algorithm competition of TCO 2008 was launched in a less spectacular way: by a small gray window stating that the coding phase has started. But even if the start wasn't that spectacular, the battle that soon started was as fierce as in any of the other competitions. The problemset offered many ways to qualify: Solving a tricky 250, implementing an almosttextbook dynamic programming in the 600, or finding a working approach for the 900... And last but not least, there was the opportunity to gain easy points from challenges, especially on the easy submissions. An interesting consequence of a lesstraditional easy problem: After a quarter of an hour, the top 20 was populated by coders of all colors. (And there didn't seem to be much corelation between their colors and the correctness of their solutions.) The most significant event in the coding phase was blackmath's great time on the hard problem. This gave him a comforting lead at the beginning of the challenge phase. But things were about to change. Astein's 275 points from challenges gave him the first place, and blackmath had to settle for second. Third place went to showbu. Congratulations to all the advancers, and let the best ones advance in the remaining two qualification rounds! The ProblemsMonstersAndBunniesUsed as: Division One  Level One:
Notation: Let Monsters onlyFirst, let's solve an easier version of the problem – for now, we will try to solve the situation where there are no bunnies. The first important thing is to notice that in each meeting either 0 or 2 monsters die. This means that the parity of monsters never changes. If the initial number of monsters is odd, it will always be odd, and thus it can never decrease to zero. In other words, if the initial number of monsters is odd, we can not win.
Furthermore, we can make the following observation: If there are M monsters and me,
there are
Let p(M) = ( C(M,2) / C(M+1,2) ) * p(M2)
Together with the initial conditions Constant time solutionUsing the above formula, we can compute: P(2) = C(2,2) / C(3,2) = 1/3 P(4) = (C(4,2) / C(5,2)) * P(2) = 6/10 * 1/3 = 3/5 * 1/3 = 1/5 P(6) = (C(6,2) / C(7,2)) * P(4) = 15/21 * 1/5 = 5/7 * 1/5 = 1/7
We start to see a pattern emerging: Consider a game where the number of monsters is 2K. We will make two slight modifications to our game rules:
Clearly, these changes don't affect your chance of survival. However, they have an important consequence: They make the game symmetric. Each of the 2K+1 players (that is, 2K monsters + us) has got an equal probability of being the last one alive. And this probability clearly has to be 1/(2K+1). What about the bunnies?Imagine that you have a fair 6sided dice. Consider the following algorithm: "Repeatedly throw the dice until you get either a 1, or a 6." Clearly, the probability of ending with a 1 is the same as the probability of ending with a 6. Now, what would happen if the dice were biased? For example, let prob(1)=1/13 and prob(6)=3/13. How will this affect the final outcome of our algorithm? Note that we don't even need to know how probable each of the outcomes 2, 3, 4, and 5 is. What matters is that in each throw the outcome 6 is three times more likely than the outcome 1. If we make many throws, we will get approximately three times as many 6s as 1s. Thus, for example, if we executed our algorithm 400 times, we can expect 300 runs to end with a 6, and only 100 to end with a 1. This reasoning can be formalized using conditional probability. The probability of our algorithm returning 6 is the probability of a throw returning 6, given that we know it returned (6 or 1). This probability can be computed as prob(6) / (prob(1)+prob(6)). The moral of the story: The outcome of our algorithm only depends on the ratio prob(1):prob(6). Okay, but what about the bunnies?The bunnies don't influence monster count in any way. We can simply ignore all meetings that involve bunnies, just as in the above experiment we ignored outcomes 2, 3, 4, and 5, and only focused on 1s and 6s. More precisely, we have a town with monsters and possibly some bunnies. We will generate the meetings (throw the dice), until we get an important meeting that does not involve a bunny (the throw ends with a 1 or a 6). Now there are two possible outcomes: either we meet a monster and lose (the algorithm returns 1), or two monsters meet and we win (the algorithm returns 6). We can make the same argument as before: The probability that in the important meeting two monsters meet (the algorithm returns a 6) depends only on the ratio of probabilities prob(two monsters meet):prob(you meet a monster). The two probabilites in question can be expressed as: prob(two monsters meet) = C(M,2) / C(M+B+1,2) prob(you meet a monster) = M / C(M+B+1,2)
And thus their ratio is always the same, This means that if we completely ignore the bunnies, and only focus on the meetings that involve us and the monsters, we will get the correct result. (A good way of looking at the bunnies: We and the monsters are playing the game. The bunnies just roam around and get into our way, but they don't influence our game in the same way ducks that fly above the town don't influence it.) (Yet another way of getting the right intuition on bunnies: Consider the modified rules that make the game symmetric. The bunnies can't help you, and they also can't help the monsters, simply because of the symmetry. If there was an argument that shows, say, "if there are more bunnies, you have a higher chance to win", the same argument could be used to show "if there are more bunnies, the kth monster has a higher chance to win", and that is not possible.) SummaryWe just explained that for all values of B and even values of M the answer is 1/(M+1), and for all other inputs the answer is 0. Dynamic programmingFinally, we would like to note that the entire task was solvable without the above analysis, just by rewriting the problem statement as a recursive formula, and then use dynamic programming to evaluate it. The code for such a solution follows. double fullDP(int M, int B) { double[][] prob = new double[M+1][B+1]; for (int m=0; m<=M; m++) for (int b=0; b<=B; b++) { if (m==0) { prob[m][b]=1.0; continue; } int allEvents = (m+b+1)*(m+b)/2; int MMEvents = m*(m1)/2; double MMProb = 1.0*MMEvents/allEvents; int MBEvents = m*b; double MBProb = 1.0*MBEvents/allEvents; int BBEvents = b*(b1)/2; double BBProb = 1.0*BBEvents/allEvents; int HMEvents = m; double HMProb = 1.0*HMEvents/allEvents; int HBEvents = b; double HBProb = 1.0*HBEvents/allEvents; double pp = 0.0; if (m>=2) pp += MMProb * prob[m2][b]; // two monsters meet and die if (b>=1) pp += MBProb * prob[m][b1]; // a monster kills a bunny if (b==0) { prob[m][b] = pp; } else { // we meet a bunny, examine whether killing it is better than // letting it go, and pick the better possibility prob[m][b] = Math.max( (1BBProb)*(pp + HBProb*prob[m][b1]) , (1BBProbHBProb)*pp ); } } return prob[M][B]; }PrimeSums Used as: Division One  Level Two:
This task could be split into two separate questions: The bag has at most 50 elements, and they don't exceed 10,000. Thus the values W for which we need to answer these questions lie in the range from 0 to 500,000. Prime numbersChecking whether a number is prime can be done by a trivial algorithm: The number N is prime if it is greater than 1, and no number between 2 and sqrt(N), inclusive, divides N. There are also more efficient methods. One particularly suitable and easy to implement is the Sieve of Eratosthenes. Subset countsThis part of the problem was an exercise in knapsackstyle dynamic programming. First, let's show how to solve the problem for sets, i.e., in the case when all input values are distinct. Let N(X,W) be the number of subsets that only use first X elements from the input, and have weight W. Clearly, N(0,0)=1, and N(0,W)=0 for any positive W. Now, how to compute N(X,W) for a positive X? We can split all the subsets counted by N(X,W) into two kinds: those that don't contain the Xth element, and those that do. For the first kind, the count of such subsets is clearly N(X1,W). For the second kind, take a look at how the rest of the set can look like. It may only contain some of the first X1 elements, and its weight has to be W(weight of the Xth element). Thus the number of subsets of the second type is N(X1,Wweight(X)). In this simple case, all the values N(X,W) can be computed at the same time using the following pseudocode: set N(0,0)=1 for all w from 1 to maxW: set N(0,w)=0 for all x from 1 to maxX: for all w from 0 to maxW: N(x,w) = N(x1,w) if (weight(x) ≤ w): N(x,w) += N(x1,wweight(x)) Handling duplicatesIn the general case we need to make sure we don't count identical subbags more than once. To achieve this, we will simply process all equal values at the same time. This means that the recurrence relation won't have 2 cases (take element X or not?), but multiple cases (take element X how many times?). Fitting it all into memoryThe entire array needed to store the values N(x,w) would not fit into the memory limit. Luckily, we have two circumstances speaking in our favor: First, we only need the values N(maxX,*). Second, to compute the values N(X,*) we only need the values N(X1,*). This means that we can only remember two rows of the table at any time. Java code follows. int SUM; boolean[] isPrime; long[][] ways; public long getCount(int[] bag) { SUM=0; for (int i=0; i<bag.length; i++) SUM += bag[i]; Arrays.sort(bag); // do the sieve isPrime = new boolean[SUM+1]; Arrays.fill(isPrime,true); isPrime[0]=isPrime[1]=false; for (int i=2; i*i<=SUM; i++) if (isPrime[i]) for (int j=i*i; j<=SUM; j+=i) isPrime[j]=false; ways = new long[2][SUM+1]; Arrays.fill(ways[0],0); Arrays.fill(ways[1],0); ways[0][0] = 1; int last=0, next=1; for (int i=0; i<bag.length; i++) { if (i>0) if (bag[i]==bag[i1]) continue; // skip duplicates // count duplicity int cnt=1; while (i+cnt < bag.length) if (bag[i+cnt]==bag[i]) cnt++; else break; // fill in new values for (int s=0; s<=SUM; s++) { ways[next][s] = ways[last][s]; for (int t=1; t<=cnt; t++) if (st*bag[i] >= 0) ways[next][s] += ways[last][st*bag[i]]; } // prepare next step last=1last; next=1next; } long result = 0; for (int i=0; i<=SUM; i++) if (isPrime[i]) result += ways[last][i]; return result; } FootnoteThere is at least one asymptotically better algorithm than this one. Can you find one? (Hint: There is a better way how to handle the duplicates.) MagicFingerprintUsed as: Division One  Level Three:
There were two possible approaches, and they can be labeled "filter and precompute", and "generate". FilteringIf implemented efficiently, the magic fingerprint method is pretty fast, and any reasonably fast computer can process all numbers up to 1 billion in a matter of a few minutes. Well, but the time limit is just two seconds... What can we do to help? The answer is: let your computer do most of the work. For example, precompute the answer for inputs of the type [k*10^6,(k+1)*10^6). You will get around 1,000 values. Store these in your program as an array of integer constants. Now, if you get a large input, it surely contains many of these ranges. Just add together all their counts. Now you only need to compute magic fingerprints for a few elements at the beginning and at the end of the given range. A similar approach was used in blackmath's fastest solution. GeneratingClearly, the number N is lucky if and only if magic(N) is lucky. So far, we used one direction: given N, compute magic(N). However, a more efficient way is to do it backwards: given magic(N), determine all possible N. This isn't too hard. For example, suppose that magic(N)=8111. How many fivedigit Ns are there? We can generate them recursively. We start by trying the first digit 1. Then the second digit has to be 9, the third has to be 8. We have two choices for the fourth digit: the first one leads to the numbers 19876 and 19878, the second one yields the number 19898. And so on. (In this case, leading digits 8 and 9 will bring some more solutions.) We can now use breadthfirst search to generate all lucky numbers less than a billion: Start with the number 7, and for each number X we process, find all N≤10^9 such that magic(N)=X, and add them into the queue to be processed. Java code that generates all lucky numbers follows. Set<Integer> lucky; Queue<Integer> process; int[] digits; int digitCount; int[] newDigits; void generate(int where) { if (where==1) { int current = 0; for (int d=digitCount; d>=0; d) { current *= 10; current += newDigits[d]; } if (!lucky.contains(current)) { lucky.add(current); process.add(current); } } else { newDigits[where] = newDigits[where+1] + digits[where]; if (newDigits[where]>=0 && newDigits[where]<=9) generate(where1); newDigits[where] = newDigits[where+1]  digits[where]; if (newDigits[where]>=0 && newDigits[where]<=9) generate(where1); } } public int countLuckyNumbers(int A, int B) { lucky = new HashSet<Integer>(); process = new LinkedList<Integer>(); digits = new int[12]; newDigits = new int[12]; lucky.add(7); process.add(7); while (!process.isEmpty()) { int current = process.remove(); digitCount = 0; while (current > 0) { digits[digitCount++] = (int)current%10; current /= 10; } while (digitCount<=8) { for (int i=1; i<10; i++) { newDigits[digitCount]=i; generate(digitCount1); } digits[ digitCount++ ] = 0; } } int result = 0; for (Integer x : lucky) { if (A<=x && x<=B) result++; System.out.println(x); } return result; } 
