Page 8 of 10

Posted: Sun Apr 29, 2007 7:28 pm
by Jan
The input set is not fully correct I think. My accepted code ignores blank lines. I think there is no special case. So, you can post your code.

fed up with TLE...

Posted: Wed Jun 13, 2007 5:58 am
by soddy
I have tried everythin but still i am getting TLE...
wat is the complexity required for this problem

First I coded using O(n2) and got TLE then i chked by submitting O(nlogk) solution from net...again I got TLE....i dont think I/O is a problem coz i have tried a lot of test cases......but still here is my I/O code:

Code: Select all

int main()
{
	int n;
	cin>>n;
	string s;
	getline(cin,s);
	for(int kase=0;kase<n;kase++)
	{
		vector<int> x;
		if(kase>0)
			cout<<endl;
		else
			getline(cin,s);
		while(getline(cin,s))
		{
			if(s.length()==0)
				break;
			const char *cs=s.c_str();	
			x.push_back(atoi(cs));
		}
		vector<int> y=lis(x),z;
		cout<<"Max hits: "<<y.size()<<endl;
		for(int i=0;i<y.size();i++)
			cout<<x[y[i]]<<endl;
	}
	return 0;
}	
if I/O is not a problem then i'll submit my whole code...can anyone help???

Posted: Wed Jun 13, 2007 12:07 pm
by ayeshapakhi
O(n^2) solution is ok for this problem.....
ur problem is elsewhere.

Posted: Mon Aug 13, 2007 3:40 pm
by WingletE

Code: Select all

//  Q497: Strategic Defense Initiative
//  LIS(最長遞增子序列) 
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <ctype.h>

using namespace std;

int main()
{
    int n = 0;
    vector<int> array, array2;
    char str[11];
    
    cin >> n;
    getchar();
    cin.getline(str, 11, '\n');
    
    for(n--; n >= 0; n--)
    {
        array.clear();
        array2.clear();
        
        while(cin.getline(str, 11, '\n'))
        {
            if(strlen(str) == 0)
                break;
            
            array.push_back(atoi(str));
        }
        
        for(int i = 0; i < array.size(); i++)
        {
            if(array2.size() == 0)
                array2.push_back(array[i]);
            else
            {
                if(array2[array2.size()-1] < array[i])
                    array2.push_back(array[i]);
                else if(array2.size() == 1)
                    array2[0] = array[i];
                else if(array2[array2.size()-2] < array[i])
                    array2[array2.size()-1] = array[i];
            }
        }
        
        cout << "Max hits: " << array2.size() << endl;
        
        for(int i = 0; i < array2.size(); i++)
            cout << array2[i] << endl;
        
        if(n != 0)
            cout << endl;
    }
    
    return 0;
}
I've tried many times and it had passed all the I/O I found. I think my code is OK but it keeps getting WA.
Could somebody check it for me or give me some more I/O please?

Another question: After the last number, is there any '\n' before the EOF?

Posted: Mon Aug 13, 2007 10:05 pm
by Jan
Your algorithm is not correct. You are checking only previous two elements which is wrong.
WingletE wrote:Another question: After the last number, is there any '\n' before the EOF?
The answer is no.

Re: Wa 497 Strategic Defense Initiative

Posted: Wed Sep 03, 2008 8:57 pm
by newton
i cant figure out why WA?
please help me.
code:

Code: Select all

#include <cstdio>
#include <string>
#include <algorithm>
#define INF 1<<29
#define MAX 100000

using namespace std;

int A[MAX];
int L[MAX];
int P[MAX];

int maxLenth(int array[], int n){
	int max = -INF,i;
	for(i = 0; i<n; i++)
		if(array[i] > max)
			max = i;
		return max;
}

void printPath(int P[],int p){
	if(p == INF)
		return;
	printPath(P,P[p]);
	printf("%d\n",A[p]);
}

void setInitial(int n){
	for(int i = 0; i<n; i++){
		P[i] = INF;
		L[i] = 1;
	}
}


int main(){
	//freopen("in.txt","rt",stdin);
	int input,i,j,max,n;
	char str[20];	
	scanf("%d\n",&input);	
	while(input--){		
		i = 0;
		while(gets(str) && strcmp(str,"")){
			sscanf(str,"%d",&A[i++]);
		}		
		n = i;
		setInitial(n);
		for(i = 0; i<n; i++){
			for(j = i+1; j<n; j++){
				if(A[i] < A[j] && L[j] < L[i]+1)
				{
					L[j] = L[i] + 1;
					P[j] = i;
				}
			}
		}		
		max = maxLenth(L,n);
		printf("Max hits: %d\n",L[max]);
		printPath(P,max);
		printf("\n");
	}
	
	return 0;
}
thanks in advanced.

Re: Wa 497 Strategic Defense Initiative

Posted: Tue Sep 09, 2008 10:18 am
by linux
There an ambiguous segment in your code:

Code: Select all

    void printPath(int P[],int p){
       // Two array-varialble in the same name P[], (one global, another local)

       if(p == INF)
          return;
       printPath(P,P[p]);
       printf("%d\n",A[p]);
    }
I think it's a good habit to avoid this type of things for clarity and precise functionality of functions.

Try out after recode..

You will get PE(I'm not sure if that gives WA) because
(In description)
The outputs of two consecutive cases will be separated by a blank line.
Also this function is absolutely wrong which might reward PE:

Code: Select all

    int maxLenth(int array[], int n){
       int max = -INF,i;
       for(i = 0; i<n; i++)
          if(array[i] > max)
             max = i;
       return max;
    }
I let it be judged by your intelligence! Good luck..

RUNTIME ERROR 497 Strategic Defense Initiative

Posted: Wed May 20, 2009 7:51 pm
by calicratis19
got AC. my mistake was the way of taking input......

Code: Select all

	gets(str);
		while(str[0]!=NULL)
		{
			array[i++]=atoi(str);
			gets(str);		
		}
	
thnks to mf.

Re: Wa 497 Strategic Defense Initiative

Posted: Thu May 21, 2009 10:35 am
by mf
Well, this part of your code is wrong:

Code: Select all

      while(str[0]!=NULL)
      {
         array[i++]=atoi(str);
         gets(str);      
      }
You have to check the return value of gets() to determine that you've reached EOF.

Re: Wa 497 Strategic Defense Initiative

Posted: Thu May 21, 2009 11:40 am
by calicratis19
many many thanks to mf. this code gave me so much pain :evil: :evil: :evil: :evil:

i got ac. infinite thanks to mf :lol: :lol: :lol: :lol: :lol:

ps: no need to check for empty line . i think there is no input like that.

Re: Wa 497 Strategic Defense Initiative

Posted: Sun Nov 14, 2010 10:00 pm
by BUET
what's the reason of runtime error?

#include<iostream>
#include <vector>
#include<cctype>
#include<cstring>
using namespace std;


template<typename T> vector<int> find_lis(vector<T> &a)
{
vector<int> b, p(a.size());
int u, v;

if (a.size() < 1) return b;

b.push_back(0);

for (int i = 1; i < (int)a.size(); i++) {
if (a[b.back()] < a) {
p = b.back();
b.push_back(i);
continue;
}

for (u = 0, v = b.size()-1; u < v;) {
int c = (u + v) / 2;
if (a[b[c]] < a)
u=c+1;
else v=c;
}

if (a < a[b]) {
if (u > 0)
p = b[u-1];
b = i;
}
}

for (u = b.size(), v = b.back(); u--; v = p[v]) b = v;
return b;
}


int main()
{
int a[100000];
char in[100];
int n,ca = 1;
unsigned long i;
int size;
int check = 0;
i = 0;
int t;
cin >> t;
getchar();
getchar();

n = 0;

while(t--)
{

i = 0;

while(1)
{



gets(in);

if( strlen(in) == 0)
break;

n = atoi(in);


a = n;
i++;
}



size = sizeof(a[0])*i;
vector<int> seq(a, a+size/sizeof(a[0]));
vector<int> lis = find_lis(seq);

if(check == 1)
cout << "\n";
else
check = 1;
cout << "Max hits: ";
printf("%d\n",lis.size());
for ( i = 0; i < lis.size(); i++)
printf("%d\n", seq[lis]);
seq.clear();
lis.clear();
}

return 0;
}

Re: Wa 497 Strategic Defense Initiative

Posted: Thu May 26, 2011 2:37 pm
by ss89162504
i don't know why i get RE ......

Code: Select all

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cctype>

using namespace std;

int n,t;
char IN[10];
int s[100];
int dp[100];
int parent[100];
int anw;
void print(int x)
{
     if(parent[x]!=-1)print(parent[x]);
     cout<<s[x]<<endl;
}

main()
{
     while(cin>>t)
     {
          cin.getline(IN,10);
          cin.getline(IN,10);
          while(t--)
          {    
               n=-1;
               while(cin.getline(IN,10))
               {
                    if(strlen(IN)==0)break;
                    n++;
                    s[n]=atoi(IN);
               }
               n++;
               for(int i=0;i<n;i++)dp[i]=1,parent[i]=-1;
               for(int i=0;i<n;i++)
                    for(int j=i+1;j<n;j++)
                         if(s[j]>s[i])
                              if(dp[i]+1>dp[j])
                              {
                                   dp[j]=dp[i]+1;
                                   parent[j]=i;
                              }
               anw=0;
               for(int i=0;i<n;i++)
                    anw=max(anw,dp[i]);
               cout<<"Max hits: "<<anw<<endl;
               for(int i=n-1;i>=0;i--)
                    if(dp[i]==anw)
                    {
                         print(parent[i]);
                         cout<<s[i]<<endl;    
                    }
          }   
     }

}

Re: Wa 497 Strategic Defense Initiative

Posted: Thu May 03, 2012 8:53 am
by tzupengwang
Can anyone help with my WA~

Code: Select all

/*497*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;

int main () 
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int amm;
    scanf("%d",&amm);
    char ss[100];
    gets(ss);
    gets(ss);
    while (amm--)
    {
          int s[10000];
          int g[10000];
          int i=0;
          while (1)
          {
                if(gets(ss)==NULL) break;
                if(!strlen(ss)) break;
                s[i++]=atoi(ss);                
          }
          int str[10000];
          int val[10000];int p=1;
          int ans=1;
          str[0]=s[0];
          val[0]=p;   
          for (int j=1;j<i;j++)
          {
              //strengthen
              if (s[j]>str[ans-1])
              {
                 str[ans]=s[j];
                 val[ans]=p++;
                 ans++; 
                 for (int l=ans-1;(l==ans-1||val[l+1]>val[l])&&l>=0;l--)
                 {
                     g[l]=str[l];
                     //printf("%d ",g[l]);
                 }
                 //puts("");
                 continue;                
              }
              
              int pt=lower_bound(str,str+ans,s[j])-str;
              val[pt]=p++;
              str[pt]=s[j];
              //printf("xx\n");
          }   
          printf("Max hits: %d\n",ans);
          for (int p=0;p<ans;p++)
              printf("%d\n",g[p]);
          if (amm)puts("");    
    }
    return 0;
}


Re: Wa 497 Strategic Defense Initiative

Posted: Thu May 03, 2012 9:09 am
by tzupengwang
I've passed all I/O I could find but still receive WA ,can anyone help??TKS

Re: Wa 497 Strategic Defense Initiative

Posted: Thu May 03, 2012 11:21 pm
by brianfry713