4 methods to count the number of occurrences of integers in a certain interval (including imos method) [Python implementation]

background

When I was solving the ABC127 C problem of Competitive Programming AtCoder, I thought about how many intersections there are in a set of consecutive integers. I found it very interesting because there were various solutions to the problem, so I decided to write an article. The problem can be found at the link below. We also explain the ABC127 C problem, so be careful of spoilers.

AtCoder Beginner Contest 127 C - Prison

C - Prison Let's start with the problem statement.

スクリーンショット 2020-07-31 2.49.32.png

Write an outline of the problem statement. There are M gates and you need an ID card to open them. There are N ID cards, numbered from 1 to N. Some gates can only open ID cards with numbers above Li and below Ri. It is a matter of counting how many ID cards exist that can open all gates.

First, let's consider an input example. There are four ID cards, each numbered 1, 2, 3, and 4. There are 3 gates, the 1st gate can be opened with 1, 2 and 3 ID cards and the 2nd gate can be opened with 2, 3 and 4 ID cards. You can see that only 2 and 3 ID cards can open all gates. In other words, I wanted to take the intersection of ID cards that can open all the gates.

Considering a set using set Policy 1

In conclusion, this method took a lot of calculation time and became TLE and did not pass.

As a policy, the minimum value and maximum value information of the ID card number that can open one gate is input in one line, so create the number from the minimum value to the maximum value in range and make it a set type Converted to. The operation was performed for all gates, and the intersection was taken for all sets.

Consider the cause of TLE. Since the maximum number of ID cards that can open one gate is $ {10 ^ {5}} $, $ {10 ^ {5}} $ data is converted to set each time, and M (maximum) You can see that doing for the gate of $ {10 ^ {5}} $) is very computationally intensive. Since the work is done M times, I estimated that it would cost about $ {O (NM)} $ in the worst case. Due to the constraint, the amount of calculation is $ {O (10 ^ {10})} $ and it becomes TLE.

I will put the python code for reference.

python


n, m = map(int, input().split())
line = set(range(1, n + 1))

for i in range(m):
    l, r = map(int, input().split())
    line &= set(range(l, r + 1))

print(len(line))

Revised Policy 1 Policy 2

When considering a set, it may be effective in situations where ID cards are not continuous, but in this case the amount of calculation was large and it was not effective. You can see that the amount of calculation should be at most $ {O (N)} $.

If you think about the policy again, the data is continuous, so if you save the largest ID card number among the minimum ID card Li and the minimum number among the maximum Ri, the number between them will be the same. I thought it was the number.

I realized that the background to this policy came up by arranging the numbers on the ID card that opens the gate for each gate. In this case, ID cards are entered continuously, so this method is fine. Ri --Li + Can be opened with one ID card.

However, as a point to note, if the range of ID cards does not overlap, the value of Ri --Li + 1 will be negative, so if it is negative, there is no ID card that satisfies the condition, so implement to output 0. Must be.

python


n, m = map(int, input().split())
l_max = 1
r_min = 10 ** 5

for i in range(m):
    l, r = map(int, input().split())
    l_max = max(l, l_max)
    r_min = min(r, r_min)

print(max(0, r_min - l_max + 1))

I was able to get AC with this code. I'm satisfied with this if I just take AC, but when I was watching the commentary broadcast, there was a comment saying that I solved it with the imos method, so I got interested and reconsidered another solution.

Policy 3 before entering the imos law

Before working on the imos method, I would like to consider a method that is similar to the imos method. To conclude first, I think that this method requires a large amount of calculation and results in TLE. Our imos method solves this problem.

Let's organize our thoughts. Considering the number of gates that ID cards can open, the number of ID cards that can open all gates is M because any gate can be opened. If it is less than M, some gates cannot be opened. In other words, you can count the number of ID cards that can open M gates.

Then I would like to implement it. First, prepare an array to store how many gates the ID card number can open. I prepared an array called cardid_2_num_map. The number of elements is one more than the maximum value of the ID card. The intention is that the number entered is 1 or more and N or less, so I tried to reduce the error by using it as it is when specifying the index. The 0th array is never used.

When considering an array whose card ID number is index from 0 to $ {10 ^ 5} $ and whose contents hold the number of gates that the ID card can open, [0, 1, 2, 2, 1 , 0, ...] is the array you want to get in the case of the input example.

Considering that for is duplicated, it seems that the amount of calculation is large. The maximum order of computational complexity is $ {O (NM)} $, and TLE is the same as when considering the intersection. The imos method solves this problem. We will discuss it in the next section.

python


n, m = map(int, input().split())
cardid_2_num_map = [0] * (10**5 + 1)

for i in range(m):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        cardid_2_num_map[j] += 1

max_sum_num = max(cardid_2_num_map)
count_max_card = cardid_2_num_map.count(max_sum_num)

if max_sum_num == m:
    print(count_max_card)
else:
    print(0)

imos method, the leading role of this time, policy 4

I will post the article that I used as a reference.

Imos laboratory-imos laboratory The imos method is an algorithm that succeeds in reducing the amount of calculation by using the cumulative sum when counting the number of occurrences of consecutive numbers and combining the processes that have been counted each time into one.

Let's return to the above problem and think about it. I counted the number of ID cards that could open the gate and updated the values in the array. The maximum order of computational complexity is $ {O (NM)} $, which is TLE. It seems that it can be solved if the order can be suppressed to about $ {O (M)} $.

So, if you go back to the input example, there are four ID cards, which are numbered 1, 2, 3, and 4, respectively. There are 3 gates, the 1st gate can be opened with 1, 2 and 3 ID cards and the 2nd gate can be opened with 2, 3 and 4 ID cards.

Similar to policy 3, the card ID number is 0, 1, 2, 3, 4, ..., $ {10 ^ 5} $ in the index, and the contents of the array are the number that the ID card can open the gate. When considering the retained array, [0, 1, 2, 2, 1, 0, ...] is the array you want to obtain in the case of the input example. The 0th index is not used because the card ID indicates 0. The imos method is used to obtain such an array.

First, initialize the array with $ {10 ^ 5 + 2} $ elements and a value of 0. The intention of +2 will be explained later. The first gate can be opened with 1, 2 and 3 cards, so index number 1 is +1 and index number 4 is -1. [0, 1, 0, 0, -1, 0, ..., 0] Similarly, the second gate can be opened with 2, 3 and 4 ID cards, so index number 2 is +1 and index number 5 is -1. [0, 1, 1, 0, -1, -1, ..., 0] Since -1 is operated for the index of +1 at the right end of the ID card, the number of elements in the array is added by 1 to $ {10 ^ 5} $ and +2 (+1 was done to match the input with the index number). ).

Next, the cumulative sum of this array is taken from index number 0 to the end. A[i + 1] = A[i] + A[i + 1] to hold. As a result, the desired array [0, 1, 2, 2, 1, 0, ...] can be obtained as in policy 3.

Then, if the maximum value of the array is equal to the number of gates, there is an ID card that can open all the gates, and the number of ID cards with the maximum value is counted. The maximum order of computational complexity was about $ {O (M)} $, and we were able to AC.

python


n, m = map(int, input().split())
cardid_2_num_map = [0] * (10**5 + 2)

for i in range(m):
    l, r = map(int, input().split())
    cardid_2_num_map[l] += 1
    cardid_2_num_map[r + 1] -= 1

for i in range(1, n + 1):
    cardid_2_num_map[i] += cardid_2_num_map[i - 1]

max_sum_num = max(cardid_2_num_map)
count_max_card = cardid_2_num_map.count(max_sum_num)

if max_sum_num == m:
    print(count_max_card)
else:
    print(0)

Consideration

By adding +1 to the index at the left end of the range you want to count and -1 to the index at the right end +1 it is possible to add +1 only from the left end to the right end at the stage of finally taking the cumulative sum, and for all areas. You can count the number of appearances at one time.

x <Do nothing in the leftmost area Left end <= x <= Right end area is incremented by +1 Since the area of the right end <x does nothing

You are able to perform the intended enumeration.

This way of thinking can be applied to multiple dimensions and the amount of calculation can be reduced, so I found it very interesting. The illustrations in the article I referred to were very easy to understand. That's all.

Recommended Posts

4 methods to count the number of occurrences of integers in a certain interval (including imos method) [Python implementation]
How to count the number of occurrences of each element in the list in Python with weight
How to count the number of elements in Django and output to a template
How to get the number of digits in Python
A reminder about the implementation of recommendations in Python
How to identify the element with the smallest number of characters in a Python list?
A simple Python implementation of the k-nearest neighbor method (k-NN)
How to use the __call__ method in a Python class
"A book to train programming skills to fight in the world" Python code answer example --1.2 Count the number of the same characters
Get the number of specific elements in a python list
[Homology] Count the number of holes in data with Python
[Python] Programming to find the number of a in a character string that repeats a specified number of times.
How to quickly count the frequency of appearance of characters from a character string in Python?
Count the number of Thai and Arabic characters well in Python
How to determine the existence of a selenium element in Python
How to check the memory size of a variable in Python
How to check the memory size of a dictionary in Python
A function that measures the processing time of a method in python
Get the number of readers of a treatise on Mendeley in Python
Put the process to sleep for a certain period of time (seconds) or more in Python
Count / verify the number of method calls.
[Python] A program that calculates the number of socks to be paired
[Python] How to put any number of standard inputs in a list
Various methods to numerically create the inverse function of a certain function Introduction
Check the in-memory bytes of a floating point number float in Python
I made a program to check the size of a file in Python
Count the number of times two values appear in a Python 3 iterator type element at the same time
Various ways to read the last line of a csv file in Python
How to pass the execution result of a shell command in a list in Python
Output the number of CPU cores in Python
Set the number of elements in a NumPy one-dimensional array to a power of 2 (0 padded)
Get the caller of a function in Python
To dynamically replace the next method in python
Find the number of days in a month
Visualize the timeline of the number of issues on GitHub assigned to you in Python
Build a python environment to learn the theory and implementation of deep learning
Use twitter API to get the number of tweets related to a certain keyword
Output in the form of a python array
How to get a list of files in the same directory with python
Various methods to numerically create the inverse function of a certain function Part 1 Polynomial regression
[Python] A program that finds the shortest number of steps in a game that crosses clouds
How to check in Python if one of the elements of a list is in another list
[Python] Representing the number of complaints from life insurance companies in a bar graph
Find a guideline for the number of processes / threads to set in the application server
A story about trying to introduce Linter in the middle of a Python (Flask) project
Check if the string is a number in python
[Python] A program that counts the number of valleys
Count the number of parameters in the deep learning model
A python implementation of the Bayesian linear regression class
Get the size (number of elements) of UnionFind in Python
[Python] Created a method to convert radix in 1 second
To do the equivalent of Ruby's ObjectSpace._id2ref in Python
Python Note: The mystery of assigning a variable to a variable
Let's see how to count the number of elements in an array in some languages [Go, JavaScript, PHP, Python, Ruby, Swift]
Get the value of a specific key up to the specified index in the dictionary list in Python
[Python] How to delete rows and columns in a table (list of drop method options)
Understand the metropolitan hasting method (one of the methods in Markov chain Monte Carlo method) with implementation
[OCI] Python script to get the IP address of a compute instance in Cloud Shell
[Super easy! ] How to display the contents of dictionaries and lists including Japanese in Python
What seems to be a template of the standard input part of the competition pro in python3
I tried to create a Python script to get the value of a cell in Microsoft Excel