497 - Strategic Defense Initiative

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

[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???

[ayeshapakhi]

O(n^2) solution is ok for this problem.....
ur problem is elsewhere.

[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?

[Jan]

Your algorithm is not correct. You are checking only previous two elements which is wrong.

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

The answer is no.

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

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

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

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

[calicratis19]

many many thanks to mf. this code gave me so much pain

i got ac. infinite thanks to mf

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

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

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

}

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

[tzupengwang]

I've passed all I/O I could find but still receive WA ,can anyone help??TKS

[brianfry713]

I got AC with this algorithm:
http://www.algorithmist.com/index.php/L ... sequence.c