Need help identifying exact different between two similar solutions for CHFING

For a problem on Codechef - https://www.codechef.com/problems/CHFING,
I submitted two programs that differs only on a part where a division occurs.

1st Solution https://www.codechef.com/viewsolution/24978403

import math
MOD = 1000000007
test = int(input())
for _ in range(test):
    n,k = map(int, input().split())
    first=k-1;
    diff=n-1;
    t = (first+diff)//(diff)
    y=(2*(first)-(t-1)*(diff))
    ans = (y*t)//2;
    ans = ans%MOD
    print(ans)

2nd Solution https://www.codechef.com/viewsolution/24978385

import math
MOD = 1000000007
test = int(input())
for _ in range(test):
    n,k = map(int, input().split())
    first=k-1;
    diff=n-1;
    t = int((first+diff)/(diff))
    y=(2*(first)-(t-1)*(diff))
    ans = (y*t)//2;
    ans = ans%MOD
    print(ans)

solution #1 passed all test cases but solution #2 fails for one test case.

The only difference is on line #8 where t is calculated as t = (first+diff)//(diff) in the 1st solution and t = int((first+diff)/(diff)) in the 2nd solution.

Note that inputs are always integer, so variables first and diff are ints. And the code is in Python 3.6.

So does python returns different for x//y and int(x/y)? Or am I missing something else? Can someone kindly point me out why the second solution gives WA?

Edit: I came to know that these two are different for negative numbers. (https://stackoverflow.com/questions/56816677/does-x-y-and-intx-y-return-same-results-in-python). But input for this problem is non-negative and hence the variables first and diff also.

Edit #2: https://stackoverflow.com/a/56569910/7845063
the division operator behaves abnormally generally for numbers greater than 10 ^ 17.

x = 10000000000000000000006
if x / 2 == x // 2:
    print("Hello")
else:
    print("World")

For the above code, World will be printed and not Hello. This is because 10000000000000000000006 / 2 will return 5e + 21, but 10000000000000000000006 // 2 will return the correct answer 5000000000000000000003. Even int(10000000000000000000006 / 2) will return 5000000000000000000000, which is incorrect.

floor divide gives lower value and int(x/y) gives round off value

and wont they be same in this case?

Tried to compare outputs from both approaches upto allowed limit. But answer is same for the iterations.

import math
MOD = 1000000007
#test = int(input())
#for _ in range(test):
for n in range(2,1000):
for k in range(1,1000):
    #n,k = map(int, input().split())
    first=k-1;
    diff=n-1
    
    
    t = (first+diff)//(diff)
    y=(2*(first)-(t-1)*(diff))
    ans = (y*t)//2;
    ans = ans%MOD
    #print(ans)

    t2 = int((first+diff)/(diff))
    y2=(2*(first)-(t2-1)*(diff))
    ans2 = (y2*t2)//2;
    ans2 = ans2%MOD
    #print(ans2)
    
    if ans == ans2:
        continue
    else:
        print(n,k)

Yeah,
i checked it too!
Not exactly sure, but surely there must be a test case where the answer differs

Try this TC:
1
12 1000000000000000000

1 Like

wow, result differs for this TC. can you please explain why is this so?

Sorry, I don’t know the reason for this :pensive:
If you don’t get the answer here you can post it on stackoverflow.

Before posting here, i posted it SO, and it was marked as duplicate. Will edit that and will see if gets any answers. Thanks.

1 Like

from the SO link in edit2:
the division operator behaves abnormally generally for numbers greater than 10 ^ 17

Now i see the reason for the WA with the submission having ‘/’ operator. Cost me 80 points in june challenge. Thank you for your valuable input. May I ask how did you identify this exceptional case?

1 Like

I thought the reason for this abnormal behavior was that casting to int and using // operator take different number of significant digits for rounding off the number. So took a pair that generates a large number with recurring decimal representation as output. The assumption turned out to be wrong as in that case the numbers should only differ by 1. But a pair generating different output was achieved.
Was an interesting exception.

2 Likes

yeah i was saying this as well
there’s a difference in rounding off
floor division and typecasting has difference
i just couldn’t find exact solution
when i was doing this same problem i had a lot of WA because of it!