×

[closed] HandShake Problem BitFreak2013 NITA

 2 1 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? asked 10 Mar '13, 16:14 8.6k●19●48●98 accept rate: 9%

The question has been closed for the following reason "The question is answered, right answer was accepted" by bugkiller 16 Apr '13, 22:48

 2 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. answered 10 Mar '13, 20:55 201●2●8 accept rate: 33% @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. (10 Mar '13, 22:50) @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. (11 Mar '13, 15:15) 1 followed by 10 zeroes overflows int? :-O Oops, it does by one digit! My bad! (11 Mar '13, 17:37)
 3 test cases of the problem was wrong but after they corrected the test cases my same WA solution got AC today .. answered 10 Mar '13, 22:22 3.6k●13●35●55 accept rate: 10% 2 and apart from this for input 0 answer was 1.... (10 Mar '13, 22:27) @devanshug >> WTH, for input 0 answer 1? means there are zero persons and still 1 handshake was possible? (10 Mar '13, 22:51) @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. (10 Mar '13, 22:53) 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. (11 Mar '13, 03:30) 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) (11 Mar '13, 18:28) and same solution nothing difference http://www.codechef.com/viewsolution/1927259 Got Ac . (11 Mar '13, 18:37) @chandan11111 >> thats a real WTF situation! Anyways, congratulations for solving 10 / 10. (11 Mar '13, 23:03) showing 5 of 7 show all

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.7k111927
accept rate: 13%

@devanshug >> Thanks for the code man. Understood your logic. PS: I am thinking to learn Python since a long time.

(10 Mar '13, 22:56)
 0 @anton_lunyov >> then why was this, the very first submission of mine got WA! It was printing "1" for "0". http://www.codechef.com/viewplaintext/1921432 answered 11 Mar '13, 03:44 8.6k●19●48●98 accept rate: 9% Should I assume that there were n > 1000 in testcases then? Or would you mind telling some other bug in my code? (11 Mar '13, 03:46) 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. (11 Mar '13, 03:48) How can it get int overflow when I am maintaining %MOD at each step? I don't get this. :/ (11 Mar '13, 03:50) Do (long long)(catalan[j]) * catalan[i - j] (11 Mar '13, 03:57) @bugkiller : Now, you might have idea why you were wrong? Exponential progress in you. (25 May '13, 22:39) @bit_cracker007 >> I din't get you. Please elaborate. (25 May '13, 23:47) I mean did you get where you went wrong? (26 May '13, 00:10) Yes this is quite an old question. What does this mean "Exponential progress in you."? (26 May '13, 00:19) In simple words : " You are a hard working guy. ". (26 May '13, 00:24) 1 Oh thanks. I was wondering how that comment was related to this question :D (26 May '13, 00:28) It happens :D (26 May '13, 00:46) showing 5 of 11 show all

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×37
×12

question asked: 10 Mar '13, 16:14

question was seen: 1,729 times

last updated: 26 May '13, 00:46