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. image.png 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)

image.png

** 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.

Recommended Posts

AtCoder Beginner Contest 177 Problem C I tried to find out why it was wrong
AtCoder Beginner Contest # 002 C Problem
AtCoder Beginner Contest 174 C Problem (Python)
When I tried the AtCoder Beginner Contest, it was a terrible result, so I look back
[Professional competition practice] I tried AtCoder Beginner Contest 171
AtCoder Beginner Contest 176 C Problem "Step" Explanation (Python3, C ++, Java)
A beginner tried coloring line art with chainer. I was able to do it.
AtCoder Regular Contest # 002 C Problem
AtCoder Beginner Contest 166 A Explanation of Problem "A? C" (Python3, C ++, Java)
I tried to find out the outline about Big Gorilla
AtCoder Beginner Contest 174 B Problem "Distance" Explanation (C ++, Python, Java)
AtCoder Beginner Contest 177 B Problem "Substring" Explanation (Python3, C ++, Java)
[Professional competition] I tried At Coder Beginner Contest 175 (A ~ C)
AtCoder Beginner Contest 167 A Problem "Registration" Explanation (Python3, C ++, Java)
AtCoder Beginner Contest 169 B Problem "Multiplication 2" Explanation (Python3, C ++, Java)
AtCoder Beginner Contest 170 A Problem "Five Variables" Explanation (C ++, Python, Java)
AtCoder Beginner Contest 169 A Explanation of Problem "Multiplication 1" (Python3, C ++, Java)
AtCoder Beginner Contest 176 A Explanation of problem "Takoyaki" (Python3, C ++, Java)
AtCoder Beginner Contest 175 B Problem "Making Triangle" Explanation (C ++, Python3, Java)
I tried to find out if ReDoS is possible with Python
AtCoder Beginner Contest 175 A Problem "Rainy Season" Explanation (C ++, Python3, Java)
AtCoder Beginner Contest 176 B Problem "Multiple of 9" Explanation (Python3, C ++, Java)
python beginners tried to find out
AtCoder Beginner Contest 174 A Problem "Air Conditioner" Explanation (C ++, Python, Java)
AtCoder Beginner Contest 177 A Problem "Don't be late" Explanation (Python3, C ++, Java)
AtCoder Beginner Contest 173 B Problem "Judge Status Summary" Explanation (Python3, C ++, Java)
When I tried to run Python, it was skipped to the Microsoft Store
AtCoder Beginner Contest 170 B Problem "Crane and Turtle" Explanation (Python3, C ++, Java)
AtCoder Beginner Contest 177 C Problem "Sum of product of pairs" Explanation (Python3, C ++, Java)
I tried to find out what I can do because slicing is convenient
AtCoder Beginner Contest 165 A Problem "We Love Golf" Explanation (Python3, C ++, Java)
AtCoder Beginner Contest 167 B Problem "Easy Linear Programming" Explanation (Python3, C ++, Java)
Atcoder Beginner Contest A, B Input summary Python that tends to be a problem
A programming beginner tried to find out the execution time of sorting etc.
AtCoder AGC 041 C --I was addicted to the full search of Domino Quality
[I'm an IT beginner] I tried my best to implement Linux on Windows
[Introduction to json] No, I was addicted to it. .. .. ♬
I tried to find 100 million digits of pi
I tried to implement the traveling salesman problem
I tried to find out how to streamline the work flow with Excel x Python ②
I tried to find out how to streamline the work flow with Excel x Python ④
I tried to make the phone ring when it was posted at the IoT post
I tried to find out how to streamline the work flow with Excel x Python ⑤
[Rails] v1.0 came out on google-cloud-vision of gem, so I tried to support it
I tried to find out how to streamline the work flow with Excel x Python ①
I tried to find out what would happen if I converted NaN or INF to int
A Python beginner made a chat bot, so I tried to summarize how to make it.
I tried to find out how to streamline the work flow with Excel x Python ③
AtCoder Beginner Contest 177
AtCoder Beginner Contest 172
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder Beginner Contest 5 questions to fill in tea diff
Brown coder tried to solve Panasonic Contest 2020A ~ C
CTF beginner tried to build a problem server (web) [Problem]
I tried to solve the problem with Python Vol.1
I was able to repeat it in Python: lambda
I tried to find an alternating series with tensorflow
When I tried to install PIL and matplotlib in a virtualenv environment, I was addicted to it.
Since there was a doppelganger, I tried to distinguish it with artificial intelligence (laugh) (Part 2)
There was a doppelganger, so I tried to distinguish it with artificial intelligence (laughs) (Part 1)