Match summary

The 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 Problems

ManyNumbers

Used as: Division One - Level One:

Value 250

Submission Rate 139 / 140 (99.29%)

Success Rate 134 / 139 (96.40%)

High Score Zuza for 249.87 points (0 mins 39 secs)

Average Score 238.81 (for 134 correct submissions)

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(a-b);

LuckyFives

Used as: Division One - Level Two:

Value 500

Submission Rate 66 / 140 (47.14%)

Success Rate 59 / 66 (89.39%)

High Score tomekkulczynski for 493.56 points (3 mins 15 secs)

Average Score 366.22 (for 59 correct submissions)

First, let's count the probability of rolling N dice and getting exactly K fives. It's the probability of getting K-1 fives on N-1 dice and a five on the last die plus the probability of getting K fives on N-1 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:

Value 1000

Submission Rate 61 / 140 (43.57%)

Success Rate 48 / 61 (78.69%)

High Score Zuza for 949.61 points (6 mins 36 secs)

Average Score 652.20 (for 48 correct submissions)

Let's count the minimal number of moves we need to reach Nth step. To get to Nth step, you either stood on the N-1th 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[i-1] == 1) C[i] = C[i-1]+1;
      for(j=0;j<i;j++) for(k=0;k<j;k++) if ((stairs[i] <= stairs[k] + P[j-k]) && (C[i] > C[j] + j-k+1)) C[i] = C[j] + j-k+1;
      if (C[i] == 1000000) return -1;
   }
   return C[stairs.length-1];

In this solution P[i] is 2ⁱ.

By Vedensky
TopCoder Member