SEAGM2 - Editorial

editorial
, , , , ,
2

i had the same logic…just messed up with the precision thing !!..nice problem though!!!

3

I used BigInteger in Java, but got WA on the large input set…
Unable to understand why…
Is there a way to look at 1 sample test from large input set ?

Ok I understand my mistake. I share it with you, because it’s very stupid and not easy to find.

I read the p[i][j] as doubles, then multiply them by 10000, then converting them to Integer. This is were the bug was. Because of the following:
if double x=0.0710
then x*10000=709.99999999 and when casting to Int, this gives 709…(!!!)
This is a lesson. Never cast a double to an int basically…

1 Like
4

I’ve a less complex solution for this problem:

http://www.codechef.com/viewsolution/7413020

I Changed the formula a bit, Now in the solution I don’t have to deal much with precision so it will work always :slight_smile:

7 Likes
5

exactly the same logic…just precision errors…

Also, the first test case was weak though, even my guess solution which i first applied for finding minimum of every row and printing the minimum of first row passed. This should not have happened…

Still a good question. Came to know about the importance of precision of numbers and how to take care of it.

6

I used the BigDecimal class in java and got it accepted. Here’s the link to my solution CodeChef: Practical coding for everyone .

7

I have used the BigDecimal class in java. Here is the link to my solution. CodeChef: Practical coding for everyone

8

The test cases were weak ; the following solution gets 100 points :

http://www.codechef.com/viewsolution/7474964

All I did was scale all the elements by 25.

3 Likes
9

Got AC with big integer calculation without any fast multiplication optimization. The only trick I used is when you divide big integer on another big integer the only precision you need is first 6 digits after decimal point. So it is enough to divide up to 9th digit and the stop dividing.

1 Like
10

This problem really pissed me off. I was very confident of my solution but I kept getting WA’s. I still don’t know the reason though. My maths is the same as author’s but my answer may be more precise because I am never rounding off (PYTH). I opened up a discussion for this. It will be helpful if someone provides any guidance.

11

I don’t understand why the author suggests a “fast multiplication method like Karatsuba or FFT” for multiplying bignums. All of the probabilities can be expressed as scalars from 0 ＜= n ＜= 1000000, so all you ever need to do is multiply by scalars which takes O(s) time where s is the size of the bignum. This is even faster than Karatsuba and FFT because we’re not multiplying bignums by bignums. Here’s my solution.

In this solution, I simply find the product of all of the probabilities by having one bignum called curProduct and repeatedly taking inputs as scalars (long longs) and then multiplying them into curProduct. Then, in the end, I take the first one and multiply it by 1000000 into sereja and add them all up into sum. I then use binary search to divide sereja by sum and output the resulting number with a decimal point. No Karatsuba or FFT necessary!

12

@amaneureka Nice idea, but the following test case should not work:

2 10000

0.0001 0.0001 … (5000 times) 0.9999 0.9999 0.9999 … (5000 times)

0.9999 0.9999 0.9999 … (5000 times) 0.0001 0.0001 … (5000 times)

13

@spagiarri Here :slight_smile:alt text

PS: After watching your comment (at 04:00AM) from mobile, Just to prove my code I booted laptop again :stuck_out_tongue:

I can give you brief explanation that why it worked, but its 4AM and I’m very tired so, sorry :slight_smile:

14

Why dies my solution passes the subtask 2 but now 1? In JAVA
Link : link text

15

@amaneureka: can you explain your logic?

1 Like
16

Please explain your solution

17

…I HAD TO USE MY OWN bignum LIBRARY IN C AND YOU JUST WALTZ IN AND SCALE THE ELEMENTS BY 25…(so depressed)

1 Like
18

How did your solution pass? It went over the time limit of 3 seconds!

19

Your solution is similar to my solution because we both multiplied by scalars instead of using a bignum multiplication algorithm. (I saw your solution here.)

20

Time limit for java is not 3 seconds. It is for C/C++, I guess. JAVA is slow.

21

Wow! this is a really good solution! He has just played around with the formula and calculated Ai / A1 on the fly without actually calculating the whole Ai first. Ai is the product of numbers in the ith row (probability that ith guy wins). The answer initially is A1 / (A1 + A2 + … + An). Divide both sides by A1 and you get 1 / (1 + A2/A1 + A3/A1 + … + An/A1). nice!

4 Likes