Bravo, Bryan!
Looks very neat! (pity I can't give it a try in my Py 2.3.4
because of reversed() and sorted() functions)
And I've submitted it but got ... TLEs:
http://spoj.sphere.pl/status/SUPPER/
Funnily, the exec.time of the best C solution is only 0.06s!
PS
In my 1st submission I overlooked that your code handles only
1 testcase (there are 10 of them); hence its 0.13s exec. time.
PPS
This is the code's text I submitted:
#!/user/bin/env python
from sys import stdin
def one_way(seq):
n = len(seq)
dominators = [n + 1] * (n * 1)
# dominators[j] is lowest final value of any increasing sequence
of
# length j seen so far, as we left-right scan seq.
score = [None] * n
end = 0
for (i, x) in enumerate(seq):
# Binary search for x's place in dominators
low, high = 0, end
while high - low > 10:
mid = (low + high) >> 1
if dominators[mid] < x:
low = mid + 1
else:
high = mid + 1
while dominators[low] < x:
low += 1
dominators[low] = x
score[i] = low
end = max(end, low + 1)
return score
def supernumbers(seq):
forscore = one_way(seq)
opposite = [len(seq) - x for x in reversed(seq)]
backscore = reversed(one_way(opposite))
score = map(sum, zip(forscore, backscore))
winner = max(score)
return sorted([seq[i] for i in range(len(seq)) if score[i] ==
winner])
for tc in range(10):
_ = stdin.readline()
sequence = [int(ch) for ch in stdin.readline().split()]
supers = supernumbers(sequence)
print len(supers)
for i in supers:
print i,
--
http://mail.python.org/mailman/listinfo/python-list
