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

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

Post by Tamagodzi » 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 ...

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

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

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

Post by sergio » 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

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

rejudgement of 10930

Post by Krzysztof Duleba » 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).

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

10930 - A-Sequence

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

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

Post by mohiul alam prince » 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

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

Post by rube » 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.
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 » Thu Feb 02, 2006 1:47 pm

Try this:

Code: Select all

Input:
5 5 6 7 8 16

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

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

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

Post by rube » Mon Feb 06, 2006 12:57 pm

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


}

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

Post by sergio » 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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » 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.

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

10930 - A-Sequence

Post by Ankur Jaiswal » 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
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)”