481 - What Goes Up

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Ivo Sluganovic
New poster
Posts: 12
Joined: Tue Sep 21, 2004 10:08 pm

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

Post by Ivo Sluganovic » Wed Nov 03, 2004 12:25 pm

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?

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm

Post by Andrew Neitsch » Tue Nov 16, 2004 10:01 pm

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.

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

481 Why WA?

Post by Morning » Mon Jan 31, 2005 4:24 pm

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;
}
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Fri Feb 11, 2005 4:06 pm

try for this input
2
-100000

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

MAP

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning » Fri Feb 11, 2005 4:11 pm

yeah,that's why i got WA.
thank u so much!
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

User avatar
Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

Wrong answer.

Post by Ndiyaa ndako » Sat Oct 22, 2005 4:38 pm

I am using the O(n log k) algorithm but I cannot get it accepted. Could you post some test cases?

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

WA

Post by Moha » Sat Oct 29, 2005 2:20 am

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?

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

481 WHY TLE

Post by sds1100 » Sat Dec 10, 2005 3:07 pm

#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);
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Dec 10, 2005 4:39 pm

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.

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

481 Compile Error Help me..

Post by sds1100 » Thu Dec 15, 2005 4:18 am

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!

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Thu Dec 15, 2005 9:19 am

my compiler says its in boundcheck() function. declare t as LLINT *t, not int *t.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

481 CE...

Post by tmdrbs6584 » Mon Jan 30, 2006 1:29 pm

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;
}

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Jan 30, 2006 2:48 pm

line 34 of your code:

Code: Select all

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

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Tue Jan 31, 2006 4:25 pm

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...:)

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

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

Post by serur » Tue Mar 28, 2006 2:59 pm

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.

Post Reply

Return to “Volume 4 (400-499)”