n00m wrote: > Firstly I find ordering numbers when moving from left to the right; > then I find ord. numbers for backward direction AND for DECREASING > subsequences:
Sounds good. > Btw, I did it in Pascal. Honestly, I don't believe it can > be done in Python (of course I mean only the imposed time limit). > http://spoj.sphere.pl/status/SUPPER/ Is there a platform specified? Below is an alleged solution in Python. -- --Bryan #!/user/bin/env python """ Python 2.4 solution to: http://spoj.sphere.pl/problems/SUPPER/ """ 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]) _ = 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
