## 481 - What Goes Up

Moderator: Board moderators

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

### 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
Isn't it a LIS algorithm? LIS can be done in O(nlogn) with O~1.
_____________
NO sigNature

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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).

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 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=0, LIS=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)
_____________
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 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=0, LIS=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 ? Last edited by Farid Ahmadov on Mon Dec 01, 2003 9:35 pm, edited 1 time in total.
_____________
NO sigNature

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
nevermind.... i think i have it...... writing that helped me sort it out in my mind........

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

Thanks,

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

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

1
3

which occurs later.

Is it right? Or, do I understand the problem correctly?
Wenyuan Dai, Shanghai Jiaotong University.

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:
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.
Wenyuan Dai, Shanghai Jiaotong University.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:
I known the mistakes I made now. Thanks for Adrian's help. Wenyuan Dai, Shanghai Jiaotong University.

Oog
New poster
Posts: 6
Joined: Sat Dec 20, 2003 5:29 am

### 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;
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
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm
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
New poster
Posts: 6
Joined: Sat Dec 20, 2003 5:29 am
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.