|
Match Editorial |
Wednesday, March 28, 2007
Match summary
Considering the success rates of my previous SRMs, this time I really needed something on the simple side. So we got a relatively simple SRM, with quite a lot of coders scoring on all three problems. Finishing on top was ACRush, who was very fast on both the medium and the hard and quick on challenges. He was followed by bmerry and Egor. The top three finishers got +150 on challenges, putting them way ahead of the pack.On the contrary, Division 2 had only three people who solved all three problems: skywendy in first place, At_the_Summit in second place and ngg in fourth. Three challenges compensated kp0t for the flawed easy and earned him third place.
The Problems
Chessboard
Used as: Division Two - Level One:
This problem was pretty straightforward. By looking at the first character of the input we could deduce the operation to be performed; performing it led us to the fact that the coordinates could be obtained from the cell number via dividing by 8. However, you had to be very careful to avoid 'off-by-one' errors, and the system tests confirmed that. See At_the_Summit's passing solution for the implementation details.
Value 250 Submission Rate 630 / 736 (85.60%) Success Rate 300 / 630 (47.62%) High Score ikicic for 244.51 points (4 mins 16 secs) Average Score 171.42 (for 300 correct submissions)
SimpleRotationDecoder
Used as: Division Two - Level Two:
The main difficulty about this problem was understanding all the details about the encryption algorithm used. The key fact was that we knew the length of the password - 3 letters. That yields only 263 = 26*26*26 = 17576 possible passwords, and leads us to the bruteforce approach. First, we iterate over all possible passwords. For each password, we need to decrypt the text and then to verify the original text. Once we've got a correct decryption result we're done.
Value 500 Submission Rate 183 / 736 (24.86%) Success Rate 106 / 183 (57.92%) High Score MrBananaBrains for 429.32 points (11 mins 56 secs) Average Score 256.68 (for 106 correct submissions)
To decrypt the text, we notice that if a + b = c (mod 27), then a = c - b (mod 27). So we need to subtract the password from the text to get the original text. We could go with subtraction, but if we'd like to avoid negative numbers we can notice that subtracting a number in range from 1 to 26 is just the same as adding a number from that range (because -1 = -1 + 27 = +26, -2 = -2 + 27 = +25, etc) and continue with adding the password instead of subtracting it - but that's not really important.
Having decrypted the text, we need to carefully verify all the constraints written in the first paragraph of the problem statement. For a neat implementation of such verification, as well as of all the above technique, see MRoizner's solution.
This problem posted another interesting challenge: coming up with correct testcases, both for you during the challenge phase and for me when preparing the contest. It's not so obvious how to achieve exactly one correct possible decoding, so I did the following: add random letters one-by-one, and keep track of what passwords are already incorrect, what's the length of the last word for each password and whether it contains a vowel or not. That way I could quickly see if there's at least one possible password, and if there's not I just took another random letter. As soon as exactly one password could be correct, I stopped.
And let's end with a kind of shortest code contest: what is the shortest correct testcase? QuantumAlchemy
Used as: Division Two - Level Three:
Used as: Division One - Level Two:
Value 1000 Submission Rate 83 / 736 (11.28%) Success Rate 8 / 83 (9.64%) High Score kp0t for 593.35 points (27 mins 55 secs) Average Score 522.75 (for 8 correct submissions)
If our initial set contains the required substance 'X', we're done. If it doesn't, we need to get it somehow... But wait! There's at most one way to do it! If there's no reaction resulting in 'X', the answer is -1, and if there is, this reaction must be done. So, instead of getting 'X', we should focus on getting all the ingredients for that reaction.
Value 500 Submission Rate 381 / 522 (72.99%) Success Rate 131 / 381 (34.38%) High Score ACRush for 476.45 points (6 mins 22 secs) Average Score 324.91 (for 131 correct submissions)
This simple idea, applied inductively, was the key to this problem. Let's look at our transformations from the end to the beginning. Suppose we need to get a grams of substance b at some point. In case we don't have such amount in our initial set, we need to get the extra amount by applying the corresponding reaction — there's just one, remember?
So, essentially, we keep track of how many reactions we've already 'unperformed', and the currently needed amounts of each substance. If those amounts are already contained in the initial set, we're done. If not, we take any of exceeding amounts and 'unperform' the corresponding reaction. We stop and return -1 if the total weight of needed substances exceeds 50, for example. This will run in time because each 'unperforming' increases the total weight of needed substances. See darnley's solution for a sample implementation.
VolleyballTournament
Used as: Division One - Level One:
Each won match gives 3 won sets. Thus, wonSets - 3 * wonMatches gives the total number of won sets in the lost matches. In the same way, lostSets - 3 * lostMatches gives the total number of lost sets in the won matches. Having noticed that, we can now consider the won and lost matches separately. For example, let's study the won matches (we've won them after all :)). Suppose we have a matches, each having between 0 and 2 lost sets, and we know that we lost b sets in total. When is it possible to reconstruct the exact distribution of the lost sets?
Value 250 Submission Rate 472 / 522 (90.42%) Success Rate 289 / 472 (61.23%) High Score Egor for 241.27 points (5 mins 26 secs) Average Score 164.10 (for 289 correct submissions)
Long story short, the answer is: when b is 0, 1, 2a-1 or 2a. It's not so difficult to prove that, and we'll leave it as a math exercise for the reader. Having that fact in our hands, we can construct a short solution, like that of Egor.
This problem, in fact, allows a more straightforward solution: just bruteforce the amount of matches with each outcome. See nika's code for a simple implementation.
FairTournament
Used as: Division One - Level Three:
This problem featured the classical DP-on-subsets technique. Suppose we've already put the first m numbers of the permutation. All of them, due to fairness restriction, are between 1 and m+k. On the other hand, all the remaining numbers will be at least m-k+1. Thus, we must have already placed all numbers between 1 and m-k. The only freedom we have is what k numbers from the range [m-k+1..m+k] were used.
Value 1000 Submission Rate 78 / 522 (14.94%) Success Rate 66 / 78 (84.62%) High Score Gluk for 816.61 points (14 mins 8 secs) Average Score 589.23 (for 66 correct submissions)
That nearly constitutes a DP solution. Let's define amount[m,X] (where m is a number between 1 and n, and X is a subset of [m-k+1..m+k] with k elements) as the amount of ways to put the first m numbers of the permutation in such a way that all the numbers from the set X are used, as well as all the numbers less than or equal to m-k. By looping over the value of the m-th number we can find this amount by adding some amounts for smaller m's. Or, if we like the DP the other way, we could loop over the value of the m+1-st number to add this amount to all the amounts on the next step that contain it.
You need to be careful at the beginning and at the end of the permutation, but after some thinking you could find out that these corners don't even need any special treatment. However, what needed special treatment was the representation of the result. As you were required to return a String and not a long, and the last example featured a 21-digit answer with k equal to just one, it was quite obvious that any standard numeric type could not hold such big numbers. Thus you had to implement the addition of arbitrary-long numbers. Or, if you're using Java, employ the BigInteger class.
See bmerry's solution for an implementation of the all-by-myself approach, or Vitaliy's solution for the BigInteger way.
