JOIN
 Match Editorial
SRM 285
Tuesday, January 24, 2006

Match summary

Each of the problems presented to the competitors have at least two fundamentally different solutions and this may explain the high success rate even for the harder problems. The Division 1 winner is rem with the highest score for the hard problem. bmerry, wleite and andrewzta placed second to forth correspondingly. marek.cygan who was the first coder to submit a correct solution for the 1000th problem took fifth place.

The Division 2 winner is knuckleslives followed by two newcomers pawko and jackiex.

# The Problems

Used as: Division Two - Level One:
 Value 250 Submission Rate 296 / 384 (77.08%) Success Rate 237 / 296 (80.07%) High Score fpavetic for 248.66 points (2 mins 5 secs) Average Score 203.60 (for 237 correct submissions)

The solution for this problem is straightforward. Obviously the discarded baskets should have smaller number of apples then the remaining. So we just need to sort the baskets and choose the best answer for all possible numbers of discarded baskets. Here is the sample solution:

```    public int removeExcess(int[] apples) {
Arrays.sort(apples);
int ans = 0;
for(int i=0; i<apples.length; i++) {
ans = Math.max(ans, (apples.length - i) * apples[i]);
}
return ans;
}
```

SentenceSplitting
Used as: Division Two - Level Two:
 Value 500 Submission Rate 90 / 384 (23.44%) Success Rate 30 / 90 (33.33%) High Score RodrigoBurgos for 441.83 points (10 mins 35 secs) Average Score 284.21 (for 30 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 273 / 317 (86.12%) Success Rate 198 / 273 (72.53%) High Score Im2Good for 244.57 points (4 mins 15 secs) Average Score 179.76 (for 198 correct submissions)

The easiest way to solve the problem is to try all possible values of the text width and choose the smallest value which satisfies the problem statement. For a given width of the text we can greedy add words to the current line, unless their total length exceeds the width. After that we put the line break and go to the next line. If the total number of lines will not exceed K + 1, the width considered satisfying the problem statement. The sample solution goes further:

```    public int split(String sentence, int K) {
String[] words = sentence.split(" ");
for(int ln = 1; ln <= sentence.length(); ln++) {
if (can(words, K, ln))
return ln;
}
return -1;
}

private boolean can(String[] words, int k, int ln) {
int l = -1;
for (String s : words) {
if (l + 1 + s.length() > ln) {
k--;
if (k < 0)
return false;
l = s.length();
if (l  > ln)
return false;
} else {
l += 1 + s.length();
}
}
return true;
}

```

A lot of coders used more complex dynamic programming algorithms, calculating for example the answer for all possible substrings and all allowable numbers of lines.

OperationsArrangement
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 64 / 384 (16.67%) Success Rate 13 / 64 (20.31%) High Score michu23 for 739.51 points (18 mins 16 secs) Average Score 548.30 (for 13 correct submissions)

If given sequences contains zero digit, all operators in the result string will be '*', because the value of the expression will be minimal possible - zero and '*' comes before '+' lexicographically.
For all other cases it is easy to show that the following algorithm is correct. We will iterate from left to right, putting the operators and calculating the current result of continuous multiplication. If the current digit is B and current product is P, we should put the '+' operator if and only if B * P > B + P. Here is the solution written by brett1479:

```public String arrange(String sequence) {
String ret = sequence.charAt(0)+"";
if (sequence.indexOf("0")!=-1) {
for (int i = 1; i < sequence.length(); i++) ret += "*" + sequence.charAt(i);
return ret;
}
int acc = sequence.charAt(0)-'0';
for (int i = 1; i < sequence.length(); i++) {
char c = sequence.charAt(i);
if (acc*(c-'0') > acc+(c-'0')) {
ret += "+"+c;
acc = c-'0';
} else {
ret += "*"+c;
acc *= c-'0';
}
}
return ret;
}

```

Dynamic programming solution was also possible for this problem.

RobotTesting
Used as: Division One - Level Two:
 Value 500 Submission Rate 181 / 317 (57.10%) Success Rate 132 / 181 (72.93%) High Score b285714 for 449.39 points (9 mins 45 secs) Average Score 319.83 (for 132 correct submissions)

Let's put one robot to each cell, resulting N*N robots on the grid. We will calculate the number of commands all robots will do in total before stop. Obviously the answer will be equal to the calculated number of commands divided by the number of robots N*N. Each robot will do no more then 50000 moves, so we can calculate the number of "live" robots for each move by simulating the process.

All "live" robots on each move will form a rectangle, which can be defined by coordinates of two opposite vertices. The total number of commands is equal to the sum of counts of "live" robots during all steps of simulation.

Here is the sample C++ solution by BenjaminHummel:

```double estimateCommands(int N, string program) {

long long sum = 0;
int xmin = 0, xmax = 0, ymin = 0, ymax = 0;
int x = 0, y = 0;
int ps = program.size ();

for (int i = 0; i < 50000; ++i) {
xmin <?= x;
xmax >?= x;
ymin <?= y;
ymax >?= y;

int dx = xmax - xmin;
int dy = ymax - ymin;

if (dx >= N || dy >= N) break;

sum += (N - dx) * (N - dy);

switch (program[i % ps]) {
case 'U': ++y; break;
case 'D': --y; break;
case 'L': --x; break;
case 'R': ++x; break;
}
}

return (double)sum / (N*N);
}
```
Distincter
Used as: Division One - Level Three:
 Value 1000 Submission Rate 30 / 317 (9.46%) Success Rate 22 / 30 (73.33%) High Score rem for 835.45 points (13 mins 9 secs) Average Score 629.53 (for 22 correct submissions)

We will solve the problem using the dynamic programming.

First step is to sort the numbers in ascending order. After sorting we can assume that performing operations will not change the order of the numbers.

Let's define A(i, j, k) as a number of operations required to make k distinct numbers using first i elements so that i-th element is not greater then j. To calculate A(i, j, k) we should choose best from two choices:

• A(i, j-1, k), which means that we are not going to make sequence[i] equals to j;
• A(i-1, j-1, k-1) + abs(sequence[i] - j), which means that we are going to make sequence[i] equals to j in order to increase number of distinct numbers and abs(sequence[i] - j) is a number of operations required to make sequence[i] be equal to j.

So the final formula is:

A(i, j, k) = min(A(i, j-1, k), A(i-1, j-1, k-1) + abs(sequence[i] - j))

As a sample solution you can take the fastest coded solution by rem.

By Andrew_Lazarev
TopCoder Member