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
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
2 | cry | 160 |
4 | nor | 156 |
4 | atcoder_official | 156 |
6 | -is-this-fft- | 155 |
7 | adamant | 153 |
7 | maroonrk | 153 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
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
Name |
---|
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.
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.
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]];
Exactly =) I forgot about it. But with 2 lines it'll work also, only 4 Mb(or 500 Kb) of 16 Mb.
Divide-and-conquer technique solves this problem in O(2^(N/2)*N)