Match Editorials

Match summary

In this problem set coders faced an easy first problem, an easy second -- which had the same number of correct submissions as the first problem-- and a not very difficult third, though it did require some accuracy in coding.

After the coding phase, Weiqi was the first, but challenge phase made him fourth, and after system tests he finished in third place. fatit finished second, getting 100 points during the challenge phase. YuJieLu took first place with 175 challenge points, racking up his second first-place finish in only his second High School SRM.

The Problems

Value	250
Submission Rate	133 / 143 (93.01%)
Success Rate	112 / 133 (84.21%)
High Score	Zuza for 249.40 points (1 mins 23 secs)
Average Score	234.38 (for 112 correct submissions)

In this problem, the main thing was to parse integers from a string, but to do it carefully. The sample code can be as follows:

   public int getLeast(String line, int givenNumber) {
      line += " ";
      int curr = 0, mn = 10000;
      for(int i = 0; i < line.length(); i++) {
         if (line.charAt(i) == ' ') { if ((curr != 0) && (curr > givenNumber) && (mn > curr)) mn = curr; curr = 0; } else
            curr = 10*curr + line.charAt(i) - '0';
      }
      if (mn == 10000) return -1; else return mn;
   }

Value	500
Submission Rate	117 / 143 (81.82%)
Success Rate	112 / 117 (95.73%)
High Score	Zuza for 496.00 points (2 mins 33 secs)
Average Score	416.96 (for 112 correct submissions)

The second problem didn't take long time for competitors to solve it and, since it had only five wrong solutions, there weren't many possibilities for challenge.

In this problem, the simplest approach was to count the probability that your friend will not hit the target in n or less shots. For each shot he misses with probability (1-accuracy/100.0), and shots are independent, so you may count it as (1-accuracy/100.0)^n. And when this probability becomes less than or equal to 0.5, you should break and return current n.

From examples you can see that the answer will never be greater than 68, so you didn't need to worry about time limit or double precision.

Java code follows:

   public int profitableBet(int accuracy) {
    double p = 1-(accuracy/100.0),w = 1;
    for(int n=0;;n++) {
        w *= p;
        if (w <= 0.5) return n;
    }
   }

Value	1000
Submission Rate	47 / 143 (32.87%)
Success Rate	29 / 47 (61.70%)
High Score	Weiqi for 844.93 points (12 mins 39 secs)
Average Score	530.16 (for 29 correct submissions)

In this problem, you were asked to count the probability that a point will be contained in some number K of boxes. You can say it as follows: it is the probability that a point will be contained in at least K boxes minus the probability that a point will be contained in at least K+1 boxes. For each box, you may count the number of boxes it is contained in. Then the probability that a point will be contained in at least K boxes will be equal to the sum of the areas of the boxes, contained in K-1 other boxes (which represents the favourable outcomes), divided by 10,000 - the area of the large square box (all possible outcomes).

In other words, you could solve this problem using these steps:

• Parse the coordinates of triangles
• For each pair of triangles, determine if the first one lies in the second one
• For each triangle, determine the number of triangles in which it is contained
• For each triangle that is contained in inBox triangles, add its area to the answer
• For each triangle that is contained in inBox+1 triangles, substract its area from the answer
• If inBox is 0, add 10000 to answer