Wednesday, December 27, 2006 Match summaryThe problems in HS SRM 25 seemed to be rather easy, and Zuza submitted all three problems in 15 minutes. sluga and Weiqi both finished coding right after Zuza, in 16 minutes, and fell into second and third places after the coding phase. The challenge phase didn't bring any changes to the top three, so Zuza won this SRM by a margin of 3.42 points.The ProblemsManyNumbersUsed as: Division One  Level One: We can do this problem as it is written in the problem statement: count A, count B, and return the absolute value of the difference between them. All the coders who failed to solve this problem returned the difference itself, not the absolute value. Java code follows: int a=0,b=0; for(int i=0;i<numbers.length;i++) if (numbers[i] % K == 0) a += numbers[i]; else b += numbers[i]; return Math.abs(ab); LuckyFives Used as: Division One  Level Two: First, let's count the probability of rolling N dice and getting exactly K fives. It's the probability of getting K1 fives on N1 dice and a five on the last die plus the probability of getting K fives on N1 dices and of not getting a five on the last die. A boundary condition is that we have 0 fives on 0 dices with the probability of 1. Second, count the probability of getting enough fives as a sum of the probabilities of getting five from 1+dice/5 to dice fives if rolling dice dice. You can see the implementation of this algorithm in Zuza's solution Staircase Used as: Division One  Level Three: Let's count the minimal number of moves we need to reach Nth step. To get to Nth step, you either stood on the N1th step and moved up or stood on some step lower than Nth, made some moves down, and then moved up to Nth. Of course, you should check height differences for all moves to be correct. Also notice that if you can't get to the Nth step, you also can't get to all the higher steps. You can see it in this Java code: C[0] = 0; for(i=1;i<stairs.length;i++) { C[i] = 1000000; if (stairs[i]  stairs[i1] == 1) C[i] = C[i1]+1; for(j=0;j<i;j++) for(k=0;k<j;k++) if ((stairs[i] <= stairs[k] + P[jk]) && (C[i] > C[j] + jk+1)) C[i] = C[j] + jk+1; if (C[i] == 1000000) return 1; } return C[stairs.length1];In this solution P[i] is 2^{i}. 
