# CodeJam Online Competition for Veterans 2013 C: Ocean View

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!