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?

 

[Dan Sommers]

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?

I wrote something like that for the Discrete Mathematics I took last
spring (we had to produce the longest sequence, though, rather than the
indexes into the original list, our list was not necessarily a
permutation of 1..N, and I "cheated" on the longest descending sequnce
by changing one of the comparison operators and re-running the program).

If push comes to shove, I suppose I could post the whole program (all
100 lines of it), but here's the comment near the top:

# consider that there are 2 ** n subsequences (corresponding to the 2 **
# n permutations of the original sequence); the trick is to accumulate
# them all at once while skipping the ones that are not strictly
# ascending and also pruning sequences that obviously can't "win"

It's not much to go on, but that bit after the ";" is the algorithm I
use. I can't tell you how fast it runs in big-O notation, but my old
500 MHz PowerMac G4 digested lists of tens or hundreds of thousands of
random integers while I waited.

Regards,
Dan

 

[manuelg]

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)

Are you sure that this is not a homework problem?

 

[n00m]

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.

 

[manuelg]

... and let me reveal the secret:

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

your question is different than the question on this website.

also, what do you consider to be the correct output for this
permutation? (according to your original question)

[4, 5, 1, 2, 3, 6, 7, 8]

Manuel

 

[sp1d3rx]

So, this has no real world use, aside from posting it on a website.
Thanks for wasting our time. You are making up an arbitrary problem and
asking for a solution, simply because you want to look at the
solutions, not because your problem needs to be solved. Clearly, this
is a waste of time.

 

[manuelg]

Working on this allowed me to avoid some _real_ (boring) work at my
job.

So clearly it served a very useful purpose!

Manuel

 

[Tim Peters]

[[email protected]]

So, this has no real world use, aside from posting it on a website.
Thanks for wasting our time. You are making up an arbitrary problem and
asking for a solution, simply because you want to look at the
solutions, not because your problem needs to be solved. Clearly, this
is a waste of time.

If investigating algorithms irritates you, ignore it. The people
writing papers on this topic don't feel it's a waste of time. For
example,

http://citeseer.ist.psu.edu/bespamyatnikh00enumerating.html
"Enumerating Longest Increasing Subsequences and Patience Sorting (2000)"
Sergei Bespamyatnikh, Michael Segal

That's easy to follow, although their use of a Van Emde-Boas set as a
given hides the most challenging part (the "efficient data structure"
part).

 

[manuelg]

That's easy to follow, although their use of a Van Emde-Boas set as a

given hides the most challenging part (the "efficient data structure"
part).

The "efficient data structure" is the easy part.

Obviously, it is a dict of lists.

....or is it a list of dicts?...

....or is it a tuple of generators?...

Anyway, "being aware of the literature", "thinking", "being smart", and
"being Tim Peters" are all forms of cheating.

I prefer not to cheat.

nOOm, I still need an answer...

also, what do you consider to be the correct output for this
permutation? (according to your original question)

[4, 5, 1, 2, 3, 6, 7, 8]

Manuel

 

[n00m]

So, this has no real world use, aside from posting it on a website.

I don't think you're quite right.
We never know where we gain and where we lose.

So clearly it served a very useful purpose!

Thanks, Manuel!

your question is different than the question on this website.

Not exactly so (maybe I'm wrong here). How I did it (but got TLE
- Time Limit Exceeded (which is 9 seconds)).

Firstly I find ordering numbers when moving from left to the right;
then I find ord. numbers for backward direction AND for DECREASING
subsequences:

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

Now those numbers with sum_of_ord.pair = max + 1 = 6 + 1
are the answer.
So the answer for your sample is: 1 2 3 6 7 8

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/

 

[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]

> 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 = 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 for i in range(len(seq)) if score == winner])


_ = stdin.readline()
sequence = [int(ch) for ch in stdin.readline().split()]
supers = supernumbers(sequence)
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 = 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 for i in range(len(seq)) if score ==
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,

 

[Bryan Olson]

> 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 = 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 + [0])
return sorted([seq for i in range(len(seq)) if score == winner])


_ = stdin.readline()
sequence = [int(ch) for ch in stdin.readline().split()]
supers = supernumbers(sequence)
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]

> 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).

 

[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(sequence)
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).