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]) #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 = [ 1, 2, 0, 3, 6, 0, 7, 8 ]
path = [ 1, 2, 4, 0, 6, 0, 7, 8 ]
path = [ 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 =  * 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!