Saturday, May 19, 2007 Match summaryThe match started with a very easy 250 problem that almost everyone was able to solve. The medium had a coderfriendly statement and was not very difficult as well. The hard problem could be solved using a wellknown algorithm but it included several tricks, which brought a lot of excitement into the challenge phase (and lots of points to some coders). Many of the hard solutions failed during either the challenge or the system test, so only 7 coders got it right.The leading position on the scoreboard was occupied by Burunduk2 from Russia. He was followed by gurugan1 and fpavetic, from Canada and Croatia, respectively. The ProblemsSortInsideNumberUsed as: Division One  Level One: This problem was pretty straightforward and many coders solved it quickly. The problem had two very simple parts. The first consists of converting the given integer number into the array of digits, then sorting it in ascending order. Next, add each element to the beginning of the resulting string by iterating over the sorted array. This is valich's Java solution for the implementation details: public int sort(int x) { String s = String.valueOf(x); char[] arr = new char[s.length()]; for (int i = 0; i < s.length(); i++) { arr[i] = s.charAt(i); } Arrays.sort(arr); String res = ""; for (int i = 0; i < s.length(); i++) { res = arr[i] + res; } return Integer.parseInt(res); }SoccerCommentator Used as: Division One  Level Two: This problem was not very difficult and the only thing to worry about was following the statement rules carefully. The first step was to calculate how many goals both teams have already scored. Let's compute X  the number of goals scored by the second team minus the number of goals scored by the first team. Obviously, if X < 0 the first team does not need any more goals to win (return 0 in this case). Second, the first team needs at least X more goals to score. When it will score X goals, the number of away goals becomes significant. Now, the answer depends on the host team of the first game:
KnapsackProblem Used as: Division One  Level Three: You were given an array A={a_{1},...,a_{x}} of x integers (the weights of the items you have) and another integer C (the maximum weight of your bag). You were asked to find the number of different sets of items you can carry in the bag. Clearly you have 2^{x} subsets of A, and you can not naively solve this problem by exhaustively comparing the sum of the elements of each subset of A to C. Such a procedure would work slightly long and could exceed the timelimit. The problem can be solved more quickly with an algorithm discovered by Horowitz and Sahni in 1974, which is called the MeetintheMiddle algorithm. It takes on the order of 2^{x/2} steps instead of the 2^{x} steps of the naive exhaustive comparison algorithm. The idea of the MeetintheMiddle algorithm is the following. First, partition the array A into two arrays A_{1}={a_{1},...,a_{x/2}} and A_{2} ={a_{x/2 + 1},...,a_{x}}. Now iterate through all subsets of A_{1}, calculating the sum of the elements for each subset and adding this sum to array s1. When you are done with all subsets, sort s1 in ascending order. Perform the same operation for A_{2}, getting sorted array s2. Now for each ith element of the s1 you have to find the biggest s2 element such that the sum of these two elements is less than or equal to C. Since the array s2 is sorted in the ascending order, all the elements on the left of the just found "biggest value" are also matched (sum of the ith element of s1 and each of them is less or equal to C). Thus you have found the number of sets which can be carried in the bag and contain the ith element of s1. To find the total number of sets you need to sum such numbers on each step of iterating for s1. Each time the search of the biggest s2 element can be done using the binary search algorithm. This helps to speed up the solution. The problem had one interesting trick inside  sometimes the subsetsum can be greater than the maximum value of 32bit integer. During the round, several coders stumbled over this hidden trap. Burunduk2's C++ code follows: int numberOfWays( vector 
