481  What Goes Up
Moderator: Board moderators
481 what goes up
My current algorithm for this is O(n^2) worse case and O(n) best case but it fails with TLE on this problem  each time it adds a new element it looks back through an array to find where it can be added to a sequence to make a longer one. It appears that the array size is somewhere between 100000 and 200000 elements and it just isn't fast enough with this number of elements. I can see that potentially you could use an LCS type algorithm if you could order a second set of elements and find the LCS of the two, but the number of elements is too big. So am I missing some other better algorithm for this problem ?

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan
My algo is below:
a  array of elements
LIS  array[20000] of indexes in a
b  b[x] contains the index of such elements that index(x)=index(b[x])1 in LIS, a[x]>a[b[x]]
(0) z=1, b[1]=0, LIS[1]=1, (1)
(1) while not eof { n=n+1, readln(a[n]) }, (2)
(2) if a[n]>LIS[last] then { b[n]=LIS[last], last=last+1, LIS[last]=n (4) } else (3)
(3) binary search in LIS for such x that a[LIS[x1]]<a[n]<a[LIS[x]]
b[n]=LIS[x1], LIS[x]=n, (4)
(4) x=LIS[last], for i = 1 ... last { answer=a[x], z=b[x] }, (5)
(5) for i = 1 ... last writeln(answer)
a  array of elements
LIS  array[20000] of indexes in a
b  b[x] contains the index of such elements that index(x)=index(b[x])1 in LIS, a[x]>a[b[x]]
(0) z=1, b[1]=0, LIS[1]=1, (1)
(1) while not eof { n=n+1, readln(a[n]) }, (2)
(2) if a[n]>LIS[last] then { b[n]=LIS[last], last=last+1, LIS[last]=n (4) } else (3)
(3) binary search in LIS for such x that a[LIS[x1]]<a[n]<a[LIS[x]]
b[n]=LIS[x1], LIS[x]=n, (4)
(4) x=LIS[last], for i = 1 ... last { answer=a[x], z=b[x] }, (5)
(5) for i = 1 ... last writeln(answer)
_____________
NO sigNature
NO sigNature

 Experienced poster
 Posts: 131
 Joined: Thu Apr 17, 2003 8:39 am
 Location: Baku, Azerbaijan
My algo is below:
a  array of elements
LIS  array[20000] of indexes in a
b  b[x] contains the index of such elements that index(x)=index(b[x])1 in LIS, a[x]>a[b[x]]
(0) z=1, b[1]=0, LIS[1]=1, (1)
(1) while not eof { n=n+1, readln(a[n]) }, (2)
(2) if a[n]>LIS[last] then { b[n]=LIS[last], last=last+1, LIS[last]=n (4) } else (3)
(3) binary search in LIS for such x that a[LIS[x1]]<a[n]<a[LIS[x]]
b[n]=LIS[x1], LIS[x]=n, (4)
(4) x=LIS[last], for i = 1 ... last { answer=a[x], x=b[x] }, (5)
(5) for i = 1 ... last writeln(answer)
I got AC with this algo. Maybe there exist a better algo ?
a  array of elements
LIS  array[20000] of indexes in a
b  b[x] contains the index of such elements that index(x)=index(b[x])1 in LIS, a[x]>a[b[x]]
(0) z=1, b[1]=0, LIS[1]=1, (1)
(1) while not eof { n=n+1, readln(a[n]) }, (2)
(2) if a[n]>LIS[last] then { b[n]=LIS[last], last=last+1, LIS[last]=n (4) } else (3)
(3) binary search in LIS for such x that a[LIS[x1]]<a[n]<a[LIS[x]]
b[n]=LIS[x1], LIS[x]=n, (4)
(4) x=LIS[last], for i = 1 ... last { answer=a[x], x=b[x] }, (5)
(5) for i = 1 ... last writeln(answer)
I got AC with this algo. Maybe there exist a better algo ?
Last edited by Farid Ahmadov on Mon Dec 01, 2003 9:35 pm, edited 1 time in total.
_____________
NO sigNature
NO sigNature
sounds interesting but...... your pseudo code loses me, i tried implementing this but can't get it to work.......
(4) x=LIS[last], for i = 1 ... last { answer=a[x], z=b[x] }, (5)
what is z doing here ? do you mean x ?
(2) if a[n]>LIS[last]
shouldnt this be a[n]>a[LIS[last]] ?
I still don't understand how this is supposed to work....... you start with LIS[last] at the end, but if you had a series like:
1
2
3
10
4
5
6
then 'last' has not been changed since 10 was added to the sequence according to your pseudocode but 1 2 3 10 is clearly not the longest sequence.
(4) x=LIS[last], for i = 1 ... last { answer=a[x], z=b[x] }, (5)
what is z doing here ? do you mean x ?
(2) if a[n]>LIS[last]
shouldnt this be a[n]>a[LIS[last]] ?
I still don't understand how this is supposed to work....... you start with LIS[last] at the end, but if you had a series like:
1
2
3
10
4
5
6
then 'last' has not been changed since 10 was added to the sequence according to your pseudocode but 1 2 3 10 is clearly not the longest sequence.

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
Can someone please confirm if my statement below is correct:
If we have 2 LIS sequence with different starting indices, then we should pick the one with greater starting index. And then starting from there, we look for the next greatest index which can give us (LIS1) ... and so on ...
Thanks,
turuthok
If we have 2 LIS sequence with different starting indices, then we should pick the one with greater starting index. And then starting from there, we look for the next greatest index which can give us (LIS1) ... and so on ...
Thanks,
turuthok
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
Hi, Farid Ahmadov,
I don't think you algo could find a longest sequence that occurs last in the input file. I believe that your algo finds the sequence ends last.
For example, for this case
2
1
3
You algo may find the answer
2
3
But, there is another answer
1
3
which occurs later.
Is it right? Or, do I understand the problem correctly?
I don't think you algo could find a longest sequence that occurs last in the input file. I believe that your algo finds the sequence ends last.
For example, for this case
2
1
3
You algo may find the answer
2
3
But, there is another answer
1
3
which occurs later.
Is it right? Or, do I understand the problem correctly?
Wenyuan Dai, Shanghai Jiaotong University.
I'm still confused about the problem's meaning.
The problem says, if there are multiple longest sequences, the one that occurs last should be printed. But in this case,
2
1
3
which is the longest sequence that occurs last?
my AC program outputs
2
3
I can't understand why "2 3" is the one that occurs last.
In my opinion, turuthok's understanding should be correct. I wrote a program based on his understanding, but got WA.
The problem says, if there are multiple longest sequences, the one that occurs last should be printed. But in this case,
2
1
3
which is the longest sequence that occurs last?
my AC program outputs
2
3
I can't understand why "2 3" is the one that occurs last.
In my opinion, turuthok's understanding should be correct. I wrote a program based on his understanding, but got WA.
Wenyuan Dai, Shanghai Jiaotong University.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
481 MLE  out of ideas
im trying to solve 481 and i believe my program works except i keep getting memory limit exceeded and dont see why. ive tried cutting the memory down changing vectors to arrays because that is the only thing i could thing of. i also changed the binary search to use a stack instead of recursive calls. any ideas?
[cpp]
int nums[100000];
int size = 0;
int LIS_BS( pair<int, vector<int> > *L, int Lsize, int s, int f, int t )
{
int m;
stack<pair<int, int> > theStack;
pair<int, int> cur;
theStack.push( pair<int, int>( s, f ) );
while( !theStack.empty() )
{
cur = theStack.top();
theStack.pop();
s = cur.first;
f = cur.second;
if( s > f )
{
while( s >= Lsize  L[s].first >= t )
s;
return s;
}
m = (s + f) / 2;
if( L[m].first > t )
theStack.push( pair<int, int>( s, m  1 ) );
//return LIS_BS( L, s, m  1, t );
else if( L[m].first < t )
theStack.push( pair<int, int>( m + 1, f ) );
//return LIS_BS( L, m + 1, f, t );
else
{
while( L[m].first == t )
m;
return m;
}
}
}
vector<int> LIS( /*vector<int> &nums*/ )
{
int i, a, Lsize = 0;
//vector< pair<int, vector<int> > > L;
pair<int, vector<int> > *L;
vector<int> ret;
L = new pair<int, vector<int> >[size];
//L.reserve( nums.size() );
//L.push_back( pair<int, vector<int> >( INT_MIN, vector<int>() ) );
L[Lsize++] = pair<int, vector<int> >( INT_MIN, vector<int>() );
for( i = 0; i < size; ++i )
{
a = LIS_BS( L, Lsize, 0, Lsize  1, nums );
//a = 0;
if( a + 1 >= Lsize )
L[Lsize++] = pair<int, vector<int> >( nums, vector<int>() );
else
L[a + 1].first = nums;
L[a+1].second = L[a].second;
L[a+1].second.push_back( L[a + 1].first );
}
return L[Lsize  1].second;
}
int main()
{
int i, n;
vector<int> ret;
while( cin >> n )
nums[size++] = n;
ret = LIS();
cout << ret.size() << endl;
cout << "" << endl;
for( i = 0; i < ret.size(); ++i )
cout << ret << endl;
return 0;
}
[/cpp]
[cpp]
int nums[100000];
int size = 0;
int LIS_BS( pair<int, vector<int> > *L, int Lsize, int s, int f, int t )
{
int m;
stack<pair<int, int> > theStack;
pair<int, int> cur;
theStack.push( pair<int, int>( s, f ) );
while( !theStack.empty() )
{
cur = theStack.top();
theStack.pop();
s = cur.first;
f = cur.second;
if( s > f )
{
while( s >= Lsize  L[s].first >= t )
s;
return s;
}
m = (s + f) / 2;
if( L[m].first > t )
theStack.push( pair<int, int>( s, m  1 ) );
//return LIS_BS( L, s, m  1, t );
else if( L[m].first < t )
theStack.push( pair<int, int>( m + 1, f ) );
//return LIS_BS( L, m + 1, f, t );
else
{
while( L[m].first == t )
m;
return m;
}
}
}
vector<int> LIS( /*vector<int> &nums*/ )
{
int i, a, Lsize = 0;
//vector< pair<int, vector<int> > > L;
pair<int, vector<int> > *L;
vector<int> ret;
L = new pair<int, vector<int> >[size];
//L.reserve( nums.size() );
//L.push_back( pair<int, vector<int> >( INT_MIN, vector<int>() ) );
L[Lsize++] = pair<int, vector<int> >( INT_MIN, vector<int>() );
for( i = 0; i < size; ++i )
{
a = LIS_BS( L, Lsize, 0, Lsize  1, nums );
//a = 0;
if( a + 1 >= Lsize )
L[Lsize++] = pair<int, vector<int> >( nums, vector<int>() );
else
L[a + 1].first = nums;
L[a+1].second = L[a].second;
L[a+1].second.push_back( L[a + 1].first );
}
return L[Lsize  1].second;
}
int main()
{
int i, n;
vector<int> ret;
while( cin >> n )
nums[size++] = n;
ret = LIS();
cout << ret.size() << endl;
cout << "" << endl;
for( i = 0; i < ret.size(); ++i )
cout << ret << endl;
return 0;
}
[/cpp]

 New poster
 Posts: 43
 Joined: Fri Jun 25, 2004 9:37 pm
I am using the O( n log n) DP algorithm but I'm not sure about the space usage. The problem must be how I'm storing the intermediate LIS. I'm using pair<int, vector<int> > *L; The vector<int> must be the problem but I don't know how else to do it. I could change it to an array but I don't think that would fix the problem. Is there a better way to reconstruct the LIS then storing all the intermediate ones?
Andrew Neitsch wrote:I have not read your code or post, but there is an O(n log n) dynamic programming solution for this problem, which uses linear space.