You are not logged in. Please login at www.codechef.com to post your questions!

×

[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

bugkiller's gravatar image

3★bugkiller
8.6k194898
accept rate: 9%

closed 16 Apr '13, 22:48

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


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.

link

answered 10 Mar '13, 20:55

shahid_khan's gravatar image

5★shahid_khan
20128
accept rate: 33%

edited 10 Mar '13, 20:55

@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) bugkiller3★

@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) shahid_khan5★

1 followed by 10 zeroes overflows int? :-O Oops, it does by one digit! My bad!

(11 Mar '13, 17:37) bugkiller3★

test cases of the problem was wrong but after they corrected the test cases my same WA solution got AC today ..

link

answered 10 Mar '13, 22:22

chandan11111's gravatar image

3★chandan11111
3.6k133555
accept rate: 10%

2

and apart from this for input 0 answer was 1....

(10 Mar '13, 22:27) devanshug4★

@devanshug >> WTH, for input 0 answer 1? means there are zero persons and still 1 handshake was possible?

(10 Mar '13, 22:51) bugkiller3★

@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) bugkiller3★

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) anton_lunyov ♦6★

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) chandan111113★

and same solution nothing difference http://www.codechef.com/viewsolution/1927259 Got Ac .

(11 Mar '13, 18:37) chandan111113★

@chandan11111 >> thats a real WTF situation! Anyways, congratulations for solving 10 / 10.

(11 Mar '13, 23:03) bugkiller3★
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]
link

answered 10 Mar '13, 18:38

devanshug's gravatar image

4★devanshug
2.7k111927
accept rate: 13%

edited 10 Mar '13, 18:40

@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) bugkiller3★

@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

link

answered 11 Mar '13, 03:44

bugkiller's gravatar image

3★bugkiller
8.6k194898
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) bugkiller3★

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) anton_lunyov ♦6★

How can it get int overflow when I am maintaining %MOD at each step? I don't get this. :/

(11 Mar '13, 03:50) bugkiller3★

Do (long long)(catalan[j]) * catalan[i - j]

(11 Mar '13, 03:57) anton_lunyov ♦6★

@bugkiller : Now, you might have idea why you were wrong? Exponential progress in you.

(25 May '13, 22:39) bit_cracker0073★

@bit_cracker007 >> I din't get you. Please elaborate.

(25 May '13, 23:47) bugkiller3★

I mean did you get where you went wrong?

(26 May '13, 00:10) bit_cracker0073★

Yes this is quite an old question. What does this mean "Exponential progress in you."?

(26 May '13, 00:19) bugkiller3★

In simple words : " You are a hard working guy. ".

(26 May '13, 00:24) bit_cracker0073★
1

Oh thanks. I was wondering how that comment was related to this question :D

(26 May '13, 00:28) bugkiller3★

It happens :D

(26 May '13, 00:46) bit_cracker0073★
showing 5 of 11 show all

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,700 times

last updated: 26 May '13, 00:46