Match Editorial

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

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;
    }

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)

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.

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.

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);
}

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:

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