Page 2 of 6

How do I solve 481 (What goes up)? PLZ HLP!!!

Posted: Wed Nov 03, 2004 12:25 pm
by Ivo Sluganovic
How do I solve the 481 (What goes up) problem more efficently?
I implemented the standard LIS algorithm, but it seems to be too slow.
I've tried implementing it using linked lists and some other things to improve the time, but stil keep on getting TLE.

Can anybody give me an idea to fasten my program up?

How did someone get 0.00.086 on this?

Posted: Tue Nov 16, 2004 10:01 pm
by Andrew Neitsch
There's an O(n log n) algorithm for this.

Super-fast times are usually I/O optimization or tables or something like that. Don't worry about it.

481 Why WA?

Posted: Mon Jan 31, 2005 4:24 pm
by Morning
i used the DP(LIS) which is O(n^2),that algorithm may cause TLE,but why i got WA?

is my algorithm okay?

Code: Select all

#include <iostream>
using namespace std;

int height[10000];
int len[10000];
int pre[10000];
int limit;
int i,j;
int maxlen;
int tail;

void output(int i)
{
	if(pre[i] == -1) 
	{
		cout << height[i] << endl;
	}
	else
	{
		output(pre[i]);
		cout << height[i] << endl;
	}
}

int main()
{
	limit = 0;
	maxlen = -1;
	while(cin >> height[limit])
	{
		len[limit] = 1;
		pre[limit++] = -1;
	}
	limit--;
	for(i = 0;i < limit;i++)
	{
		for(j = i + 1;j <= limit;j++)
		{
			if(height[j] > height[i])
			{
				if(len[i] + 1 >= len[j])
				{
					len[j] = len[i] + 1;
					pre[j] = i;
					if(len[j] >= maxlen)
					{
						maxlen = len[j];
						tail = j;
					}
				}
			}
		}
	}
	
	cout << maxlen << endl << '-' << endl;

	output(tail);
	
	return 0;
}

Posted: Fri Feb 11, 2005 4:06 pm
by mohiul alam prince
try for this input
2
-100000

after increase ur array size
int height[200005];
int len[200005];
int pre[200005];

MAP

Posted: Fri Feb 11, 2005 4:11 pm
by Morning
yeah,that's why i got WA.
thank u so much!

Wrong answer.

Posted: Sat Oct 22, 2005 4:38 pm
by Ndiyaa ndako
I am using the O(n log k) algorithm but I cannot get it accepted. Could you post some test cases?

WA

Posted: Sat Oct 29, 2005 2:20 am
by Moha
I am getting WA, in this problem, can anybody post some tested testcases.
I use long long number but, still WA!
my code, answer adrian Testcase correctly, and i don't know where is my bug.
can anybody help me?

481 WHY TLE

Posted: Sat Dec 10, 2005 3:07 pm
by sds1100
#include <fstream.h>
int k,a[1000000],n,cnt,max,d[1000000],p[1000000];
void prs(int aa){
if(p[aa]==-1){
cout << a[aa] << endl;
return;
}
prs(p[aa]);
cout << a[aa] << endl;
}
void main()
{
int i,j;
while(cin >> k){
p[cnt]=-1;
a[cnt++]=k;
}
n=cnt;
d[0]=1;
int max=-999;
for(i=0;i<n;i++){
cnt=0;
for(j=0;j<i;j++){
if(a>a[j]){
if(d<=d[j]){
d=d[j]+1;
p=j;
}
}
}

if(d>max)max=d;
}
for(i=0;i<n;i++){
if(max==d)break;
}
cout << d << endl << "-" << endl;
prs(i);
}

Posted: Sat Dec 10, 2005 4:39 pm
by mf
TLE -- because your program isn't fast enough. Generate an input with 100000 random numbers, and you'll see why.

You have to find a better algorithm, or use some clever data structure to speed up yours.

481 Compile Error Help me..

Posted: Thu Dec 15, 2005 4:18 am
by sds1100

Code: Select all

#include <fstream.h>
#include <memory.h>
#define MAX 200005
typedef long long int LLINT
LLINT a[MAX],x[MAX],t,n,now,p[MAX],*aa[MAX],aacnt[MAX],go[MAX],gocnt,aanow,anum[MAX];

void BoundCheck(int i)
{
	int *t;
	if (anum[i] == 0) {
		anum[i] = 20;
		aa[i] = new LLINT[20];
	}
	else if (anum[i] <= aacnt[i]) {		
		t = new LLINT[anum[i]*2];
		memcpy(t, aa[i], anum[i]*sizeof(int));
		delete [] aa[i];
		aa[i] = t;
		anum[i] <<= 1;
	}
}


void main()
{
	int i,j,sw=0;
	while(cin >> t){
		a[n]=-2147483648;
		x[n++]=t;
	}
	for(i=0;i<n;i++){
		sw=0;
		for(j=0;j<=now;j++){
			if(x[i]<=a[j]){
				a[j]=x[i];
				sw=1;				
				aacnt[j]++;				
				BoundCheck(j);
				aa[j][aacnt[j]]=x[i];
				break;
			}
		}
		if(sw==0){
			anum[now] = 8;
			aa[now] = new LLINT[8];
			if(aacnt[now]==0){
				aa[now][0]=x[i];
			}
			a[now++]=x[i];
		}
	}
	for(i=0;i<now;i++){
		aacnt[i]++;
	}
	cout << now << endl << "-" << endl;
	go[gocnt++]=aa[now-1][0];
	aanow=aa[now-1][0];
	for(i=now-2;i>=0;i--){
		for(j=0;j<aacnt[i];j++){
			if(aa[i][j]<aanow){
				go[gocnt++]=aa[i][j];
				aanow=aa[i][j];
				break;
			}
		}
	}
	for(i=now-1;i>=0;i--){
		delete [] aa[i];
		cout << go[i] << endl;
	}
}
help me!

Posted: Thu Dec 15, 2005 9:19 am
by ayon
my compiler says its in boundcheck() function. declare t as LLINT *t, not int *t.

481 CE...

Posted: Mon Jan 30, 2006 1:29 pm
by tmdrbs6584
I got CE..
but why?
#include<iostream.h>
int n,cnt;
int a[100000],d[100000],pos[100000],path[100000];
int main(){
int i,j;
int q=0;
while(cin >> a[q]){
if(a[q]==-1) break;
q++;
}
int max=0,idx;
for(i=0;i<q;i++)
pos=-1;
for(i=0;i<q;i++){
d=1;
for(j=0;j<i;j++){
if(a>a[j] && d<d[j]+1){
d=d[j]+1;
pos=j;
}
}
if(max<d){
max=d;
idx=i;

}
}
path[cnt++]=idx;
while(pos[idx]!=-1){
path[cnt++]=pos[idx];
idx=pos[idx];
}
cout << q << endl << "-" << endl;
for(i=cnt-1;i>=0;i---)
cout << a[path] << endl;
n=cnt=0;
for(i=0;i<300;i++)
a=d[i]=pos[i]=path[i]=0;
return 0;
}

Posted: Mon Jan 30, 2006 2:48 pm
by sohel
line 34 of your code:

Code: Select all

for(i=cnt-1;i>=0;i---) 
i---

Posted: Tue Jan 31, 2006 4:25 pm
by A1
I think you are using O(n^2) algorithm of LIS to solve this, but in this problem n could be as big as 100000
so n^2 solution will get TLE.
Try to use n log(n) solution...:)

and another one asking for help - 481"What Goes Up"

Posted: Tue Mar 28, 2006 2:59 pm
by serur
Hello everyone!
I read in Halim's website the explanation of O(nlog(k)) algo for LIS,
it seems I have grasped the main idea(for I got AC 231-"Testing the Catcher"), but how to restore the LIS itself and even how to maintain the predecessor array- it is still a mystery for me...
Would you be so kind to explain what is the the crux?
Is this multiple input problem?
If you want to cast a glance on my code (which invariably gives WA, though behaves well for my own I/O :)), I'll send it immediately.

Algoritmist website also very good for this problem, I thank them too
Thank you.