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.

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.