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

×

codechef question removal

0
1

how can i remove(delete) my question from forum...??

This question is marked "community wiki".

asked 27 Jun '15, 17:25

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

edited 26 Aug '15, 02:06


I read this problem and also the solution. This problem don't have weak test cases, but they'll pass using some hashing technique and some may not work
For long string , this solution is working as you are calculating fibo%(2^64-1), as in using first loop we are just putting this value in a long long variable and by default it balances overflow using mod 2^64 -1 and then we start from 1,1 and iterate till 6000 , (6000th fibo has more that 1000 digits) and then checking if after taking modulo we get same result as earlier. Thats it. there is probability of collision!

link

answered 27 Jun '15, 22:25

dracowane's gravatar image

6★dracowane
59316
accept rate: 48%

edited 28 Jun '15, 16:58

collision here means that you are hashing all the fibonacci numbers by 2^64-1 which may map two different values at the same place. Though you are not directly using hashing but When there is overflow then calculation is done automatic by taking modulo by the largest number that can fit in that data type.

link

answered 27 Jun '15, 22:40

apptica's gravatar image

5★apptica
949210
accept rate: 17%

@dracowane. I think it is unfair to blame the test cases just because of the hashing solution passed with modulus 2^64. Solutions with an extremely high probability to pass is obviously a correct solution for the contest's/problem's purpose. It is not possible for the problem author to prepare tests against a specific hashing technique/parameter as these are unknown to the author. Besides you can use multiple hashing with different parameters to increase the success rate of such hashing based solution. So IMO this should not be called "weak test cases".

link

answered 28 Jun '15, 05:26

yubowenok's gravatar image

6★yubowenok
465
accept rate: 50%

edited 28 Jun '15, 05:26

Hey, chill!, well i am sorry to blame test cases, but this solution, modulo 2^64-1 was a naive solution, some coders code it assuming that everything will fit in unsigned long long and it passed and some coders were struggling knowing that 1000 digit number can't be stored in unsigned long long and was thinking about something else! so i feel that cause of test cases, many suffered so i called them weak. well i'll edit my answers :)

(28 Jun '15, 16:57) dracowane6★
Answer is hidden as author is suspended. Click here to view.

answered 24 Aug '15, 15:46

devil12's gravatar image

0★devil12
(suspended)
accept rate: 100%

what is pest control services??

these links are no opening in pc???

(24 Aug '15, 17:34) rcsldav20175★

sorry for weak test case data...thanks for response....guys

link

answered 28 Jun '15, 20:11

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

one more solution , you can close your question too....

link

answered 26 Aug '15, 02:05

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

toggle preview
Preview

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:

×365
×161
×69
×14
×9

question asked: 27 Jun '15, 17:25

question was seen: 2,740 times

last updated: 26 Aug '15, 02:06