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

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: SOME TEST CASES, PLEASE

Post by helloneo » Sun Dec 03, 2006 4:54 pm

nymo wrote:Hi, I 've used an INT array of size 50000 and getting WA. Can someone provide some IOs? [I 've tried IOs posted on other threads]... THANKS. and THERE IS ONLY ONE TEST CASE, RIGHT?
My array size is 100000.. try to increase yours..

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Sun Dec 03, 2006 5:01 pm

I 've tried using bigger array size as you suggested, but still WA. I 've used 32 bit int. Thanks. Some more help will be greatly appreciated... :)
regards,
nymo

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Sun Dec 03, 2006 7:07 pm

Spoiler:
http://www.algorithmist.com/index.php/L ... quence.cpp

So dont cut & paste. ;)
Try to learn something from it.

Hope it helps.

bye
Rabbi

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Sun Dec 03, 2006 7:14 pm

:D I knew that url :D , I 've coded myself from the scratch and trying to figure out my fault... :-? Thanks but some test cases would be really handy. thanks again.
regards,
nymo

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Sun Dec 03, 2006 7:26 pm

Randomly generate some INPUTs then store OUTPUTs into a file then compare. ok. Its best.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Acc now :)

Post by nymo » Sun Dec 03, 2006 9:14 pm

Acc now, fixed a small bug, i wasn't updating parent array in a proper way :oops: Thanks.
regards,
nymo

joebin
New poster
Posts: 12
Joined: Fri Dec 29, 2006 7:18 am
Location: Taiwan
Contact:

Post by joebin » Tue Aug 14, 2007 11:28 am

mf wrote: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.
could you give me some idea about 481 ? THX!!
following is my code . i have the same problem .

Code: Select all

#include<iostream> 
using namespace std; 
int d[100000],t[100000],l[100000];//l link-d data-t time 
void out(int i){ 
  if(l[i]!=i) 
    out(l[i]); 
  cout <<d[i]<<endl; 
} 
int main( int argc, char * argv[] ) 
{ 
  int i=0,j,a=0,b=0; 
  while(cin >>d[i]){ 
    t[i]=1;l[i]=i; 
    if(d[i]>d[b]){ 
      l[i]=b; 
      t[i]=(a++); 
      b=i; 
    } 
    else{ 
      for(j=i-1;j>=0;j--) 
        if(d[j]<d[i]&&t[j]+1>t[i]){ 
          t[i]=t[j]+1; 
          l[i]=j; 
        } 
      if(t[i]>=a){ 
        a=t[i]; 
        b=i; 
      } 
    } 
    i++; 
  } 
  cout <<a<<endl<<'-'<<endl; 
  out(b); 
  return 0; 
} 

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Aug 14, 2007 11:57 am

Your complexity is O(n^2). There is an O(n*log(n)) algorithm. Try the links below:

http://en.wikipedia.org/wiki/Longest_in ... ce_problem
http://www.algorithmist.com/index.php/L ... ubsequence

Hope these help.
Ami ekhono shopno dekhi...
HomePage

joebin
New poster
Posts: 12
Joined: Fri Dec 29, 2006 7:18 am
Location: Taiwan
Contact:

Post by joebin » Thu Aug 16, 2007 10:05 am

thx!! Jan ! i got AC .
that idea is too great .
it saves helf of the run time .
:D

shashank.neo
New poster
Posts: 1
Joined: Fri Oct 03, 2008 11:22 pm

481 What goes up --- help needed!

Post by shashank.neo » Thu Oct 16, 2008 3:13 am

Can anyone tell why i am getting WA .I am using (nlogk) algo for it.
Here is my code.

#include<iostream>
using namespace std;
int a[50000],p[50000],pt[50000],i,j,k;
int srch(int b)
{
int m;
for(m=j-1;m>=0;m--)
{
if(a[m]==b)
break;
}
return m;
}
void prnpath(int ind)
{
if(ind==-1)
return;
prnpath(pt[ind]);
cout<<a[ind]<<"\n";

}
main()
{ int in;
i=0;
while(cin>>a)
{
i++;
}
p[0]=a[0];
pt[0]=-1;
k=0;
for(j=1;j<i;j++)
{
in=(lower_bound(p,p+k+1,a[j])-p);
if(in>k)
{
k++;
p[k]=a[j];
}
else
p[in]=a[j];
if(k-1>=0)
pt[j]=srch(p[k-1]);
else
pt[j]=-1;
}
cout<<k+1<<"\n"<<"-"<<"\n";
prnpath(srch(p[k]));
}

oscartheroot
New poster
Posts: 5
Joined: Sat Oct 11, 2008 1:03 pm

481 Runtime Error!!

Post by oscartheroot » Sat Nov 08, 2008 11:54 pm

I don't understand what's wrong in my code, I haven't found any test case in which the program gives runtime error, I mean, it works for all the cases I've tested!!

Here's my code:

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    long long n;
    vector <long long> num, v;
    vector <vector <long long> > seq;
    while (cin>>n){
          num.push_back (n);
          v.push_back (1);
          seq.push_back (vector <long long> (1, n));
          long long pos=num.size()-1, max=0;
          for (int j=0; j<num.size()-1; j++){
              if (num[j]<num[num.size()-1]) if (v[j]>=max){max=v[j]; pos=j;}
          }
          v[v.size()-1]=max+1;
          seq[v.size()-1]=seq[pos];
          if (pos!=num.size()-1)seq[v.size()-1].push_back (n);
    }
    if (num.size()==0) {cout<<0<<endl<<"-"<<endl;return 0;}
    long long pos=0, max=0;
    for (int i=0; i<v.size(); i++) if (v[i]>=max){max=v[i]; pos=i;}
    cout<<max<<endl<<"-"<<endl;
    for (int i=0; i<seq[pos].size(); i++) cout<<seq[pos][i]<<endl;
    return 0;
}
I really do not understand... :oops: :-? :evil:

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 481 Runtime Error!!

Post by newton » Wed Jan 07, 2009 4:47 pm

what do u mean by the line:

Code: Select all

 vector <vector <long long> > seq;

BonDo2
New poster
Posts: 1
Joined: Thu Nov 19, 2009 12:41 am

481 - What Goes Up

Post by BonDo2 » Thu Nov 19, 2009 12:45 am

Code: Select all

#include <iostream>
using namespace std;


int main ()
{
	int n =0;
	int MaxLength =1;
	int k=0;
	int Arr[50000];
	int Length[50000];
	int Seq[50000];

	while (cin >>Arr[n])
	{
      	n++;
	}

	for (int i = 0; i < n; i++)
	{
		Length[i]=1;
		for (int j = 0; j < i; j++)
		{
			if(Arr[j]<Arr[i] && 1+Length[j] >Length[i])
				Length[i] = Length[j]+1;
		}
		MaxLength = max(MaxLength,Length[i]);
	}
	for (int i = 0; i < n; i++)
	{
		if (MaxLength ==Length[i])
		{
			for (int j = 0; j < i; j++)
			{
				if (Arr[j] <Arr[i])
				{
					Seq[k] = Arr[j];
					k++;
				}
			}
			Seq[k] = Arr[i];
			k++;
			break;
		}
	}
	cout <<MaxLength<<endl<<"-"<<endl;
	for (int i = 0; i < k; i++)
	{
		cout <<Seq[i]<<endl;
	}
	return 0;
}
Help Me PLZ :S

mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

Re: 481 - What Goes UP (Run Time Error)

Post by mostafa_angel » Fri Nov 20, 2009 11:44 pm

why the size of your arrey is 5000 !?
maybe the sequence is more than 5000...
I think it is better use vector... :wink:

mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

Re: 481 - What Goes UP (Run Time Error)

Post by mostafa_angel » Fri Nov 20, 2009 11:57 pm

by the way you can use arrey as global variables whit size of more than 50000...
for example 100000...
:wink:

Post Reply

Return to “Volume 4 (400-499)”