Google Code Jam Round 1-B 2018 Rounding Error Problem WA

general
,
1

Solution : https://ideone.com/3ZEbao

Problem : https://codejam.withgoogle.com/2018/challenges/0000000000007764/dashboard

My approach was simple if language was rounded up simply use rounded up value else store them and then for users that did not respond I processed each user separately. Got WA and can’t figure out what is error in code.

P.S.: WA because I was using set, changed it to vector passed first two cases but failed last case. Link: https://ideone.com/ZvEAKP

2

Looks like, you have discarded the value of (Ci * 100) % n. You have rounded of (Ci * 100) / n, ignoring any exceeding fraction, and then distributed the remaining number of people.

For example, try this test case:

1
14 4
3 3 3 3

My solution gives 100%, but your one gives 99%

My Solution: https://repl.it/repls/NiceAccurateScientist

1 Like
3

What is value for total participants and number of languages for which response has been recorded in this test case ?

4

For this test case correct answer is 101%, for val=1 it will give only 3% and 14 gives 45%, 4 gives 13%, 3 gives 10% so in total it gives 101% which is the correct answer.

5

I think he is saying
This

1

14 4

3 3 3 3

1 Like
6

Exactly… Extremely sorry for the bad format.

Edited. :slight_smile:

7

Thanks, it was because I used set and it does not store duplicates. I changed it to vector and it passed first two test cases but not the last one, I even checked for overflow. Link: https://ideone.com/ZvEAKP

8

@vijju123 Can you look at my code for error. Only last test case is failing now.

9

Okay, checking it.

1 Like
10

@rj25 - Can you first try changing all >=0.5 to >=0.4999999999 ? If that doesnt work, please comment the code so I can exactly get what you want. Your algo seems correct to me and I suspect it can be an implementation error.

11

Surprisingly it gave correct answer. I don’t understand why ? In question it is given 12.499 will be made 12 and its has to be 12.5 to be converted to 13. I changed >=0.5 to >=0.499999999. Can anyone explain this ?@vijju123

12

Since ancient times, the concept of witchcraft and black magic was used to describe unexplainable phenomenon. It was said that witches (male(?) and female) were able to manipulate forces of nature to perform their supernatural deeds. All the witches, however, had one common rule.

Never trust a floating point

Long story short, its nothing but rounding errors. The ideal fix was abs(value-(int) value)<=0.000001 . I just asked you to keep a gap of delta {10}^{-6}- though in a bit lenient fashion :stuck_out_tongue:

1 Like
13

Great explanation. Thanks