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

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Wed May 10, 2006 5:34 pm

i have solved this problem without sorting and i got accepted , check your code carefully , maybe you have some bugs somewhere else,

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

Post by Ankur Jaiswal » Wed May 10, 2006 5:41 pm

i submitted the same code again and got accepted.
i just didnt use sorting.
although i got WA some 4-5 times more.
the same code then gave runtime error (although my array size was 1050.. which means that input contains integers gretaer than 1050).
neways noe its accepted.

altaf hussain(sust_2002)
New poster
Posts: 10
Joined: Sat Aug 19, 2006 7:23 pm
Location: bangladesh
Contact:

10930 - A-Sequence

Post by altaf hussain(sust_2002) » Sun Aug 20, 2006 11:21 pm

i am getting wa in 10930. i saw all the post in the board but getting the same result. hope u will help me to get it AC.



here is my code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define sz 30010

int comp_fun(const void *a, const void *b){
int *x=(int*) a;
int *y =( int* ) b;
int m= *x;
int n= *y;
return ( m - n );
}

void main(){
int array [sz],n,num[40],sum,i,j,cas=0,flag;
//freopen("10930.txt","w",stdout);
while ( scanf ( "%d" , &n ) == 1 ) {

memset( array, 0 , sizeof (array) );
sum = flag = 0 ; cas++ ;

printf ( "Case #%d:", cas );

for( i=0 ; i<n ; i++ ) {
scanf( "%d" , &num );
printf(" %d",num);
}

qsort(num , n , sizeof( int ),comp_fun);

for( i = 0 ; i<n ; i++){
array[ num ]++;
for( j=0 ; j < num ; j++ ) {
if( array[j] != 0 ) {
sum = num + j ;
array[ sum ]++ ;
}
}
}

for(j=0;j<sz;j++)
if(array[j]>=2){
flag=1;
break;
}

if(flag)
printf("\nThis is not an A-sequence.\n");
else
printf("\nThis is an A-sequence.\n");
}
}

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Post by Towhid » Mon Aug 21, 2006 12:00 pm

The first thing is you should not sort the data. And 2nd thing when there is a thread containing the same problem use that thread, don't create a new one. However you haven't checked if the data are strictly increasing order. Try it...
From 0 to 0

altaf hussain(sust_2002)
New poster
Posts: 10
Joined: Sat Aug 19, 2006 7:23 pm
Location: bangladesh
Contact:

Post by altaf hussain(sust_2002) » Mon Aug 21, 2006 12:32 pm

another WA.now without sort.
thanks for yr (respected Thowid) reply.

my modified code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define sz 30010


void main(){
int array [sz],n,num[40],sum,i,j,cas=0,flag,pre_num;

while ( scanf ( "%d" , &n ) == 1 ) {
pre_num = 0;

memset( array, 0 , sizeof (array) );
sum = flag = 0 ; cas++ ;

printf ( "Case #%d:", cas );

for( i=0 ; i<n ; i++ ) {

scanf( "%d" , &num );
if(num <= pre_num)
flag= 1;
pre_num = num;
printf(" %d",num);
}

if(!flag){
for( i = 0 ; i<n ; i++){
array[ num ]++;
for( j=0 ; j < num ; j++ ) {
if( array[j] != 0 ) {
sum = num + j ;
array[ sum ]++ ;
}
}
}

for(j=0;j<sz;j++)
if(array[j]>=2){
flag=1;
break;
}
}

if(flag)
printf("\nThis is not an A-sequence.\n");
else
printf("\nThis is an A-sequence.\n");

}
}

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Post by Towhid » Mon Aug 21, 2006 12:39 pm

altaf hussain(sust_2002) wrote:
for( i = 0 ; i<n ; i++){
array[ num ]++;
for( j=0 ; j < num ; j++ ) {
if( array[j] != 0 ) {
sum = num + j ;
array[ sum ]++ ;
}
}
}
}

I think this doesn't work correctly. Try the input:

Code: Select all

5 1 6 8 10 12
This is an A-sequence, but what your program says?????
From 0 to 0

altaf hussain(sust_2002)
New poster
Posts: 10
Joined: Sat Aug 19, 2006 7:23 pm
Location: bangladesh
Contact:

Post by altaf hussain(sust_2002) » Mon Aug 21, 2006 1:39 pm

i am still getting WA. Please help!!!

here my code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define sz 30010


void main(){
int array [sz],n,num[40],sum,Max,i,j,cas=0,flag,pre_num;

while ( scanf ( "%d" , &n ) == 1 ) {
pre_num = Max=0;

memset( array, 0 , sizeof (array) );
sum = flag = 0 ; cas++ ;

printf ( "Case #%d:", cas );

for( i=0 ; i<n ; i++ ) {

scanf( "%d" , &num );
if(num <= pre_num)
flag= 1;
pre_num = num;
printf(" %d",num);
}

if(!flag){
for( i = 0 ; i<n ; i++){
array[ num ]++;
for( j=0 ; j < num ; j++ ) {
if( array[j] != 0 ) {
sum = num + j ;
array[ sum ]++ ;
}
}
}

for(j=0;j<= pre_num;j++)
//if(array[ j]!=0)
// printf("a [ %d]= %d",j,array[j]);
if(array[j]>=2){
flag=1;
break;
}
}

if(flag)
printf("\nThis is not an A-sequence.\n");
else
printf("\nThis is an A-sequence.\n");

}
}

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

Post by Towhid » Mon Aug 21, 2006 1:54 pm

altaf hussain(sust_2002) wrote: for( j=0 ; j < num ; j++ ) {
if( array[j] != 0 ) {
sum = num + j ;
array[ sum ]++ ;
}
}
}

}

Still problem here. Try

Code: Select all

1 6 8 10 25
This is not an A sequence, but your program outputs the opposite...
From 0 to 0

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Mon Aug 28, 2006 1:02 pm

hey !
i dont know what to do ..... i applied a very straight forward method and passed all the test cases. I was afraid to get TLE but it got WA!!!

I cant have any clue ... is there anyone to help?

Code: Select all

cut after AC
Last edited by Kallol on Wed Aug 30, 2006 10:37 am, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Aug 28, 2006 2:20 pm

Why are you sorting the sequence?
(don't forget to change the condition, too)

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Tue Aug 29, 2006 11:53 pm

Darko wrote:Why are you sorting the sequence?
(don't forget to change the condition, too)
Yep, "1 2 4" is an A-sequence, but "4 2 1" is not an A-sequence.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Wed Aug 30, 2006 5:49 am

well,
i submitted the same code without sorting , but again i got a WA. I myself dont have any reason to sort the sequence. After getting WA without sorting , I found in one of the threads here that someone got AC with sorting. So, I sorted it. Anyway now my code looks like as follows:
can you guess why is it getting WA?

Code: Select all

cut after AC
Last edited by Kallol on Wed Aug 30, 2006 10:36 am, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Aug 30, 2006 6:02 am

I told you to change the condition. Now that they are not sorted, will this work?

Code: Select all

 if(N[i]==N[i-1])...

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Wed Aug 30, 2006 7:32 am

Hi Darko!
I got ur point ! I have changed my code for equality check but still cnat get rid of WA!
here it is..

Code: Select all

cut after AC
Last edited by Kallol on Wed Aug 30, 2006 10:36 am, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Wed Aug 30, 2006 8:07 am

No, I don't think you got it :)

I just added " && N>N[i-1]" somewhere and it was AC

Just checking the I/O that is in this thread would've helped you.

Btw, this problem took me forever to solve. I recoded it 4-5 times and once it worked. I have no idea what mistakes I made in other versions.

Post Reply

Return to “Volume 109 (10900-10999)”