
Match Editorials 
TCHS SRM 15Monday, September 25, 2006
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 firstplace finish in only his second High School SRM.
The Problems
NumbersLine Used as: Division One  Level One:
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;
}
ShootingGallery
Used as: Division One  Level Two:
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 (1accuracy/100.0), and shots are independent, so you may count it as (1accuracy/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;
}
}
SetOfBoxes Used as: Division One  Level Three:
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 K1 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
You can also see
fatit's code or
reiten's code a clear implementation of this approach.
By
Vedensky TopCoder Member