SRM 596: Lack of speed will kill you

Well, that it is , a not great day because I took too long to solve 250 points and the other problems seem too hard. Starting this at 11:55.

Div1 250: The one with sequences

You start with a sequence of n zeros. You want to convert it into a desired sequence. There are two allowed moves: a) Increment a single element by 1. b) Multiple all of the elements by 2. The elements of desired are non-negatives less than 1001.

I noticed right away that you can first decide the number of double operations because you will need at most 9 (Multiply 1 by 2 ten times and you get 1024). So the rest is an easy subproblem: For each element in the desired sequence, find the minimum number of increments you need if you are going to multiply by 2 a fixed number of times. I used dynamic programming, maybe there is an easier method.

static const int MAX     = 1000;
static const int MAX_N   = 50;
static const int MAX_LOG = 11;
static const int INF     = MAX_N * MAX;

vector<int> desiredArray;

int mem[MAX + 1][MAX + 1][MAX_LOG + 1];
int rec(int x, int y, int d)
{
    int & res = mem[x][y][d];
    if (res == -1) {
        res = INF;
        if (x == y) {
            res = 0;
        } else {
            //increment
            if (x  + 1 <= y) {
                res = 1 + rec(x + 1, y, d);
            }
            //double
            if ( (2*x <= y) && (d > 0) ) {
                res = std::min(res,  rec(2 * x, y, d - 1) );
            }
        }
    }
    return res;
}

int getMin(vector<int> desiredArray)
{
    int res = INF;
    memset(mem, -1, sizeof(mem));
    for (int d = 0; d <= MAX_LOG; d++) {
        // If we do the double operation d times, what is the minimum number
        // of increment moves each element needs?
        int m = d;
        for (int x: desiredArray) {
            m += rec(0, x, d); 
        }
        res = std::min(res, m);
    }
    return res;
}

I took way too long to code. Everyone in the division summary had far better scores than I.

Update: During the challenge phase, I noticed that the answer is equal to the maximum number of bits (if not 0) plus the sum of 1 bits. Makes sense. I wish I coded my dp faster.

Div1 500: The one with bits

This problem strikes me as having too many complicating factors. I am starting to think that it is a brute force problem. Right now trying to think of a way to do that, but with 13 minutes left I doubt I will be able to do anything. My 250 score is too low, my only hope is that there is a greedy solution to 250 that most people are usuing and it is wrong, but I doubt that to be the case. I think the "Fix number of doubling" solution is straightforward to see and can't think of anything else.

Programming this post to appear exactly as the match ends.

Update

Now they are gonna have an update. This is the kind of matches that makes me hate the 250-500-1000 strategy. Putting two greedy problems in the first two slots ensures that even if I get to solve them, it will be low score and a wasted match. At least focusing on 1000 would be more interesting, and a low score in a match where everyone solve 2 problems is as disastrous for rating as a zero score anyway.

Wish I could opt out of writing the editorial ( I cannot ), also without practice rooms it will delay development of the editorial too. Just awful.