AtCoder ABC155 Problem D Pairs Review Note 1

Overview

A note about AtCoder ABC155 Problem D Pairs.

Background

I couldn't participate in AtCoder ABC155 held on February 16, 2020 because I was busy with work, but due to my dedication [Problem D](https: //) Atcoder.jp/contests/abc155/tasks/abc155_d) I couldn't think of a solution. Looking at the commentary article, I understood that I should count by the dichotomy method. I tried coding in Python myself, but I couldn't get out of TLE by myself.

From Previous comparison, I guessed that I could probably go with C ++, but

--Is it possible to pass it with Python? ――What is sweet about your code when you pass it?

I was curious about such things, so I looked it up.

Survey results

Is it possible to pass it with Python?

Conclusion: Can pass (but is it a little difficult?)

When I searched for a person who took AC with Python3, the result was like this. ABC155D-python-AC-01m.png Only two people passed through during the contest time, maspy was yellow, and nohtaray was blue but yellow (color is as of March 20, 2020). The execution time is about 1100msec.

Considering that only two people can pass in time and that the two people who pass through are yellow and blue, it seems to be a tough problem to pass by my ability.

I also tried it with PyPy, which showed a significant improvement in Previous comparison (Submission # 10928876. abc155 / submissions / 10928876)) was not very effective this time and TLE could not be resolved.

What's so sweet about your code when you pass it?

Execution speed comparison

First, I compared the execution times. maspy's Submission # 10152895 nohtaray's Submission # 10155744 I downloaded it to my server and wrote it myself Program Submission # 11068460 In addition, we compared the execution time when each program was executed for four test cases. The following results (time command measurement of elapsed time. Unit is seconds). Since the execution results themselves match, the program itself seems to be working correctly.

program test01 test02 test03 test04
My program[Submission#11068460] 0.045 0.039 9.576 9.576
nohtaray's[Submission#10155744] 0.303 0.288 1.140 1.119
maspy's[Submission#10152895] 0.275 0.312 1.097 1.045

The size of the test case is as follows. Ai was generated by random numbers.

program test01 test02 test03 test04
N 20 20 200000 200000
Number of positive numbers 10 10 100000 10000
Number of zero 1 1 1 1
Negative number 9 9 99999 99999
K 150 50 1500000000 500000000

The results show that my program is faster when N is small, but when N is large The programs of maspy and nohtaray are about 10 times faster. .. ..

Code comparison

So what's the difference? .. .. Let's take a look at the programs of maspy and nohtaray to find out. It turns out that the two code commonly use a feature called numpy searchsorted. An array is also used for the second argument. It was expected that this would probably be much faster than my hand-held function. Is there such a function? .. .. .. The code is short, thanks in part to using this.

Finally

Memo 1 is over until it turns out that the use of numpy's search sorted is "miso".

I found out that I didn't have enough knowledge about numpy to compete with Python. If you feel like writing numpy searchsorted or if you could write code that doesn't TLE more easily in C ++, I'll investigate and organize it.

Recommended Posts

AtCoder ABC155 Problem D Pairs Review Note 1
AtCoder ABC 182 Python (A ~ D)
AtCoder ABC151 Problem D Speed comparison in C ++ / Python / PyPy
AtCoder ABC156 Problem D Bouquet mod calculation and permutations, etc.
AtCoder ABC176
AtCoder ABC177
Atcoder ABC60 D --Simple Knapsack Separate Solution
Python beginner Atcoder memo @ KEYENCE 2020, ABC problem
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
AtCoder ABC 175 Python
Review of atcoder ABC158, up to question E (Python)
AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 181 Note
AtCoder Grand Contest 041 Review
AtCoder Regular Contest 105 Review
AtCoder Past Question Review (12 / 6,7)
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Regular Contest 106 Note
AtCoder Beginner Contest 182 Note
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 177 Review
AtCoder Regular Contest 105 Note
AtCoder Grand Contest 045 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Beginner Contest 183 Note
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 184 Note
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 165 Review
A person who wants to clear the D problem with ABC of AtCoder tried to scratch
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 188 Note
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solving with Ruby and Python AtCoder ABC138 D Adjacency list