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

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Found Your Mistake ..

Post by cyfra »

Hi!

I think I have found your mistake...

Look you have:
[pascal]
const
max=100;
[/pascal]
But when I have send my own program (It got AC) I had max=8000...

When I have changed in your source code max value to 8000 it had Time Limit Exceeded :cry:

I thing you should use better algoritms otherwise you will still have Time Limit..

You can do this using Dynamic Programming...

I hope This will Help..

Good Luck :wink:

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn »

Really?
but when i used max=10000 just now, i also got WA again :cry:

???????????
:roll:

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra »

Hmm....

That's strange....

I couldn't find your mistake...


But I will be searching ...

Meanwhile maybe you will try to write this program again (I it always work :wink:

My procedure which solves this task has 5 lines...

Try to use normal dynamic programming with one table...

If you don't know how to do this write me an e-mail and I will try to help you...

But don't give up..

The mistake must be somewhere here :)

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

I think I know yuor mistake

Post by Ming Han »

This should not be there: [cpp] scanf("%dnn",&Z); [/cpp]

The question says that input to your program will consist of a sequence of integer altitudes, each on a separate line.

There is no value to specify the number of lines.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 »

That line is fulfill the specifications for the "multiple input".

SnapDragon
Problemsetter
Posts: 22
Joined: Tue Jun 11, 2002 12:35 am

Found it

Post by SnapDragon »

The problem is the line "if(D[j]<D)". Figure out what you're doing wrong there. :)

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 »

Bah, I am so retarded. Fixed it... lol... I forgot to optimize the length. I knew there had to be a "decision statement" some where:) One max and it's all good.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

497

Post by htl »

Why does this code get WA? Is there only one solution to every input set?
If the input is '1 4 3 2 5 6',what should I output?'1 4 5 6' or '1 3 5 6' or '1 2 5 6'?
[c]
#include<stdio.h>
#include<string.h>
void main(void)
{
int data[10000],lis[10000],pos[10000],count,x,y,t,n,max,z,ans[10000],top;
char s[10],c;
scanf("%d\n",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
for(n=0;fgets(s,10,stdin)!=NULL;)
{
s[strlen(s)-1]='\0';
if(!strlen(s))
break;
for(y=0,t=0;s[y]!='\0';y++)
t=t*10+s[y]-'0';
data[n++]=t;
}
for(y=0;y<n;y++)
lis[y]=1,pos[y]=-1;
max=1;
for(y=0;y<n;y++)
{
for(z=0;z<y;z++)
if(data[z]<data[y] && lis[z]+1>lis[y])
lis[y]=lis[z]+1,pos[y]=z;
if(lis[y]>max)
max=lis[y];
}
for(y=n-1;y>=0;y--)
if(lis[y]==max)
break;
top=0;
while(1)
{
ans[top++]=data[y];
t=pos[y];
if(t==-1)
break;
y=t;
}
printf("Max hits: %d\n",max);
for(y=top-1;y>=0;y--)
printf("%d\n",ans[y]);
}
}
[/c]

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor »

Read the problem description again!
Russian war tactics are fairly strange; their generals are stickers for mathematical precision. Their missles will always be fired in a sequence such that there will only be one solution to the problem posed above.
Ivor

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev »

AFAIR, there was discussion about multiple possible answers for this problem. My accepted solution outputs '1 4 5 6' for '1 4 3 2 5 6' input.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl »

I modified my code and if the input is '1 4 3 2 5 6' it will output '1 4 5 6'. But it still get WA.
[c]
#include<stdio.h>
#include<string.h>
void main(void)
{
int data[10000],lis[10000],pos[10000],count,x,y,t,n,max,z,ans[10000],top;
char s[10],c;
scanf("%d\n",&count);
for(x=0;x<count;x++)
{
if(x)
printf("\n");
for(n=0;fgets(s,10,stdin)!=NULL;)
{
s[strlen(s)-1]='\0';
if(!strlen(s))
break;
for(y=0,t=0;s[y]!='\0';y++)
t=t*10+s[y]-'0';
data[n++]=t;
}
for(y=0;y<n;y++)
lis[y]=1,pos[y]=-1;
max=1;
for(y=0;y<n;y++)
{
for(z=0;z<y;z++)
if(data[z]<data[y])
{
if(lis[z]+1>lis[y])
lis[y]=lis[z]+1,pos[y]=z;
else if(lis[z]+1==lis[y] && data[z]>data[pos[y]])
pos[y]=z;
}
if(lis[y]>max)
max=lis[y];
}
for(y=n-1;y>=0;y--)
if(lis[y]==max)
break;
top=0;
while(1)
{
ans[top++]=data[y];
t=pos[y];
if(t==-1)
break;
y=t;
}
printf("Max hits: %d\n",max);
for(y=top-1;y>=0;y--)
printf("%d\n",ans[y]);
}
}
[/c]

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl »

After checking my code again and again, I think my original
code is right. But it still gets WA>< Another question: if
the input is '1 3 2 5 4', what should I output?'1 3 5' or
'1 3 4'? Or could you mail me your code and let me read it?

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev »

'1 3 4' is a correct answer for '1 3 2 5 4'.

I've sent my code to you via private message.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

I managed to get your code working just by some cleaning up and some stricter writing of it - for example you assume that all characters in the input are digits, what about spaces, and other symbols ? You can just rewrite it with sscanf.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl »

I think data reading is the problem.
The original code:
[c]
for(y=0,t=0;s[y]!='\0';y++)
t=t*10+s[y]-'0';
[/c]
got WA.

But when I replaced it with below
[c]
for(y=0,t=0;s[y]!='\0';y++)
if(s[y]>='0' && s[y]<='9')
t=t*10+s[y]-'0';
[/c]
or
[c]
t=atoi(s);/*I have included stdlib.h*/
[/c]
got RE.

I skip any characters except the digits and got RE instead.
Do you have any suggestion on this?ex. reading by sscanf

Post Reply

Return to “Volume 4 (400-499)”