taap_cader's blog

By taap_cader, history, 5 months ago, In English

Suppose there is an array of integers representing values of blocks. We have to create towers such that (i)th block in tower has value less than or equal to (i-1)th.
a. Calculate the height of tallest tower.
b. Calculate the minimum number of towers to equip all the blocks.
Obviously, the the answer of first part is longest decreasing array. I am not sure about second part but according to me the answer will the longest strictly increasing array.
Correct me if I am wrong.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

You are correct about the first one. For the second one, you can maintain a list of integers in a set and add onto the one in the set that is greater than or equal to a[i], and erase the found integer. If no such integer exists, add that number to the set. The answer is just the size of the set. Here is an example algorithm.

a := [3, 1, 4, 6, 2]

s := binary search tree set

s = {}

is set not empty? no insert into set

s = {3}

is set not empty? yes. what number is greater than or equal to 3? 1

s = {1}

is set not empty? yes. what number is greater than or equal to 4? doesn't exist, add to set

s = {1, 4}

is set not empty? yes. what number is greater than or equal to 6? doesn't exist, add to set

s = {1, 4, 6}

is set not empty? yes, what number is greater than or equal to 2? 4.

s = {1, 2, 6}

print(s -> size)

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

    I guess you are doing the same thing just in O(nlogn) time. Can you suggest some test in which your answer will differ from my proposed solution(LIS).

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

      Nop.

      This is a cses problem, btw.

      You can test your code there.

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

        I tried my solution and it got accepted. Thanks in between for telling about cses. What you are doing is also O(nlogn) version of lis(not dp version).