JOIN Match Editorial
SRM 366
Tuesday, September 18, 2007

## 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

SerialNumbers  Used as: Division Two - Level One:
 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;
}
```

ChangingSounds  Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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[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;
}
```

PickGuitars  Used as: Division Two - Level Three:
 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.

GuitarConcert  Used as: Division One - Level Two:
 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.
Where most coders implemented the first 3 steps correct, a couple of coders failed on the 4th step. There were several ways to implement it, but the best way to do it (in my opinion) was the following:

Before you do the brute force search, sort all guitars by name (and of course sort guitarSongs accordingly). Now, instead of using the rightmost bit to represent the first guitar in the list, we use the leftmost bit to represent it. This way, we are sure that if 2 bitmasks have the same number of bits, the greatest of the 2 will represent the list of guitars that comes first alphabetically. So in the loop there is no need to check for the alphabetically first items, we just check if either the number of songs is bigger then the best so far, or the number of songs is the same and the number of guitars is smaller or equal then the best so far. Because we try the bitmasks in increasing order, we are sure that we find the alphabetically first solution this way.

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]);
}
}
}
```
Now, if we have updated all states, we can find the final answer by taking the lowest answer in the table for the concert hall position where timeLeft = 0, looking at all 4 directions (we don't care which way we entered the concert hall). If the smallest is INF, we couldn't reach the concert hall and we return -1. Otherwise, we return the lowest answer we've found.  