481 - What Goes Up

[helloneo]

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]

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

[asif_rahman0]

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]

I knew that url , 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.

[asif_rahman0]

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

[nymo]

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

[joebin]

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]

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.

[joebin]

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

[shashank.neo]

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]

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

[newton]

what do u mean by the line:

Code: Select all

 vector <vector <long long> > seq;

[BonDo2]

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]

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

[mostafa_angel]

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