10930 - A-Sequence

[Timo]

Yesterday I got Accepted on this problem without sorting input sequence, so I can assume, that sorting isn't necessary. It implies, that every sequence in which order of elements after sorting is different from original order isn't A-Sequence.

Best regards
DM

If you can get AC without sorting, I think for this problem all the judge test input is in the sorted order.

[Tamagodzi]

The sequence is composed by integers, each integer is greater than or equal to 1 and less than or equal to 1000.

Wrong ... there are inputs that are not in that range ... another way making an easy problem hard ...

[windows2k]

The sequence is composed by integers, each integer is greater than or equal to 1 and less than or equal to 1000.

Wrong ... there are inputs that are not in that range ... another way making an easy problem hard ...

Sorry, I have passed all the input/output above.
But still get WA.
Could someone give me more input/output?
Thx

[sergio]

Unfortunately, there is an input where the value 1003 appears. I have already seen the input of this problems many times, but I could only see this error now

I will try to fix this error and to send the new input to UVA's site.

I am sorry!

S

[Krzysztof Duleba]

There's something wrong with the new judgements. I got the following message:

Code: Select all

  ID        Submission date    Problem  Previous  Fixed verdict
--------  --------------------  -------  --------  -------------
04051252  2005/10/19 23:03 UTC    10930       WA           RE
04051262  2005/10/19 23:11 UTC    10930       AC           RE

However, submitting the same code that was supposed to RE gave me AC a minute ago (and it's not the case that I was lucky this time, the code is correct).

[rube]

I am getting wa :
plz help me, here is my code:

Code: Select all

#include <stdio.h>
const int imax=1005;
int main()
{
	int num,nump,sum[imax],i,j,n,qsum,f,cas=1;
	
	while(scanf("%d",&n)==1)
	{
		sum[0]=qsum=f=0;
		for(i=1;i<imax;i++)sum[i]=-1;
		printf("Case #%d:",cas++);
		for(i=0;i<n;i++)
		{
			scanf("%d",&num);
			printf(" %d",num);
			if(nump>=num)
				f=1;	
			qsum+=num;
			if(f==0)
			{
				if(sum[num]==-1)
					sum[num]=1;
				else f=1;
				if(f==0)
				{
					for(j=num+1;j<imax && j<=qsum;j++)
					{
						if(sum[j-num]!=-1)
							sum[j]=sum[j-num]+1;
					}
				}
			}
			nump=num;
		}				
		if(f)
			printf("\nThis is not an A-sequence.\n");
		else
			printf("\nThis is an A-sequence.\n");
	}
	return 0;
}

[mohiul alam prince]

Hi rube

have you tried this input ?

Input
3 1 2 4
5 1 2 4 8 45

Thanks
MAP

[rube]

nump should be initialize.
I fix it but it does not help me to get AC.
Can you give me some more input output?
I test all the input in this board and my solution give correct answer for those inputs.

[krijger]

Try this:

Code: Select all

Input:
5 5 6 7 8 16

[A1]

I found your problem!!
Just change your inner for loop with this line:

Code: Select all

for(j=num+1;(j-num)<num &&j<imax && j<=qsum;j++)

and enjoy the ac

[rube]

OOPS!! Thanks for your help.

[spider_6765]

should i try with a larger array?
or a different algo?

Code: Select all

/*************************************************************/
/*  MCA03901 SPIDER  7/2/06           */
/*************************************************************/

#include<stdio.h>
#define MAX 1000000
long long int array[MAX],d,seq[MAX],add[MAX],i,temp,seq_flag=0,count=1;

main(){
    for(count=1;;count++){
    scanf("%lld",&d);
    seq_flag=1;
    seq[0]=0;
     for(i=1,temp=0;i<=d;i++){
       scanf("%lld",&seq[i]);
       temp+=seq[i];

       if(seq[i]>seq[i-1] && seq_flag==1 && array[seq[i]]!=count &&add[seq[i]]!=count){
	  array[seq[i]]=count;
	  add[temp]=count;
       }
       else seq_flag=0;
     }
     printf("Case #%lld:",count);
     for(i=1;i<=d;i++)printf(" %lld",seq[i]);
     printf("\n");
     switch(seq_flag){
	  case 1:printf("This is an A-sequence.\n");break;
	  case 0:printf("This is not an A-sequence.\n");break;
     }
    }


}

[sergio]

I think you are not evaluating all the possible sums involving the elements of the sequence, so you need to change the algo. Try this input:

4
1 3 5 8

Your output is:
Case #1: 1 3 5 8
This is an A-sequence.

And should be:
Case #1: 1 3 5 8
This is not an A-sequence.

[sclo]

The idea for the dp is classical:
define a function f(k,s,t) where f(k,s,t)=true iff s is a sum of at least t of the first k elements.

[Ankur Jaiswal]

i used the following algorithm...
first i printed the given input.
then sorted it.
then i checked whether a number can be expressed as a sum of two or more numbers.
but it gave wrong answer.
and 1 more thing.. do we really need to sort the input? because that can change the relative order of the input and hance the term "sum of two or more distinct earlier terms of the sequence." will not have any meaning.

neways here's my code :

Code: Select all

Accepted