A DP problem

What is the problem?

Jimmy (xiaoke) Shen

·

Follow

2 min read

·

Apr 26, 2020

7

Listen

Share

Today I solved a DP problem. We have n elements,

the Edge of [a, b] can not be put into the same group where a, b is in zip(allergic, poisonous). The question is what is the number of continuous range that we can have to make sure all elements in this range are valid. The range can not be empty, however, only one element is allowed.

For example, if we have n = 5

allergic is [1,2]

poisonous is [3, 5]

The valid ranges will be

• [1]
• [1,2], [2]
• [2,3],[3]
• [2,3,4],[3,4],[4]
• [3,4,5],[4,5],[5]

Problem size

n can be 10⁵. It means O(n²) algorithm will get TLE.

A quick idea about how to solve it

After reading this example, we will be clear that the left-most bolded number is critical to the final answer. If we have that number, we can use the following simple way to solve the problem.

for i in range(1, n+1):
    res += i - left_most_number in this row +1

How to find the leftmost number?

Firstly, we collect all the information given the node i, what is the largest number of a node on its left side that it can not stay together with.

In the example, we will have the results below after we process all the information provided in allergic, poisonous. -1 means no node will confilct with this node.

• i= 1, largest number of a node on its left side it can not stay with = -1
• i = 2, largest number of a node on its left side it can not stay with = -1
• i = 3, largest number of a node on its left side it can not stay with= 1
• i = 4,largest number of a node on its left side it can not stay with= -1
• i = 5, largest number of a node on its left side it can not stay with= 2

The code related to this part is

    d = collections.defaultdict(lambda :-1)
    for a,b in zip(allergic, poisonous):
        a,b = sorted([a,b])
        d[b] = max(d[b],a)

Then, I thought I was done by “the largest number of a node on its left side it can not stay with +1”, we can get the leftmost number we need.

However, I am wrong.

For example, when i=4, we should get 2. This can be easily fixed by using the following transitions:

Leftmost number of i = max(leftmost number of i, leftmost number of i-1)

The code corresponding to this part is

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

The full code

#time complexity: O(n)
import collections
def bioHazard(n, allergic, poisonous):
    d = collections.defaultdict(lambda :-1)
    for a,b in zip(allergic, poisonous):
        a,b = sorted([a,b])
        d[b] = max(d[b],a)
        
    for i in range(1, n+1):
        d[i] = max(d[i], d[i-1])
    
    res = 0
    for i in range(1, n+1):
        if d[i]==-1:
            res += i
        else:
            res += i-d[i]
    return res

Problem category

It is similar to the classical DP problem of

Largest Sum Contiguous Subarray, which can be solved by using the Kadane’s algorithm.