CSES Towers with a twist

Revision en3, by TheBhediyaOfDalalStreet, 2022-10-06 11:34:47

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English TheBhediyaOfDalalStreet 2022-10-06 11:34:47 109 Relaxed constraints
en2 English TheBhediyaOfDalalStreet 2022-10-06 09:11:55 21 Tiny change: '(Not shit-post)\n\n\nI was solv' -> 'I was solv' (published)
en1 English TheBhediyaOfDalalStreet 2022-10-06 09:10:50 888 Initial revision (saved to drafts)