MainuCodingBadiPasandAe's blog

By MainuCodingBadiPasandAe, history, 2 months ago, In English

I was solving CSES — Towers and came with an alternate problem which I think can be solved using DP somehow:

You are given n cubes in a certain order, and your task is to build towers using them. Whenever two cubes are one on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower, begin a new tower or discard the current cube. You may discard at most K cubes. What is the minimum possible number of towers?

Constraints:

(Don't worry about the constraints, if you can think of any polynomial-time solution, please let me know)

1 <= N <= 1e5,

1 <= cube sizes <= 1e9

0 <= K <= N

eg. N = 4; cubes = [3, 8, 2, 1]; K = 1

Output: 1

==> Discard cube with size 3 or 8 and use the rest to build 1 tower

Any ideas to solve this efficiently?

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by MainuCodingBadiPasandAe (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is not solvable.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by MainuCodingBadiPasandAe (previous revision, new revision, compare).

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I think this problem can be returned back to a Knapsack problem.

Let dp[i][j]= minimum number of towers can be formed from first i cubes ignoring at most j cubes of them.

I'm not sure, but I think that thinking this way will help us, can you help me to develop this idea ?

NOTE: I think this solution won't satisfy problem's constraints.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought of this before writing the blog. You are not storing sufficient information in your DP states. How would you make transitions? Even if you store a pair of ints (minimum number of towers, largest cube that is on top of any tower), you won't be able to make transitions.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 6   Vote: I like it 0 Vote: I do not like it

      My transition will be one of three:

      1- Add this cube [ith cube] (if I can) and update the upper value of my tower.

      2- Igonre this cube and increase j by one.

      3- Make a new tower then update ans and set upper value to infinity.

      Forget about constraints now and think about how to move between these states.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It is possible to think of a greedy way.

If we have only one tower and the height of the top cube is equal to h, then the optimal way is to put the nearest cube (from the right) whose height is smaller than h. If we don't find any suitable cube, then we start another tower by the first cube that has not been taken yet.

You can use a multiset to do it, the multiset will store the height of the top cube of each tower. Iterate over all cubes, the current cube will be putten above the smallest cube in the multiset which is greater than the current cube, now the current cube is the top of this tower, so you should erase the older top, if you can't find this greater cube, you should insert the current cube as a new tower.