NOI 2013 Q1

[smgfour]

The question for this problem is below:

A scientist wants to study how the rising sea level changes the landscape, in particular, how it changes the number of islands. He first investigates one-dimensional worlds. A one-dimensional world is represented by a sequence of non-negative integers {h0, h1, . . . , hn−1}, where each integer hi is the altitude at the location i. You are to code the function find_max_islands which takes in a list of n integers (5 <= n <= 10,000 representing the sequence {h0, h1, . . . , hn−1}. All numbers in the sequence are non-negative and smaller than 230. The function should then return an integer, which is the maximum number of islands. Your code should run within 1.0 seconds. You should not import any packages or modules.

And here is my code:

def find_max_islands(lst):
    maxislands = 1
    for sealevel in lst:
        flag = True # flag means canAdd
        numislands = 0
        for j in lst:
            if j <= sealevel:
                flag = True # can Add
            if flag and j > sealevel:
                flag = False # cannot Add
                numislands += 1 
        maxislands = max(maxislands,numislands) # find max num of islands after each iteration

    if lst==[] or sum(lst)==0:
        return 0
    return maxislands

The code covers all the cases correctly but takes too long to run. I suspect the possibility of it to be because the code is of function O(n^2). I want to know if it is possible to shorten the code to a function O(n log n) or anything else shorter.

[jefsummers]

I don't think you are posting all of your code. Please post all as I cannot test what you have posted.

In any case, n*n is usually faster than n^2

Also, correct me where I am wrong. The list is altitudes of various points on the "terrain". Given a particular "sealevel", the number of islands would be the number of transitions from below sealevel to above. Should not need a double loop to solve that.

[smgfour]

I believe this is the full code. You just need to use print() to run the code.

Anyways, thanks for the help.

[deanhystad]

I must not understand the problem, but can't this be solved with two passes? First pass find the lowest sea level. Second pass count how many entries are greater than the sea level? I don't see how this would be useful for anything as it does not allow counting islands for different sea levels. It would make more sense for sealevel to be an input.

[TomToad]

It looks like you are trying to go over all possible sea levels, figuring out which sea level creates the highest number of islands, then returning the number of islands at the maximum. Am I right?
In your code, you get the sea level by iterating over the list, then iterating over the list again checking each point against the sea level. If the list is at the maximum length of 10,000, then you are making 100,000,000 checks. Since the values can't be over 230, you are at best, creating 9,770 extra iterations, or 97,700,000 extra checks.
You might want to check if the list length is >= 230 and if it is, just go over all possible sea levels 0-230 instead. That would potentially get rid of over 97% of the checks.

[jefsummers]

lst is not defined (has no values) in the posted code. Where do you get the values in that list?

[deanhystad]

The function, as written, finds the number of islands taller than the shortest island in the list. It also does this in a very inefficient way, but that doesn't really matter since the function does not do what it is supposed to do.

The function needs inputs for the list of elevations AND the sea level. This makes the function a useful tool.

def count_islands(elevations, sealevel):
    islands = 0
    for elevation in elevations:
        if elevation >= sealevel:
            islands += 1
    return islands

Now you can answer questions like:
"How many islands are lost if the sea level rises 10'" (or whatever unit)
print(len(elevations) - count_islands(elevations, 10))

Or you could make a chart of islands vs sea level. This creates a list of (sea level, island count) pairs:
points = [(sl, count_islands(sl) for sl in range(230)]

[jefsummers]

But a big island may be above sealevel for multiple measurements. Therefore to get a count you would need to count the transitions from under sealevel to sealevel or above.

[deanhystad]

But a big island may be above sealevel for multiple measurements. Therefore to get a count you would need to count the transitions from under sealevel to sealevel or above.

To get a count of what? I don't see that I really care how high above sea level an island is. Above sea level it is an island. Below sea level it is a reef. My plot example or submerged islands example assumes a comparison to whatever the "base" sea level is for the elevations. If you want to know the change between two non-zero sea levels, you call the function twice and subtract.

[jefsummers]

OK, say sealevel is 5, and your array is [4,6,3,3,6,7,7,4]. If you just compare the terrain to sealevel you get 4 islands. But if you look at the transitions there are only 2. The second island is bigger. Height does not matter as much as width.

Two islands