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 » Sun Apr 29, 2007 7:28 pm

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 » Wed Jun 13, 2007 5:58 am

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 » Wed Jun 13, 2007 12:07 pm

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

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

Post by WingletE » Mon Aug 13, 2007 3:40 pm

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 » Mon Aug 13, 2007 10:05 pm

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

User avatar
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 » Wed Sep 03, 2008 8:57 pm

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.

User avatar
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 » Tue Sep 09, 2008 10:18 am

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 » Wed May 20, 2009 7:51 pm

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 » Thu May 21, 2009 10:35 am

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 » Thu May 21, 2009 11:40 am

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 » Sun Nov 14, 2010 10:00 pm

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 » Thu May 26, 2011 2:37 pm

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 » Thu May 03, 2012 8:53 am

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 » Thu May 03, 2012 9:09 am

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 » Thu May 03, 2012 11:21 pm

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

Post Reply

Return to “Volume 4 (400-499)”