Sumanto's blog

CSES PROBLEM:Book Shops II. Help needed
By Sumanto, history, 4 years ago, In English

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
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Are you talking about binary lifting?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        so How to decide whether it will be optimal to have copies of that book or not ?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              ← Rev. 3   Vote: I like it +7 Vote: I do not like it

              This approach is similar to binary lifting I guess link for this question solution using binary lifting.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      O(n*x) as only this much of states are visited and each state is computed in o(1) time

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

    → Reply