Gotchas all around! 😀 In fact, this time I’ve struggled with the algorithm to solve the problem. My first attempt did work, but could only solve correctly the small input of the problem, entitled Ocean View. It’s not complicated as a problem, but this time you need to think a bit more to get there:

Ocean View is a small town on the edge of a small lake, populated by people with high self-esteem. There is only one street in this town, Awesome Boulevard, running away from the lake on the west towards the hill in the east. All of the houses in Ocean View are situated along one side of Awesome Boulevard and are numbered starting at #1 on the edge of the lake all the way up to #N at the foot of the hill.

Each resident of Ocean View wants to be able to see the lake. Unfortunately, some of the houses may be blocking the view for some of the higher numbered houses. House #A blocks the view for house #B whenever A is smaller than B, but house #A is as tall as or taller than house #B.

Tired of hearing complaints about obstructed views, the Supreme Ruler of Ocean View has decided to solve the problem using his favorite tool of governance — violence. He will order his guards to destroy some of the houses on Awesome Boulevard in order to ensure that every remaining house has a view of the lake. Of course, if he destroys too many houses, he might have a rebellion to deal with, so he would like to destroy as few houses as possible.

What is the smallest number of houses that need to be destroyed in order to ensure that every remaining house has an unobstructed view of the lake?

It needs a little bit of thinking to understand (not if you have previously worked on it), but the general concept is: you have to find the longest increasing subsequence in a list of numbers. Yes, I didn’t know how “classic” it was, it even has its own Wikipedia entry. My lack of knowledge led me to my first solution, coded in a way that it would just solve the problem, even if not optimized:

for case in range(1,int(raw_input())+1):                #For all test cases
        size = int(raw_input())                         #Get the case size
        heights = []
        paths = []

        for i in raw_input().split(" "):                #Split the case values by spaces
                heights.append(int(i))                  #Store its values as integers

        paths.append([heights[0]])                      #Starts first list with first value
        for i in range(1, size):                        #Iterate from second member on
                for path in paths:                      #For every path
                        if heights[i] > max(path):      #Is the current height bigger than my maximum?
                                path.append(heights[i]) #Append its value, so it will be crescent
                        else:
                                path.append(0)          #Else, ignore it

                paths.append(heights[:i+1])             #Create a new path with the heights so far
                cur_num = paths[-1][-1]                 #Get the current height

                for j in reversed(range(0, i)):         #Iterate down to the first height
                        if cur_num > heights[j]:        #If the next value is smaller, keep it
                                cur_num = heights[j]
                        else:
                                paths[-1][j] = 0        #If it's not smaller, ignore it

        min_houses = size
        for path in paths:
                min_houses = min(min_houses, path.count(0)) #Get the path with least ignored members

        print "Case #%d: %d" % (case, min_houses)

As I said, not a good example of resource usage, but “works”. The thing is, while brainstorming a bit with a friend (who introduced me to the Dynamic Programming concept), I’ve found that my first attempt had a little bug (didn’t took time to debug it though): it will ignore possibilities with subsequent “out-of-order” nodes:

list = [ 1, 2, 4, 3, 6, 5, 7, 8 ]
path[0] = [ 1, 2, 0, 3, 6, 0, 7, 8 ]
path[1] = [ 1, 2, 4, 0, 6, 0, 7, 8 ]
path[2] = [ 1, 2, 4, 0, 0, 5, 7, 8 ]

As you can see, there’s the not covered possibility [ 1, 2, 0, 3, 0, 5, 7, 8], enough to invalidate the solution. As it was already a bad solution, I decided to use the wikipedia algorithm to solve the problem:

'''
 L = 0
 for i = 1, 2, ... n:
    binary search for the largest positive j ≤ L
      such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
    P[i] = M[j]
    if j == L or X[i] < X[M[j+1]]:
       M[j+1] = i
       L = max(L, j+1)
'''
for i in range(size):                                          #For all the sequence
                j = 0
                for k in range(length+1):                              #For all the sequence until the current length
                        if heights[pointers[k]] < heights[i]:          #Compare the values on pointers to the current value
                                j = max(j, k)                          #Get the maximum value index

                if j == length or heights[i] < heights[pointers[j+1]]: #If the value is a "keeper"
                        pointers[j+1] = i                              #Keeps its index
                        length = max(length, j+1)                      #Update the length

But, that algorithm has a minor bug: when “length == size”, the index keeping will fail, because j+1 exceeds the pointers list size. So, I’ve added a check for “j < size” before it. The bug only happens at the last iteration anyway, we don’t need to store its index anyway. Perhaps it can be “avoided” with a bigger than “size” pointer list.

The final, validated, solution becomes:

for case in range(1,int(raw_input())+1):                               #For all test cases
        size = int(raw_input())                                        #Get the case size
        heights = []
        pointers = [0] * size                                          #Create the pointer list
        length = 0                                                     #Sequence length

        for i in raw_input().split(" "):                               #Split the case values by spaces
                heights.append(int(i))                                 #Store its values as integers

        for i in range(size):                                          #For all the sequence
                j = 0
                for k in range(length+1):                              #For all the sequence until the current length
                        if heights[pointers[k]] < heights[i]:          #Compare the values on pointers to the current value
                                j = max(j, k)                          #Get the maximum value index

                if j == length or heights[i] < heights[pointers[j+1]]: #If the value is a "keeper"
                        if j < size-1:
                                pointers[j+1] = i                      #Keeps its index
                        length = max(length, j+1)                      #Update the length

        print "Case #%d: %d" % (case, size-length)

Until the next Jam!