Wednesday, March 28, 2007 Match summaryConsidering 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 ProblemsChessboardUsed 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 'offbyone' errors, and the system tests confirmed that. See At_the_Summit's passing solution for the implementation details. 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 26^{3} = 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. 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 onebyone, 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: 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. 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? Long story short, the answer is: when b is 0, 1, 2a1 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 DPonsubsets 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 mk+1. Thus, we must have already placed all numbers between 1 and mk. The only freedom we have is what k numbers from the range [mk+1..m+k] were used. 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 [mk+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 mk. By looping over the value of the mth 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+1st 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 21digit 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 arbitrarylong numbers. Or, if you're using Java, employ the BigInteger class. See bmerry's solution for an implementation of the allbymyself approach, or Vitaliy's solution for the BigInteger way. 
