Igor.Ivanich's blog

DP Problem
By Igor.Ivanich, 15 years ago, In English
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.


Tags dp, uva
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
15 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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)..

→ Reply
  • »
    »
    15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    Thanks brunoja for helping, Unfortunately I didn't get the idea, could u please
    explain more.
     
    → Reply
    • »
      »
      »
      15 years ago, hide # ^ |
      ← Rev. 5  
      Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        15 years ago, hide # ^ |
        ← Rev. 3  
        Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          15 years ago, hide # ^ |
          ← Rev. 2  
          Vote: I like it 0 Vote: I do not like it

          @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!

          → Reply
          • »
            »
            »
            »
            »
            »
            15 years ago, hide # ^ |
            ← Rev. 2  
            Vote: I like it 0 Vote: I do not like it

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

            → Reply
»
15 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    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)
    → Reply
  • »
    »
    13 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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 :)

    → Reply
»
13 years ago, hide # |
← Rev. 4  
Vote: I like it +3 Vote: I do not like it

I didn't use bitmasks or anything and got AC. I think it's just a dp problem without any other trick... Here's my code:uva10032

→ Reply
»
13 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

It seems this problem is not that easy.

→ Reply