|
Match Editorials |
Monday, July 31, 2006
Match summary
Submission rates were pretty high - more than 90% of the contestants submitted the first two problems and more than a half of them submitted the hard. Most of hards were down after the first couple of minutes of the challenge phase, giving some points to strong challengers. After the system tests, Zuza took home his second HS SRM win with tomekkulczynski and RuslanSM rounding out the top three.
The Problems
ExcitingGame
Used as: Division One - Level One:
Value 250 Submission Rate 81 / 83 (97.59%) Success Rate 74 / 81 (91.36%) High Score Zuza for 249.19 points (1 mins 37 secs) Average Score 230.43 (for 74 correct submissions)
Solution to this problem is just a simple simulation. Make sure you start counting from 1 (not from zero) and that you switch to classmate 0 after classmate with number (nClassmates - 1).
public int howMany(int nClassmates, int nTimes, int who) {
int ans = 0;
for (int i = 0; i
SimpleCompressor
Used as: Division One - Level Two:
Value
500
Submission Rate
75 / 83 (90.36%)
Success Rate
53 / 75 (70.67%)
High Score
Burunduk3 for 487.08 points (4 mins 39 secs)
Average Score
367.97 (for 53 correct submissions)
In this problem coders were asked to show their ability to use recursion.
If we want to uncompress a string s, the basic cases are the following ones:
s is empty. In this case return will be just an empty string.
s starts with a letter (like "Atail"). In this case we can uncompress the first letter and the tail
of s independently.
The uncompression of a letter is just the same letter, and to uncompress the tail of s we recursively call
method uncompress(s.substring(1)).
To get the final return value, we append the result of the recursive call to the first character.
If s starts with an opening bracket, we need to find the corresponding closing bracket.
We iterate through the characters of s counting opening and closing brackets, and stop when the number of
the closing brackets is equal to the number of opening brackets.
Now we process the string inside the brackets in the way it described in the statement and append the
uncompressed tail of string s.
Java implementation of this approach follows:
public String uncompress(String s) {
// Empty string
if (s.length() == 0) return "";
char c = s.charAt(0);
// s starts with a letter
if (Character.isLetter(c))
return c + uncompress(s.substring(1));
// We are looking for the correspondent bracket.
int cnt = 1;
int i = 0;
do {
i++;
if (s.charAt(i) == '[') cnt++;
if (s.charAt(i) == ']') cnt--;
} while (cnt > 0);
String ans = "";
String temp = uncompress(s.substring(2, i));
for (int j = 0; j <(s.charAt(1) - '0'); j++) ans += temp;
return ans + uncompress(s.substring(i + 1));
}
ProductsMatrix
Used as: Division One - Level Three:
Value
1000
Submission Rate
47 / 83 (56.63%)
Success Rate
10 / 47 (21.28%)
High Score
Zuza for 940.39 points (7 mins 14 secs)
Average Score
710.41 (for 10 correct submissions)
A lot of coders tried to brute force this problem by generating all elements of matrix A, writing them into a
big array and sorting it.
Unfortunately, the resulting array can contain up to 100000*100000 elements, which is way too many numbers to even
try to generate them all.
The problem asks us to find the number at the k-th position in the array. Lets look at the inverted problem -
given a number, find its position in the array
(or, if array doesn't contain this number, find the position where it would be inserted to keep array sorted).
If we can solve this inverted problem, we can use binary search to solve our main problem (if you are not familiar
with binary search, you can read our
tutorial).
To find the position of a number X in the final array, we need to find how many elements of the array are not
greater than X.
This number is the same as the number of elements of matrix A which are not greater than X.
The easiest way to find this number is to iterate through all rows of matrix A.
Really, row i of matrix A contains n elements - i, 2*i, 3*i, ..., n*i.
If X is greater or equal than n*i, then row i contains n elements not greater than X.
If X is smaller than n*i, then row i contains (X / i) elements which are not greater than X (proving this
fact is left to the reader).
To find the total number of such elements in matrix A, we iterate through all rows of the matrix and sum up
the numbers for each row.
If you are able to find this number, the binary search implementation becomes really short. For a clean C++
implementation of this approach, see Zuza's
solution.
