|
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 first-place 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 (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;
}
}
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 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
You can also see
fatit's code or
reiten's code a clear implementation of this approach.
By
Vedensky TopCoder Member