[PYTHON] 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. 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.

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

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.