## 10930 - A-Sequence

Moderator: Board moderators

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia
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.

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 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
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

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

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

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

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

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

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

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