List of integers & L.I.S.

[n00m]

Given a list of N arbitrarily permutated integers from set {1..N}.
Need to find the ordering numbers of each integer in the LONGEST
increasing sequence to which this number belongs. Sample:

List:
[4, 5, 6, 1, 2, 7, 3]

Corresponding ordering numbers:
[1, 2, 3, 1, 2, 4, 3]

Details:
e.g. number 7 belongs to increasing sequence 1, 2, 7;
but this sequence is not the LONGEST sequence for "7".
The longest sequence for the 7 is 4, 5, 6, 7.
So, the 7's ordering number in this sequence is 4.

The salt of the thing is to do this with an O(n*log(n))
algorithm!
The straightforward O(n^2) algorithm is toooo slooow.

Any ideas?

[n00m]

PS: I've still not read 2 new posts.

[n00m]

> 4 5 1 2 3 6 7 8 << the list itself

1 2 1 2 3 4 5 6 << ordering numbers for forward direction
2 1 6 5 4 3 2 1 << ordering numbers for backward direction
===
3 3 7 7 7 7 7 7 << sums of the pairs of ord. numbers

Oops! Sorry for miscounting in backward direction.
Should be (anyway the answer stays the same):

4 5 1 2 3 6 7 8 << the list itself
1 2 1 2 3 4 5 6 << ordering numbers for forward direction
5 4 6 5 4 3 2 1 << ordering numbers for backward direction
===
6 6 7 7 7 7 7 7 << sums of the pairs of ord. numbers

[Bryan Olson]

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(se q):
forscore = one_way(seq)
opposite = [len(seq) - x for x in reversed(seq)]
backscore = reversed(one_wa y(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(se quence)
print len(supers)
for i in supers:
print i,

[n00m]

Bravo, Bryan!
It's incredibly fast! But your code got WA (wrong answer).
See my latest submission: http://spoj.sphere.pl/status/SUPPER/
Maybe you slipped a kind of typo in it? Silly boundary cases?

[n00m]

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(se q):
forscore = one_way(seq)
opposite = [len(seq) - x for x in reversed(seq)]
backscore = reversed(one_wa y(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(se quence)
print len(supers)
for i in supers:
print i,

[Bryan Olson]

n00m wrote:

Bravo, Bryan!
It's incredibly fast!
Not compared to a good implementation for a compiled, low-level
language.
But your code got WA (wrong answer).
See my latest submission: http://spoj.sphere.pl/status/SUPPER/
Maybe you slipped a kind of typo in it? Silly boundary cases?

Hmmm ... wrong answer ... what could ... ah! Here's a problem: I
bomb on the empty sequence. Correction below.

I'm not a perfect programmer, but I like to think I'm a good
programmer. Good programmers own their bugs.

If there's another problem, I need more to go on. From what you
write, I cannot tell where it fails, nor even what submission is
yours and your latest.
--
--Bryan
#!/user/bin/env python

"""
Python solution to:

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

By Bryan Olson
"""

from sys import stdin
def one_way(seq):
n = len(seq)
dominators = [n + 1] * (n * 1)
score = [None] * n
end = 0
for (i, x) in enumerate(seq):
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(se q):
forscore = one_way(seq)
opposite = [len(seq) - x for x in reversed(seq)]
backscore = reversed(one_wa y(opposite))
score = map(sum, zip(forscore, backscore))
winner = max(score + [0])
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(se quence)
print len(supers)
for i in supers:
print i,

[n00m]

Oops Bryan... I've removed my reply that you refer to...
See my previous - CORRECT - reply. The code just times
out... In some sense it doesn't matter right or wrong is
its output.
Btw, what is the complexity of your algorithm?
Currently I'm at work and it's not easy for me to concentrate
on our subject.

[n00m]

> nor even what submission is yours and your latest.
Oops.. my UserName there is ZZZ.
Submissions in the html table are ordered by date DESC.

[Bryan Olson]

n00m wrote:

Oops Bryan... I've removed my reply that you refer to...
See my previous - CORRECT - reply. The code just times
out... In some sense it doesn't matter right or wrong is
its output.
If my code times out, then they are using an archaic platform.
With respect to my code, you noted:

Bravo, Bryan! It's incredibly fast!

I myself did not claim 'incredibly fast'; but the code should
beat the 9-second mark on any currently-viable platform, even if
the machine were bought on special at Wal-Mart.

For this kind of low-level challenge, Python cannot compete with
the speed of C/C++, nor Ada, Pascal, ML, PL/1, nor even good
Java implementations . Nevertheless, even in the rare cases in
which efficiency of such computations is an issue, the Python
solution is usually worthy contender, and often the superior
solution.

Human time is more valuable than machine time. Python emphasizes
human-friendly code.
Alas, I would be (and, since I did cite it, was) wrong on that.
My code failed for the empty sequence. Wheter or not that was
one of the test cases, and whether or not it was a consideration
as the problem was defined, it was a bug. As I wrote:

Good programmers own their bugs.

Btw, what is the complexity of your algorithm?

For a list of n items, time Theta(n ln(n)), space Theta(n).
--
--Bryan

[n00m]

Oh!
Seems you misunderstand me!
See how the last block in your code should look:

for tc in range(10):
_ = stdin.readline( )
sequence = [int(ch) for ch in stdin.readline( ).split()]
supers = supernumbers(se quence)
print len(supers)
for i in supers:
print i,
When I submitted it (for the 1st time) without

for tc in range(10):

the e-judge counted the output of your code as
Wrong Answer; just because the e-judge got an answer
for only the very 1st testcase (I think in it was not
too large input data).