This is the problem
http://www.codechef.com/BTFR2013/problems/NITA10
And this is my solution:
http://www.codechef.com/viewplaintext/1926203
Can anyone tell me why it gives wrong answer?
2 Likes
maybe this code which i prepared during the contest, can help you in understanding where you were wrong… and also the condition of getting wrong answer might be because there was a problem of wrong test cases which was later corrected during contest…
Python Code
n = [1,2]
b = 1
for i in xrange(3,1001):
a = 2*i
n.append(0)
for j in xrange(2,a+1,2):
x = ((j-b)/2)-1
y = ((a-j)/2)-1
z = 1
if x != -1:
z*=n[x]
if y != -1:
z*=n[y]
n[i-1] += z
MOD = 100003
for indx in xrange(len(n)):
n[indx]%=MOD
n[indx] = int(n[indx])
t = input()
for i in xrange(t):
a = input()
if a==0:
print 1
else:
print n[a-1]
2 Likes
Just replace line
catalan[i] = (catalan[i] + ((catalan[j]) * catalan[i - j]) % MOD) % MOD;
by catalan[i] = (catalan[i] + ( ((long long)(catalan[j])) * catalan[i - j]) % MOD) % MOD;
WA is due to ‘int’ overflow, typecasting it to ‘long long’ will make it AC.
2 Likes
test cases of the problem was wrong but after they corrected the test cases my same WA solution got AC today …
3 Likes
and apart from this for input 0 answer was 1…
2 Likes
@shahid_khan >> FYI, I was submitting first with long long int, and it was still giving me WA. Coming back to the argument, in no way it can overflow “int”, because we are maintaining the catalan[] % 100003 at each step.
@devanshug >> WTH, for input 0 answer 1? means there are zero persons and still 1 handshake was possible?
@chandan11111 >> Yes, last night admin commented that he will rejudge the solutions and test cases will be updated. But again in the morning, after your comment saying thanks to admin for updating test cases, I submitted again but still got AC. Well, devanshug telling the answer for 0 was 1, that alone says the quality of the testcases, and of the contest as well.
@devanshug >> Thanks for the code man. Understood your logic. PS: I am thinking to learn Python since a long time.
Common guys! Not 1 handshake but 1 way of making handshakes - to do no handshakes. It is standard mathematical convention. While you will be confused by this you will always get WA in similar situations and will be angry 
Try to google Catalan sequence and you will see that Cat(0)=1 and without this the recurrence formula is wrong.
@anton_lunyov >> then why was this, the very first submission of mine got WA!
It was printing “1” for “0”.
Should I assume that there were n > 1000 in testcases then? Or would you mind telling some other bug in my code?
int overflow.
But it seems that they have negative values of N in the input at first.
Since when I add if to print 0 for n<0 I got AC.
How can it get int overflow when I am maintaining %MOD at each step? I don’t get this. 
Do (long long)(catalan[j]) * catalan[i - j]
@bugkiller >> suppose catalan[j]%100003 = 100000 and catalan[i-j]100003 = 100000 then their actual product is 10000000000 which is out of 'int' range. so compiler converts it to 'int' first which gives 10000000000 (2^32) = 1410065408 and then it calculates 1410065408 modulo 100003 = 23108 which is WRONG because the actual answer is 10000000000%100003 = 9.
1 followed by 10 zeroes overflows int? 
Oops, it does by one digit! My bad!
http://www.codechef.com/viewsolution/1917826 see this my solution in python once got Wrong Answer and next day i got AC with the same solution . (catalan number)