Page 1 of 6

481 what goes up

Posted: Sun Nov 30, 2003 6:29 pm
by 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 ?

Posted: Sun Nov 30, 2003 10:23 pm
by Farid Ahmadov
Isn't it a LIS algorithm? LIS can be done in O(nlogn) with O~1.

Posted: Mon Dec 01, 2003 12:23 am
by 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).

Posted: Mon Dec 01, 2003 1:53 am
by 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)

Posted: Mon Dec 01, 2003 1:54 am
by 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 ? :)

Posted: Mon Dec 01, 2003 9:14 pm
by 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.

Posted: Mon Dec 01, 2003 9:27 pm
by Caesum
nevermind.... i think i have it...... writing that helped me sort it out in my mind........

Posted: Fri Jan 30, 2004 6:14 pm
by 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-

Posted: Fri Mar 12, 2004 8:43 pm
by 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?

Posted: Fri Mar 12, 2004 9:12 pm
by 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.

Posted: Fri Mar 12, 2004 9:25 pm
by 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.

Posted: Mon Mar 15, 2004 7:48 am
by dwyak
I known the mistakes I made now. Thanks for Adrian's help. :)

481 MLE - out of ideas

Posted: Tue Sep 07, 2004 12:11 am
by 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]

Posted: Tue Sep 07, 2004 11:27 pm
by 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.

Posted: Wed Sep 08, 2004 1:47 am
by 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?
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.