Match Editorial

Match summary

The Division I coders got a relatively easy set today, so speed did matter a lot. The easy problem was a pretty straightforward one, which most coders solved within a few minutes. The medium problem looked like simple brute force, but a few tricky corner cases made the problem slightly harder. The hard problem seemed to be really easy, but after a clarification came a couple of coders had to resubmit it and lost a lot of points. Because it was a close race, the challenge phase was quite important for the final score. Although tomekkulczynski was one of the people who had to resubmit the hard problem, he won the match because of his 5 successful challenges. Within a range of 50 points, ACRush and myprasanna (a new red-ranked Indian) became 2nd and 3rd.

In Division II coders faced an average easy problem, a slightly harder than usual medium, and a bit of a tricky hard problem, with only 12 correct submissions. The top 3 finishers are all newcomers: zhuojie, janezb and ryuwonha.

The Problems

Value	250
Submission Rate	367 / 446 (82.29%)
Success Rate	278 / 367 (75.75%)
High Score	IdNotFound for 246.71 points (3 mins 17 secs)
Average Score	188.23 (for 278 correct submissions)

This was mainly a problem that needed a careful implementation of the steps described in the problem statement. To do the sorting, we could use the standard libraries with our own compare function, or we could write our own sorting algorithm, for example Bubble sort. The compare function should implement the steps descibed in the problem statement, using your own function to add the digits in a string. An example solution could look like:

boolean isSmaller(String a, String b) {
   if (a.length() != b.length())
      return a.length() > b.length();
   if (sumOfDigits(a) != sumOfDigits(b))
      return sumOfDigits(b) < sumOfDigits(a);
   return a.compareTo(b) > 0;
}

int sumOfDigits(String x) {
   int s = 0;
   for(int i = 0; i < x.length(); i++)
      if(x.charAt(i) > '0' && x.charAt(i) <= '9')
         s += x.charAt(i) - '0';
   
   return s;
}

Value	500
Submission Rate	241 / 446 (54.04%)
Success Rate	94 / 241 (39.00%)
High Score	ryuwonha for 488.62 points (4 mins 21 secs)
Average Score	359.94 (for 94 correct submissions)

Value	250
Submission Rate	418 / 439 (95.22%)
Success Rate	354 / 418 (84.69%)
High Score	Jan_Kuipers for 247.92 points (2 mins 36 secs)
Average Score	222.33 (for 354 correct submissions)

The key to this problem is that it is a typical dynamic programming problem. To solve it you should make a 2-dimensional boolean array where element i, j indicates if you are able to play song i with sound level j. Initially, you set 0, beginLevel to true, and then iterate through all songs and sound levels where for each song i you update the values at i+1. See the solution below for this approach.

Alternatively, this problem could also be solved using recursion with memoization; see turuthok's solution for a clear implementation of this.

public int maxFinal(int[] changeIntervals, int beginLevel, int maxLevel) {
   boolean[][] canHave = new boolean[changeIntervals.length+1][maxLevel+1];
   for(int i = 0; i <= changeIntervals.length; i++)
      Arrays.fill(canHave[i], false);
   
   canHave[0][beginLevel] = true;
   for(int i = 0; i < changeIntervals.length; i++) {
      for(int j = 0; j <= maxLevel; j++) {
         if(canHave[i][j]) {
            if(j + changeIntervals[i] <= maxLevel)
               canHave[i+1][j + changeIntervals[i]] = true;
            if(j - changeIntervals[i] >= 0)
               canHave[i+1][j - changeIntervals[i]] = true;
         }
      }
   }
   
   int max = -1;
   for(int j = 0; j <= maxLevel; j++)
      if(canHave[changeIntervals.length][j])
         max = j;
   
   return max;
}

Value	1000
Submission Rate	38 / 446 (8.52%)
Success Rate	12 / 38 (31.58%)
High Score	ryuwonha for 855.59 points (12 mins 5 secs)
Average Score	597.91 (for 12 correct submissions)

Before one can solve this problem, some insights about the problem are needed. The first thing is that, as soon as we picked the first guitar, we no longer have a circle, but we can think about the guitars as if they were in a line.

Now let's see if we can write a function f(begin,end), that calculates the maximum score for guitars begin to end. First of all, we know that if begin > end, we cannot pick any guitars anymore, so the return value will be 0. Otherwise, it is not hard to see that if we pick guitar i (where begin <= i <= end), our score for this range will be sum - f(begin,i-1) - f(i+1,end) (where sum is the sum of all guitar values from begin to end). So, if we want to calculate f(begin,end), we can just loop over all i's from begin to end, and returning the maximum value among them. To make sure this function will run in time, we should memoize the calculated values in a 2-dimensional array.

Now that we have function that can determine the maximum value between a certain range, the last thing to do is decide which guitar we should choose first. As in function f, we can loop over all guitars i (out of n as a possibility for our first pick). If we pick guitar i, then we should place guitars i+1 to i-1 (in that order) in a new array and call our function f to find the maximum value that the other player will get in that range. Now our total value will be sum - f(0,n-1), and finding the maximum of that in all values i gives us the answer.

For a clean implementation of this solution, see hotmagic's solution.

Value	500
Submission Rate	386 / 439 (87.93%)
Success Rate	241 / 386 (62.44%)
High Score	marek.cygan for 483.43 points (5 mins 17 secs)
Average Score	357.29 (for 241 correct submissions)

With a constraint of a maximum of 10 guitars, this problem looked quite easy for a Div 1 medium problem. Because 2^10 = 1024 easily runs within the time limit, we can brute force all possible combinations of guitars we might want to buy. To do this, we use bitmasks (see this article for more information about bitmasks). For each bitmask, we do the following:

1. Calculate the number of songs we can play with these guitars, and how many guitars we would need for it.
2. Check if the number of songs we can play is bigger than, or equal to, the maximum number of songs we could play in the best solution we have found so far. If it is bigger we can use this as the best solution, if it is smaller we do not.
3. If the number of songs we can play is equal to the best so far, we check if this solution uses less guitars. If it does, we use this as the best solution; if it uses more we don't.
4. If the number of guitars is also the same, then check if this solution is alphabetically smaller then the best solution so far.

LateForConcert
Used as: Division One - Level Three:

Value	1000
Submission Rate	180 / 439 (41.00%)
Success Rate	98 / 180 (54.44%)
High Score	konqueror for 824.74 points (13 mins 42 secs)
Average Score	539.78 (for 98 correct submissions)

While this problem could look like an adaption of a shortest path algorithm at first, it turned out that there is a much easier solution to the problem. If we think about it, a state can be defined as 4 integers: (x, y, timeLeft, lastmove). We know that x and y can both be 49 at most, timeLeft can be 100 at most, and, because we can only make 4 different moves, lastmove will be between 0 and 3. So, if we make a 4-dimensional double table, it has a worst case size of 50*50*101*4 = 1010000, which is small enough to stay within time limits and memory bounds.

Initially, we make sure that every element in the table is set to a big enough value (let's call it INF), and we set your initial position at timeLeft for all different moves to 0. Now we loop over all possible values, and for a certain state (x, y, t, m), we can update the table as follows:

for(int d = 0; d < 4; d++)
   if(d == inv[m]) continue; // To make sure we do not go back
   switch(cityMap[y].charAt(x)) {
      case 'X':
      case 'C':
         continue;
      case '.':
      case 'Y':
         if(x+dirx[d] > 0 && x+dirx[d] < width &&
            y+diry[d] > 0 && y+diry[d] < height)
            table[x+dirx[d]][y+diry[d]][t-1][d] = Math.min(
                  table[x+dirx[d]][y+diry[d]][t-1][d],
                  table[x][y][t][d]);
      case 'S':
         if(x+dirx[d] > 0 && x+dirx[d] < width &&
            y+diry[d] > 0 && y+diry[d] < height)
            table[x+dirx[d]][y+diry[d]][t-1][d] = Math.min(
                  table[x+dirx[d]][y+diry[d]][t-1][d],
                  table[x][y][t][d] + speedingTicket);
      case 'T':
         if(x+dirx[d] > 0 && x+dirx[d] < width &&
            y+diry[d] > 0 && y+diry[d] < height) {
            table[x+dirx[d]][y+diry[d]][t-1][d] = Math.min(
                  table[x+dirx[d]][y+diry[d]][t-1][d],
                  table[x][y][t][d] + redLight);
            if(t > 2)
               table[x+dirx[d]][y+diry[d]][t-2][d] = Math.min(
                     table[x+dirx[d]][y+diry[d]][t-2][d],
                     table[x][y][t][d]);
         }
   }
}