CSES PROBLEM:Book Shops II. Help needed

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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.

My Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define _READ freopen("input.txt", "r", stdin);
#define _FAST                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
int32_t main()
{
    _FAST
    int n,w;
    cin>>n>>w;
    vector<int> dp(w+1,0);
    //dp[weight]-->maximum price can have using 
    vector<int> h(n),s(n),k(n);
    for(auto &i:h)
        cin>>i;
    for(auto &i:s)
        cin>>i;
    for(auto &i:k)
        cin>>i;
    vector<pair<int,int>> v;//weight,price
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<k[i];j++)
        {
            v.push_back({h[i],s[i]});
        }
    }
    int m=v.size();
    for(int i=0;i<m;i++)
    {
        int price=v[i].S;
        int weight=v[i].F;
        for(int j=w;j-weight>=0;j--)
            dp[j]=max(dp[j],dp[j-weight]+price);
    }
    cout<<dp[w];
    return 0;
}

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

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

SuperJ6

4 года назад, # |

This one was kinda weird (but cool imo). Think about splitting each of your books into powers of twos ;).

→ Ответить

Sumanto

4 года назад, # ^ |

Are you talking about binary lifting?

← Rev. 2 →

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.

spookywooky

How do we find these splits if x is not of form $$$2^k-1$$$?

navneet.h

← Rev. 3 →

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.

CoderAnshu

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

Блог пользователя Sumanto