OJ Board

Posted: **Mon Oct 17, 2005 10:15 am**

Dominik Michniewski wrote: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.

Posted: **Thu Oct 20, 2005 6:41 pm**

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 ...

Posted: **Sun Nov 06, 2005 4:31 am**

Tamagodzi wrote: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

Posted: **Wed Nov 09, 2005 6:58 pm**

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

Posted: **Tue Nov 15, 2005 3:55 pm**

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).

Posted: **Wed Jan 18, 2006 10:00 am**

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;
}

Posted: **Tue Jan 31, 2006 6:49 am**

Hi rube

have you tried this input ?

Input
3 1 2 4
5 1 2 4 8 45

Thanks
MAP

Posted: **Thu Feb 02, 2006 6:06 am**

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.

Posted: **Thu Feb 02, 2006 1:47 pm**

Try this:

Code: Select all

Input:
5 5 6 7 8 16

Posted: **Sun Feb 05, 2006 2:27 pm**

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

Posted: **Mon Feb 06, 2006 12:57 pm**

OOPS!! Thanks for your help.

Posted: **Tue Feb 07, 2006 4:30 pm**

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;
     }
    }


}

Posted: **Tue Feb 07, 2006 6:19 pm**

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.

Posted: **Tue Feb 28, 2006 10:24 pm**

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.

Posted: **Wed May 10, 2006 1:49 pm**

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

OJ Board

10930 - A-Sequence

rejudgement of 10930

10930 - A-Sequence

10930 (memory limit exceeded) someone please help me

10930 - A-Sequence