231 - Testing the CATCHER

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

poshenghsu
New poster
Posts: 1
Joined: Wed Mar 30, 2005 5:10 pm
Location: Chang-hua,Taiwan
Contact:

Could anybody help me about 231?

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
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: Could anybody help me about 231?

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
New poster
Posts: 1
Joined: Fri Jul 08, 2005 11:39 pm
Location: Santiago de Chile
Contact:

Judging of 231

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Try the problem 481 "What goes up."
It's basically the same as 231, but its input data is more challenging.

Salman
New poster
Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

231 - Testing the CATCHER

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

mosaick2
New poster
Posts: 21
Joined: Wed Mar 08, 2006 4:05 am

and, You have to change the comparision condition.

432
423
2423
423
423
-1
Test it. Correct Answer is 4.
The missile can move forward.

Witherwix
New poster
Posts: 1
Joined: Fri Feb 23, 2007 8:34 pm

231-Presentation Error

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

toru
New poster
Posts: 17
Joined: Tue Dec 30, 2008 10:38 am

WA 231 Testing the catcher

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: WA 231 Testing the catcher

toru wrote: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
New poster
Posts: 17
Joined: Tue Dec 30, 2008 10:38 am

Re: WA 231 Testing the catcher

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: WA 231 Testing the catcher

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: WA 231 Testing the catcher

Thanks mf
I also need to learn DP.
try_try_try_try_&&&_try@try.com
This may be the address of success.

toru
New poster
Posts: 17
Joined: Tue Dec 30, 2008 10:38 am

TO MF

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