[PYTHON] AtCoder Beginner Contest 177 Problem C I tried to find out why it was wrong

Introduction

I was desperately addicted to Problem C of Contest177 held on August 29, 2020, so I investigated it.

problem

https://atcoder.jp/contests/abc177/tasks/abc177_c

Thoughts

When I calculated it properly, I thought it would probably be TLE. But with a little ingenuity, it seems quite so.

Ponder for a while.

We came to the conclusion that the sum we wanted was {(A1 + A2 +… + An) ^ 2- (A1 ^ 2 + A2 ^ 2 +… + An ^ 2)} ÷ 2, and coded it. Completed in about 10 minutes.

c.py

n = int(input())
l = input()
a = l.split(' ')

tmp = 0
tmp2 = 0

for i in range(n):
    tmp += int(a[i])

for i in range(n):
    tmp2 += int(a[i])*int(a[i])

print(int((tmp*tmp-tmp2)/2)%1000000007)

Alright, I'm in good shape today! You may be able to ask 4 questions! As soon as I thought, the judgment of impermanence was made. It freezes here, and the day ends with two questions.

why

After the contest is over, see the commentary. do not know. why? Both the cumulative sum and this calculation method should be mathematically the same value. I wasn't convinced on Saturday anyway, so I slept, calmed down, I wrote a cumulative Japanese version on Sunday and submitted it.

c_.py

n = int(input())
l = input()
a = l.split(' ')

tmp = 0
total2 = 0

for i in range(n):
    tmp += int(a[i])

for i in range(n):
    total2 += int(a[i])*(tmp-int(a[i]))
    tmp -= int(a[i])

print(total2%1000000007)

** Yeah yeah yeah yeah yeah yeah **

why? Why are you doing the same thing, one is WA and the other is AC? ?? ??

I tried various things

First, I checked how large int numbers can be handled by python. As a result, in python ver3, you can use as many values as the memory allows. Then, what is strange is ÷ 2? I'm sure something strange is happening when the numbers are big.

I entered 10 numbers of appropriate size and displayed the numbers before dividing by 2 and the numbers when dividing by 2.

input_data1

10
1234567 2345678 3456789 4567890 5678901 6789012 7890123 8901234 9012345 1111111

2257615544087530
1128807772043765

This looks okay. Let's make it a little bigger.

input_data2

10
12345678 23456789 34567890 45678901 56789012 67890123 78901234 89012345 90123456 11111111

225761590208477104
112880795104238560

Looking at the 1's place, it is 4 before dividing by 2, so what is divided by 2 should be 2 or 7. Yet 0. So, if you divide a big number by 2, something strange seems to happen.

Why doesn't it break at 2

When I googled "python division is funny", I found the following article.

The result of huge floating point calculation was strange in Python3, so I tried to find out the reason https://paiza.hatenablog.com/entry/2017/08/01/Python3%E3%81%A7%E5%B7%A8%E5%A4%A7%E3%81%AA%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E8%A8%88%E7%AE%97%E3%81%AE%E7%B5%90%E6%9E%9C%E3%81%8C%E5%A4%89%E3%81%A0%E3%81%A3%E3%81%9F%E3%81%AE%E3%81%A7%E7%90%86

Well, I understand ... but I still don't understand. .. .. However, the big numbers mean that strange things can happen when you divide. I've become smarter. Thank you very much.

... Ah, regrettable.