List of integers & L.I.S. (SPOILER)

[Tim Peters]

[Bryan Olson, on the problem at
    http://spoj.sphere.pl/problems/SUPPER/
]
> I never intended to submit this program for competition. The
> contest ranks in speed order, and there is no way Python can
> compete with truly-compiled languages on such low-level code.
> I'd bet money that the algorithm I used (coded in C) can run
> with the winners. I also think I'd wager that the Python version
> outright trumps them on code size.

Oh, it's not that bad <wink>.  I took a stab at a Python program for
this, and it passed (3.44 seconds).  It just barely made it onto the
list of "best" solutions, which I also guess is ranked by elapsed
runtime.  The Java program right above it took 2.91 seconds, but ate
more than 27x as much RAM ;-)

I didn't make any effort to speed this, beyond picking a reasonable
algorithm, so maybe someone else can slash the runtime (while I
usually enjoy such silliness, I can't make time for it at present). 
I'll include the code below.

Alas, without access to the input data they use, it's hard to guess
what might be important in their data.  On my home box, chewing over
random 100,000-element permutations took less than a second each
(including the time to generate them); I'm pretty sure they're using
slower HW than mine (3.4 GHz P5).

> My first version bombed for the zero-length sequence. That was a
> mistake, sorry, but it may not be one of their test-cases. I
> wonder how many of the accepted entries would perform properly.

No idea here, and didn't even think about it.

Notes:  the `all` returned by crack() is a list such that all[i] is
list of all (index, value) pairs such that the longest increasing
subsequence ending with `value` is of length i+1; `value` is at index
`index` in the input permutation.  The maximal LISs thus end with the
values in all[-1].  findall() iterates backwards over `all`, to
accumulate all the values that appear in _some_ maximal LIS.  There's
clearly wasted work in findall() (if someone is looking for an
algorithmic point to attack).  Curiously, no use is made of that
values are integers, outside of input and output; any values with a
total ordering would work fine in crack() and findall().

"""
# http://spoj.sphere.pl/problems/SUPPER/

def crack(xs):
    from bisect import bisect_right as find
    smallest = []
    all = []
    n = 0
    for index, x in enumerate(xs):
        i = find(smallest, x)
        if i == n:
            smallest.append(x)
            all.append([(index, x)])
            n += 1
        else:
            all[i].append((index, x))
            if x < smallest[i]:
                smallest[i] = x
    return all

def findall(all):
    constraints = all[-1]
    allints = [pair[1] for pair in constraints]
    for i in xrange(len(all) - 2, -1, -1):
        survivors = []
        for pair in all[i]:
            index, value = pair
            for index_limit, value_limit in constraints:
                if index < index_limit and value < value_limit:
                    survivors.append(pair)
                    allints.append(value)
                    break
        constraints = survivors
    return sorted(allints)

def main():
    import sys
    while 1:
        n = sys.stdin.readline()
        if not n:
            break
        n = int(n)
        perm = map(int, sys.stdin.readline().split())
        assert n == len(perm)
        supers = findall(crack(perm))
        perm = None # just to free memory
        print len(supers)
        print " ".join(map(str, supers))

if __name__ == "__main__":
    main()
"""