CSES PROBLEM:Book Shops II. Help needed

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

№	Пользователь	Вклад
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	142
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

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

6 лет назад, скрыть # |

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

→ Ответить

Sumanto

6 лет назад, скрыть # ^ |

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