481 - What Goes Up

[Caesum]

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 ?

[Farid Ahmadov]

Isn't it a LIS algorithm? LIS can be done in O(nlogn) with O~1.

[Adrian Kuegel]

There is a O(n log k) algorithm, where k is the length of LIS. You have to find a structure, where you add the n numbers in the given order. The place where an element is added is determined by binary search. After you added all numbers, you can reconstruct the LIS sequence in O(n).

[Farid Ahmadov]

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[x-1]]<a[n]<a[LIS[x]]
b[n]=LIS[x-1], 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)

[Farid Ahmadov]

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[x-1]]<a[n]<a[LIS[x]]
b[n]=LIS[x-1], 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 ?

[Caesum]

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.

[Caesum]

nevermind.... i think i have it...... writing that helped me sort it out in my mind........

[turuthok]

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 (LIS-1) ... and so on ...

Thanks,

-turuthok-

[dwyak]

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?

[dwyak]

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.

[Adrian Kuegel]

My program that I used to generate the judge output prints:
2
-
1
3
for your input, as this is the sequence that occurs last.
You can send me your program that got WA, I will check it and tell you what differs from my output.

[dwyak]

I known the mistakes I made now. Thanks for Adrian's help.

[Oog]

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]

[Andrew Neitsch]

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.

[Oog]

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?

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.