10930 - A-Sequence

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

Moderator: Board moderators

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo »

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

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

Post by 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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k »

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 :D

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:

Post by 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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

rejudgement of 10930

Post by 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
New poster
Posts: 18
Joined: Thu Oct 28, 2004 10:13 am

10930 - A-Sequence

Post by 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;
}
Never argue with an idiot, they'll drag you down to their level and beat you with experience! (unknown)

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince »

Hi rube

have you tried this input ?

Input
3 1 2 4
5 1 2 4 8 45

Thanks
MAP

rube
New poster
Posts: 18
Joined: Thu Oct 28, 2004 10:13 am

Post by 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.
Never argue with an idiot, they'll drag you down to their level and beat you with experience! (unknown)

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger »

Try this:

Code: Select all

Input:
5 5 6 7 8 16

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by 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 :D

rube
New poster
Posts: 18
Joined: Thu Oct 28, 2004 10:13 am

Post by rube »

OOPS!! Thanks for your help. :)
Never argue with an idiot, they'll drag you down to their level and beat you with experience! (unknown)

spider_6765
New poster
Posts: 9
Joined: Sun Jan 08, 2006 9:57 pm

10930 (memory limit exceeded) someone please help me

Post by 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
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by 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
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

10930 - A-Sequence

Post by 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
Last edited by Ankur Jaiswal on Wed May 10, 2006 5:42 pm, edited 1 time in total.

Post Reply

Return to “Volume 109 (10900-10999)”