497 - Strategic Defense Initiative

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

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

Post 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.
Ami ekhono shopno dekhi...
HomePage

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

fed up with TLE...

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

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi »

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

WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

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

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

Post 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.
Ami ekhono shopno dekhi...
HomePage

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

Re: Wa 497 Strategic Defense Initiative

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

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

Re: Wa 497 Strategic Defense Initiative

Post 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..
Solving for fun..

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

RUNTIME ERROR 497 Strategic Defense Initiative

Post 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.
Last edited by calicratis19 on Thu May 21, 2009 11:47 am, edited 1 time in total.
Heal The World

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: Wa 497 Strategic Defense Initiative

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

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: Wa 497 Strategic Defense Initiative

Post 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.
Heal The World

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

Re: Wa 497 Strategic Defense Initiative

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

ss89162504
New poster
Posts: 2
Joined: Sat May 07, 2011 6:39 pm

Re: Wa 497 Strategic Defense Initiative

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

}

tzupengwang
New poster
Posts: 36
Joined: Fri Dec 02, 2011 1:30 pm
Location: Kaohsiung, Taiwan

Re: Wa 497 Strategic Defense Initiative

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


tzupengwang
New poster
Posts: 36
Joined: Fri Dec 02, 2011 1:30 pm
Location: Kaohsiung, Taiwan

Re: Wa 497 Strategic Defense Initiative

Post by tzupengwang »

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Wa 497 Strategic Defense Initiative

Post by brianfry713 »

Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 4 (400-499)”