My array size is 100000.. try to increase yours..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?
481 - What Goes Up
Moderator: Board moderators
Re: SOME TEST CASES, PLEASE
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 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
http://www.algorithmist.com/index.php/L ... quence.cpp
So dont cut & paste.
![;)](./images/smilies/icon_wink.gif)
Try to learn something from it.
Hope it helps.
bye
Rabbi
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
Acc now :)
Acc now, fixed a small bug, i wasn't updating parent array in a proper way
Thanks.
![:oops:](./images/smilies/icon_redface.gif)
regards,
nymo
nymo
could you give me some idea about 481 ? THX!!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.
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;
}
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.
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
HomePage
-
- New poster
- Posts: 1
- Joined: Fri Oct 03, 2008 11:22 pm
481 What goes up --- help needed!
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]));
}
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]));
}
-
- New poster
- Posts: 5
- Joined: Sat Oct 11, 2008 1:03 pm
481 Runtime Error!!
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:
I really do not understand...
![:evil:](./images/smilies/icon_evil.gif)
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;
}
![:oops:](./images/smilies/icon_redface.gif)
![:-?](./images/smilies/icon_confused.gif)
![:evil:](./images/smilies/icon_evil.gif)
-
- Experienced poster
- Posts: 162
- Joined: Thu Jul 13, 2006 7:07 am
- Location: Campus Area. Dhaka.Bangladesh
- Contact:
Re: 481 Runtime Error!!
what do u mean by the line:
Code: Select all
vector <vector <long long> > seq;
481 - What Goes Up
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;
}
-
- New poster
- Posts: 23
- Joined: Sun Oct 04, 2009 12:03 pm
Re: 481 - What Goes UP (Run Time Error)
why the size of your arrey is 5000 !?
maybe the sequence is more than 5000...
I think it is better use vector...![:wink:](./images/smilies/icon_wink.gif)
maybe the sequence is more than 5000...
I think it is better use vector...
![:wink:](./images/smilies/icon_wink.gif)
-
- New poster
- Posts: 23
- Joined: Sun Oct 04, 2009 12:03 pm
Re: 481 - What Goes UP (Run Time Error)
by the way you can use arrey as global variables whit size of more than 50000...
for example 100000...
![:wink:](./images/smilies/icon_wink.gif)
for example 100000...
![:wink:](./images/smilies/icon_wink.gif)