edem.kwadzo's blog

dp solution for Timus 1005
By edem.kwadzo, 13 years ago, In English

Hi Guys,
can anyone help me solve this problem using DP ? is that even possible ?

http://acm.timus.ru/problem.aspx?space=1&num=1005

So far only the brute force (generate all permutations) approach seems to be working.

Many thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Use bit-masks. Take a integer number and look at its bits. If i-bit is 1, then we put stone i+1 in first pile, else in second pile. You need check all numbers between 0 and 2^N - 1 (all possible variants of ones).
It's not DP, but it's fast brut force O (N * 2^N). Also this task can be solved by time O (N * 2^(N/2)) with method meet-in-middle.

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For dp solution you can use idea of Knapsack problem.

dp[i][j] = true iff using some of i first stones we can get the pile of weight j.

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    In this case, we must open the matrix dp[20][2000000]. This is approximately 40 mb, but we have only 16 mb memory limit
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      No. We don't need to store all 20 lines. We need only 2 lines for calculate dp.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Explain please
        → Reply
        • 13 years ago, # ^ |
          ← Rev. 3   Vote: I like it +1 Vote: I do not like it

          Look. Let f[i][j]=1 if using some of i first stones we can get the pile of weight j. 

          Then f[i][j]=f[i-1][j] | f[i-1][j-a[i]]; 

          So we need only f[i-1][] to calculate f[i][].

          UPD. We need only 1 line:
          f[0]=1;
          for (int i=1;i<=n;i++) for (int j=m;j>=a[i];j--) f[j]|=f[j-a[i]];
          → Reply
        • 13 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it
          Do not listen to Tranvick =) You need to store 1 line only! - this is only 2 Mb of memory, or 250Kb at all if you use bit operations! So, the problem could be solved by DP even in Pascal!
          → Reply
          • 13 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Exactly =) I forgot about it. But with 2 lines it'll work also, only 4 Mb(or 500 Kb) of 16 Mb. 

            → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
This is classic problem, for the dynamical programming with using bimasks. A bit more difficult task when you have 34 stones
→ Reply