DP Problem - Codeforces

Блог пользователя Igor.Ivanich

Автор Igor.Ivanich, 15 лет назад, По-английски

Hi Everyone,

Please give me some hints about this problem:
http://online-judge.uva.es/p/v100/10032.html

I've been stuck on it for a week but getting TLE,
the DP state of my program is:

dp(total_weight, current_index, remaining person) = min(dp(tot_weight - v[i], current_index + 1, remaining person - 1), dp(tot_weight, current_index + 1, remaining));

As I said my solution gets TLE. because of huge size of my memoization array.

Thanks in Advance.

dp, uva

Igor.Ivanich
15 лет назад
21

Комментарии (21)

Написать комментарий?

yahooo

15 лет назад, скрыть # |

← Rev. 11 →

ignor

→ Ответить

brunoja

15 лет назад, скрыть # |

← Rev. 2 →

Hi,

I think you will need the bottom up DP, like a knapsack DP. You will have three dimensions, weight x people x used. It will be O(w*p*u), just like you did with a recursive DP (that will tle). The trick is that you dont need the used dimension, you keep the min and max people you used to get to that object and weight, with the last column (weight) you check which rows have the people/2 between min and max, it is, have difference of at most 1 in the groups (choosing the best weight of course).. If I was not clear please let me know :)

I read at the forums that people are getting accepted using a greedy solution. I dont know if its true, maybe the test cases are weak (just like many others uva problems)..

→ Ответить

Igor.Ivanich

15 лет назад, скрыть # ^ |

Thanks brunoja for helping, Unfortunately I didn't get the idea, could u please
explain more.

→ Ответить

brunoja

15 лет назад, скрыть # ^ |

← Rev. 5 →

Ok, lets go by parts, it will be easier to point out which part you did not understand:

Lets define the dimensions weight (row), people (column) and used (the third dimension, depth) and our matrix lets call it memo. You process the DP from the first column to the last column, on the first column there is the first person, second column is the second and so on. If memo[w][p][u] (w is weight, p is the pth person, and u is used for the first group of people) is set to 1, it means you reach that weight, using only the people from 0 to p and with a used group size of u. The kind of pseudo-code:

http://pastebin.com/5ct7Aju8

Ok, the answer will be on the last column, that will tle, its like you did, but you used a recursive DP. O(w*p*u), where the max values are 45000, 100 and 50, ~~that is big and wont fit the time (if there was only one test case I think that would go).~~

Alias is right, my solution is wrong (removed it from my comment, its on the old revisions)! I got accepted with that o.O

→ Ответить

goo.gl_SsAhv

15 лет назад, скрыть # ^ |

← Rev. 3 →

I think your solution is wrong. There can be gaps in your DP, so min and max say nothing.

For example we have 4 persons - 1 1 1 3, weight 3 can be obtained using 1 person, or 3 persons, but it can't be reached using two of them.

Look at my comment bellow, there you can find right and fast solution.

→ Ответить

Igor.Ivanich

15 лет назад, скрыть # ^ |

← Rev. 2 →

@Alias: did u deleted ur comments? Because I've received an E-Mail
from Codeforces that you've commented on my blogpost, but I didn't find any!

→ Ответить

goo.gl_SsAhv

15 лет назад, скрыть # ^ |

← Rev. 2 →

I think it is in russian interface, sorry, there is a stupid system - by default language of my comment is russian

→ Ответить

goo.gl_SsAhv

15 лет назад, скрыть # |

← Rev. 3 →

-8

Use bitmasks

upd: look at this code, it can be optimized to work 32 times faster

let's dp[i] will be binary vector, then

for (int i = MAXV * MAXN / 2 - 1; i >= 0; i--)

if (dp[used][i])

dp[used + 1][i + x] = 1;

can be writen as dp[used + 1] |= dp[used] << x;

upd2: code

→ Ответить

goo.gl_SsAhv

15 лет назад, скрыть # |

Use bitmasks

upd: look at this code, it can be optimized to work 32 times faster

let's dp[i] will be binary vector, then

for (int i = MAXV * MAXN / 2 - 1; i >= 0; i--)

if (dp[used][i])

dp[used + 1][i + x] = 1;

can be writen as dp[used + 1] |= dp[used] << x;

upd2: code

→ Ответить

brunoja

15 лет назад, скрыть # ^ |

Wow, that runs really fast! Thank you Alias for the tip!

Igor.Ivanich, Alias tip is to use a bitmask (the bitset) for the weight dimension. So if you understand the firsts paragraphs that I wrote you will be able to understand his code!

Sorry for my wrong solution :/ (I strike-through the wrong part I wrote)

→ Ответить

KiAsaGibona

13 лет назад, скрыть # ^ |

Hello goo.gl_SsAhv

Can you explain why you are using for(int i=MAXV * MAXN / 2 -1; i >= 0; i--), Why are you starting from one less than MAXV*MAXN/2 Shouldn't it be for(int i= MAXV * MAXN / 2; i >= 0; i--)

Thanks in advance :)

→ Ответить