Help me in solving CHFHEIST problem

help
,
1

My issue

Problem Link: Bella ciao Practice Problem in - CodeChef

For some reason my code breaks with a weird high number test case, but I can’t figure out why, I think it maybe has something to do with python or division or something? My best explanation of my solution is:

For example input:
17 3 1 1
D = 17
d = 3
P = 1
Q = 1

baseSum = 17 * 1

cumulativeSum = Q * (17-3) + Q*(17-6) +Q*(17-9) + Q*(17-12) + Q*(17-15)
cumulativeSum = Q * ((D//d) * 17 - 3 - 6 - 9 - 12 - 15)
cumulativeSum = Q * ((D//d) * 17 + (D//d) * (-3 - 15)/2)

This is above is my formula, this is the best explanation of the image and my code I can give.

Custom failed input:
1
1000000 1 343 860939

My Output:
430469069873499968

Correct output:
430469069873500000

ARR_HALVES
ARR_HALVES3000×4000 285 KB

My code

# https://www.codechef.com/practice/course/2-star-difficulty-problems/DIFF1500/problems/CHFHEIST - 1410, start: 20:26, end:

import math


def solve():

    D, d, P, Q = map(int, input().split(" "))
    sum = D * P

    numOfValid_d = D//d

    sum += (numOfValid_d * D - ((d + d*numOfValid_d) / 2) * numOfValid_d) * Q

    print(int(sum))


tests = int(input())


for i in range(tests):
    solve()

Learning course: 1400 to 1600 difficulty problems

2

Short answers: floats are evil.

Long answer:

the problem is in this line of code:

sum += (numOfValid_d * D - ((d + d*numOfValid_d) / 2) * numOfValid_d) * Q

To be more precise, the problem is that floating-point division by 2 converts this number to a float. And then when you multiply two large numbers, one of which is float, you’ll get the wrong answer.

One solution is to use slower, but more precise decimal:

from decimal import Decimal
# ...
tmp = Decimal.from_float(numOfValid_d * D - ((d + d*numOfValid_d) / 2) * numOfValid_d)
Q = Decimal.from_float(Q)
sum += tmp * Q

But this isn’t ideal because float is still there. Luckily, in this case, float can be avoided completely:

sum += (numOfValid_d * D - ((d + d*numOfValid_d) * numOfValid_d // 2)) * Q

Good luck with your newly created fear of floats :slight_smile:

1 Like
3

It works, awesome, thanks!

1 Like