231 - Testing the CATCHER

[poshenghsu]

I got WA , but I thought my code is right .
Could anybody tell me what's wrong with it ?
Thanks !
Here is my code:

Code: Select all

#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;

int main(){
   int init_data;
   int cnt=0;
   while(cin>>init_data && init_data!=-1){
      if(cnt) cout<<endl;
      cnt++;
      vector<int> h,m;
      h.push_back(init_data);
      m.push_back(1);
      int data;
      while(cin>>data && data!=-1){
         int max=0;
         for(int i=h.size()-1;i>=0;i--){
            if(h[i]>=data){
               if(m[i]>max) max=m[i];
            }
         }
         m.push_back(max+1);
         h.push_back(data);
      }
      cout<<"Test #"<<cnt<<':'<<endl
          <<"  maximum possible interception: "
          <<*max_element(m.begin(),m.end())<<endl;
   }
}

And test data that I have tested.
Input:

Code: Select all

25
5
4
3
2
1
0
24
23
22
21
3
2
1
24
24
24
24
24
-1 
233
233
233
-1 
0
-1
500
-1 
423
312
23
234
234
22
2
32
-1 
423
234
2434
525
23
4343
234
22
312
2
32
-1 
3
432
423
2423
423
423
-1 
3
7324
2352
23
432
432
432
32
324
23
2
22
2
2
-1 
389
207
155
300
299
170
158
65
-1 
23
34
21
-1 
32767
32764
32760
32000
1
-1 
-1

Output:

Code: Select all

Test #1:
  maximum possible interception: 8

Test #2:
  maximum possible interception: 3

Test #3:
  maximum possible interception: 1

Test #4:
  maximum possible interception: 1

Test #5:
  maximum possible interception: 6

Test #6:
  maximum possible interception: 5

Test #7:
  maximum possible interception: 4

Test #8:
  maximum possible interception: 10

Test #9:
  maximum possible interception: 6

Test #10:
  maximum possible interception: 2

Test #11:
  maximum possible interception: 5

[tan_Yui]

Hi, poshenghsu.
That's easy. After you change the word 'interception' to 'interceptions', you will get 'Accepted'.
And you should insert a blank line after the last case to avoid Presentation Error.

Thank you.

[rebrane]

How strange. Although the problem description for 231 warns that "If your solution is based on an inefficient algorithm, it may not execute in the allotted time.", my correct submission executes in a rather unrealistic 0.00 seconds with minimum memory usage. And it appears that about a thousand people have the same result.

What gives? I was hoping that the test case would be hard enough that the scoreboard would give me a good idea of how my algorithm stacked up. This makes it look like it's not actually being tested at all.

[mf]

Try the problem 481 "What goes up."
It's basically the same as 231, but its input data is more challenging.

[Salman]

Getting Wa for this code?

Code: Select all

/*
Name: Testing the catcher
Number: 231
Type :  lis
Process : ON
Author :Salman Zaman
Email : zamansalman@gmail.com
Date : 27/08/05 23:31





*/



#include<stdio.h>
#include<string.h>



//#include<conio.h>
#define SIZE 10000


int height[SIZE];
int length[SIZE];
int predecessor[SIZE];

int input[SIZE];

void lis(int n){
 
    int i,j;
    
        for(i=1;i<=n;i++){
                length[i]=1;
                predecessor[i]=0;
         }    
    

    
    for(i=1;i<=n-1;i++){
        for(j=i+1;j<=n;j++){
            if(input[j]<input[i]){
                if(length[i]+1>length[j]){
                    length[j]=length[i]+1;
                    predecessor[j]=i;
                    
                }    
            }    
        }    
    }    
          
    
    
}              




int main(){

       char ch;
       int n,i,j,count=1;

  //     freopen("231.txt","r",stdin);
            i=1;
            while(scanf("%d",&n)==1){
                if(n>0){
                      input[i]=n;
                      i++;                 
                }   
                else{
                    lis(i-1);
                    if(length[i-1]){
                        printf("Test #%d:\n",count);
                        printf("  maximum possible interceptions: %d\n\n",length[i-1]);
                    }    
                    i=1;
                    count++;
                 }     
            }                                      

     
//   getch();
   return 0;
}

[Jan]

You are printing len[i-1]. len[i-1] can not be the desired output. Just see the I/O...

Input:

Code: Select all

9
8
6
20
11
10
3
12
-1

Output:

Code: Select all

Test #1:
  maximum possible interceptions: 4

After finding LDS you have to check all the values of len[] and find the maximum one. And there is no need to consider the predecessor[] array.

[mosaick2]

432
423
2423
423
423
-1

Test it. Correct Answer is 4.
The missile can move forward.

[Witherwix]

Hi, can anyone tell me why do I get PE?? I really have no idea.

Code: Select all

#include <iostream>

using namespace std;

int ma=0;
int koniec=0;
int test;
int D[10000];
int W[10000];
int stop=0;
int i,j;
int n;
int lp=1;

int main()
{
    while(koniec==0)
    {
      n=0;
      cin>>test;
      n++;
      W[0]=test;
      if(test==-1)
      {
        koniec=1;
      }
      if(koniec==0)
      {
        while(test!=-1)
        {
          cin>>test;
          W[n]=test; n++;     
         if(test==-1)
         {
           for(i=0; i<n; i++)
           {
             D[i]=1;
           }
             n--;
             ma=1;
             for(i=0; i<n-1; i++)
             {
               for(j=i+1; j<n; j++)
               {
                 if(W[j]<W[i])
                 {
                   if(D[i]+1>D[j])
                   {
                     D[j]=D[i]+1;
                     if(D[j]>ma)
                     ma=D[j];       
                   }
                 }
               }
             }
           cout<<"Test #"<<lp<<":"<<endl;
           cout<<"  maximum possible interceptions: ";
           cout<<ma<<endl;
           cout<<endl;        
         }
        }                      
      }//If koniec             
    }   
return 0;
}

[Jan]

Don't open a new thread if there is one already. There are many threads for this problem. Search and use any of the existing ones. You have to print a blank line between two consecutive cases; not after every case.

[toru]

HI, really i dont know whether it is dp(LIS)???, but i found it bit easier so i tried, my i/0 comes correct, if my code is anyway wrong then i will keep it for later, coz i m just a novice, still long way to go for solving this dp type question, anywayzz i attach my code beneath, i just used my basic logic..... plzzz any1 gv me just an answer, alwayz be gratefull

Code: Select all

#include<stdio.h>
#include<string.h>
#define MAXI 100000

int main()
{
	long in[MAXI], n=0, max, i, count, j, hold, test, flag=0, hv[MAXI], k, tp=0;

	test=1;
	n=0;
	k=0;
	while(scanf("%ld", &in[0])==1 && in[0]!=-1)
	{	
	  tp=in[0];
	  count=0;
	  hold=0;
	  max=0;
	  n=1;
	  k=1;
	  memset(in, '0', sizeof(in));
	  memset(hv, '0', sizeof(hv));
	  
	  hv[0]=tp;
	  while(scanf("%ld", &in[n])==1 && in[n]!=-1)
	  {
		  hv[k]=in[n];
		  k++;
		  n++;
	  }
	  
	  hold=hv[0];
	  for(i=1; i<=k; i++)
	  {
	    if(hold>=hv[i])
		{
		  max=hv[i];
		  count++;
		  break;
		}
	  }

	  for(j=i; j<k; j++)
	  {
	    if(hv[j]<=max)
	  	  count++;
	  }
     
	  printf("Test #%ld:\n", test++);
	  printf("  maximum possible interceptions: %ld\n", count);
	}

	return 0;
}

[mf]

HI, really i dont know whether it is dp(LIS)???

No. Your algorithm is an example of what we call a greedy algorithm. They almost never work.

For this problem, actually, there is a greedy algorithm that works, but that's not the case for your algorithm - it fails, for example, on this simple case: 1, 5, 4, 3, 2.

plzzz any1 gv me just an answer, alwayz be gratefull

Forty two!

I like this one, too!

[toru]

Thanks to mf for the reply, Hope u r good, can u plzz tell me from where can i learn dp, i m weak in converting pseudocode to actual code ...................... Thanx again & TC

[mf]

Here's a good place to start:
http://www.google.com/search?hl=en&q=dy ... g+tutorial

[Obaida]

Thanks mf
I also need to learn DP.

[toru]

HI, Guru Thanks a lot, We NOVICE wants support and help like this from u... hope i will get u whenever i need help , THANKS Again...............
GOOD BYE n TC


megh putra