| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | SecondThread | 145 |
| 9 | pajenegod | 145 |
https://cses.fi/problemset/task/1159/
In this problem I used 0-1 knapsack to solve but got time limit exceeded. My approach to handle copies was to make duplicates of those items and apply knapsack. But it failed to pass few of the test cases(TLE). Any help will be appreciated.
This one was kinda weird (but cool imo). Think about splitting each of your books into powers of twos ;).
Are you talking about binary lifting?
No, still do knapsack, but don't make a copy of every book. Make copies of certain sizes.
Actually ig you could call it binary lifting, though i've never heard it called that in this context.
so How to decide whether it will be optimal to have copies of that book or not ?
Every number can be created out of powers of two right? If you split the books into powers of two (with special care on the final part if it is not equal to 2^k — 1), you can then treat it has having log(n) separate books of only one copy but multiply the price and pages by the power of two representing its size, because no matter which subset your knapsack algo ends up choosing, it will always be an obtainable number of books, but there are only nlogn total books so it won't tle.
How do we find these splits if x is not of form $$$2^k-1$$$?
This approach is similar to binary lifting I guess link for this question solution using binary lifting.
Ok, just to check if I get this code right, example $$$x=1011_2$$$, then we create a list of all binary numbers up to the highest bit, and add as a last element the difference from these single bits to x.
$$$0001_2, 0010_2, 0100_2$$$
$$$1011_2-0001_2-0010_2-0100_2=0100_2$$$
From the resulting list of numbers we can sum every number from 1 to x, but none bigger than x. Clever.
U can just apply knapsack Dp with a modified trick .
Let dp[i][j] (just make only dp[2][100005] to avoid MLE and swap these ) denote the maximum number of pages if i have used upto i positioned books only . Then my answer would be dp[n][x]. Initially whole array is zero . Now for computing the dp states at position i , iterate over j from 0 to h[i] and inside of that iterate over all j+k*h[i] where k>0 , now carefully observe that dp[i][j] = max(dp[i-1][j], dp[i-1][j-h[i]] + s[i] , dp[i-1][j-2*h[i]] + 2*s[i]).. and by iterating over these states we can easily do it using a deque where we will store the max value of above expression and at max k elements are allowed .. It is exactly same as max in all subarrays of length k[i] .
If needed , u can refer my code https://pastebin.com/RCiKvwn7
I am not so good at explaining , sorry for that
If there seems a fault , please point that out
Wow, i did'nt expected to be this hard. Well can you tell what's the time complexity of your approach, i am not able to get it?
O(n*x) as only this much of states are visited and each state is computed in o(1) time
Could you tell why is ternary search wrong on this , as dp is always increasing, so the function is unimodal
My code: link
See this submission you could see dp in increasing always, so dp[wt-j*a] + j*b is unimodal, but still I am getting wa on some cases