10930 - A-Sequence

[arsalan_mousavian]

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

[Ankur Jaiswal]

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

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]

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

[altaf hussain(sust_2002)]

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]

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

[altaf hussain(sust_2002)]

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]

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

[Kallol]

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

[Darko]

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

[Martin Macko]

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.

[Kallol]

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

[Darko]

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

[Kallol]

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

[Darko]

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.