Friday, November 01, 2013

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.

1 comment : Miki said...

Hi! Here is my greedy solution for 250, together with a short explanation.

At first, let's think about a single number only. What is the best strategy for it? Well, when we have 2 different sequences S1 and S2 of increments and doubling, then if they are of the same length, the better one is the one with more doublings. This is because doubling takes as much as an increment, and may help with other numbers as well.

Let's also notice, that it is impossible, to have 2 sequences S1 and S2 which lead us to a specific number, where in S1 we have more doublings then in S2 and the length of S1 is more then S2. This is because an increment can not increase a number by more then doubling, so S2 has to have at least as many increments as S1 + the difference in doublings.

From the above 2 observations, we have that the best way is to choose for each number a sequence, which is the shortest and with the maximum number of doublings (among the shortest sequences). Such sequences will have maximum number of doublings at once.

After we choose the best sequence for each number, the result is the sum of all increments plus the maximum number of doubling in any sequence. This is an easy observation because of how the doublings are possible to perform so that each number is doubled only the number that is specified.

How to find the best sequence for a number? This can be done by Dynamic Programming: For each number n from 1 to 1000, just update the best solution for n+1 and 2*n.