List of integers & L.I.S.

n00m n00m at narod.ru
Thu Sep 8 02:33:23 EDT 2005


Thanks guys!
> Are you sure that this is not a homework problem?
... and let me reveal the secret:
http://spoj.sphere.pl/problems/SUPPER/

Hardly it can be easily reduced to "standard" LIS problem
(i.e. to find just a (any) Longest Increasing Sequence).

> I coded a solution that can compute the ordering numbers for
> random.shuffle(range(1, 1000001)) in 2.5 seconds (typical, Win 2K Pro,
> Pentium 4 2.40GHz 785Meg RAM)
Sounds very impressive! It would be great to see your py solution got
accepted on my link (yes! they accept Python 2.4.1 solutions! and of
course the registration is free and fully anonymous).
So far there is no any accepted Py solution for this problem (see
link "Best Solutions" on the top of page of this problem).
Note: their machines are PIII Xeon 700MHz (no limit. for memory usage).

PS Thanks, Dan! but frankly speaking I'm not much interested just
to get someone's ready-to-use code without understanding how it
works.




More information about the Python-list mailing list