Match summary

The match started with a very easy 250 problem that almost everyone was able to solve. The medium had a coder-friendly statement and was not very difficult as well. The hard problem could be solved using a well-known 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 Problems

SortInsideNumber

Used as: Division One - Level One:

Value 250

Submission Rate 47 / 47 (100.00%)

Success Rate 45 / 47 (95.74%)

High Score rlp for 249.21 points (1 mins 36 secs)

Average Score 241.50 (for 45 correct submissions)

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:

Value 500

Submission Rate 47 / 47 (100.00%)

Success Rate 33 / 47 (70.21%)

High Score Burunduk3 for 487.32 points (4 mins 36 secs)

Average Score 431.01 (for 33 correct submissions)

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:

If the first game was hosted by the first team, compare the number of first team away goals (goals already scored by the first team in the second game plus X) and the number of second team away goals (scored by the second team in the first game). If the second number is greater or equal than the first number, the first team needs to score one more goal, increasing the answer to (X + 1). Otherwise, X goals is enough for the first team to advance.
We act similarly if the first game was hosted by the second team. Compare A = the number of away goals scored by the first team (the number of goals it scored in the first game) and B = the number of away goals scored by the second team (the number of goals it scored in the second game). The answer is X or (X + 1) depending on whether A is greater than B or not.

For the details of the implementation please check Burunduk3's C++ fastest solution.

KnapsackProblem

Used as: Division One - Level Three:

Value 1000

Submission Rate 37 / 47 (78.72%)

Success Rate 7 / 37 (18.92%)

High Score Burunduk2 for 916.94 points (8 mins 42 secs)

Average Score 583.22 (for 7 correct submissions)

You were given an array A={a₁,...,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 time-limit.

The problem can be solved more quickly with an algorithm discovered by Horowitz and Sahni in 1974, which is called the Meet-in-the-Middle 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 Meet-in-the-Middle algorithm is the following. First, partition the array A into two arrays A₁={a₁,...,a_x/2} and A₂ ={a_{x/2 + 1},...,a_x}.

Now iterate through all subsets of A₁, 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₂, getting sorted array s2.

Now for each i-th 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 i-th 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 i-th 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 subset-sum can be greater than the maximum value of 32-bit integer. During the round, several coders stumbled over this hidden trap.

Burunduk2's C++ code follows:

int numberOfWays( vector  x, int C )
  {
    vector  a, b;
    int n1 = x.size() / 2, n2 = x.size() - x.size() / 2;
    for (int i = 0; i < (1 << n1); i++)
    {
      a.push_back(0);
      for (int j = 0; j < n1; j++)
        if ((i >> j) & 1)
          a[a.size() - 1] += x[j];
    }
    for (int i = 0; i < (1 << n2); i++)
    {
      b.push_back(0);
      for (int j = 0; j < n2; j++)
        if ((i >> j) & 1)
          b[b.size() - 1] += x[n1 + j];
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    fprintf(stderr, "a.size()=%d b.size()=%d", a.size(), b.size());
    int ans = 0;
    for (int i = 0; i < a.size(); i++)
    {
      int mi = 0, ma = b.size() - 1, av;
      while (mi < ma)
      {
        av = (mi + ma + 1) / 2;
        if (b[av] + a[i] <= C)
          mi = av;
        else
          ma = av - 1;
      }
      if (a[i] <= C)
        ans += mi + 1;
    }
    return ans;
  }

By Katya_Lazareva
TopCoder Member