Recently I am actively doing Leetcode weekly contest because of two reasons: 1) Practicing for industrial style job interview; 2) Just for fun.
Why it is fun??? Grinding Leetcode is more like some enjoyable activities to me, just like solving other small puzzles like chess, sudoku, crossword. They all have clear rules and clear goal, and usually takes less than one hour to finish. Sometimes it might be technically difficult dealing with HARD level problems, but still mentally easier than coding for research or some useful big projects that I need to struggle with many decision makings.
One additional benefit for doing leetcode is to protect my brain by doing congnition heavy tasks without AI. See this article “Your brain on ChatGPT”.
I plan to record my weekly progress here so I can keep track my progress, and also track some interesting problems.
Rank 4705/26710, 2 Solved
You are given a string `s` of length `m` consisting of digits. You are also given a 2D integer array `queries`, where `queries[i] = [li, ri]`.
For each `queries[i]`, extract the **substring** `s[li..ri]`. Then, perform the following:
- Form a new integer `x` by concatenating all the **non-zero digits** from the substring in their original order. If there are no non-zero digits, `x = 0`.
- Let `sum` be the **sum of digits** in `x`. The answer is `x * sum`.
Return an array of integers `answer` where `answer[i]` is the answer to the `ith` query.
Since the answers may be very large, return them **modulo** `109 + 7`.
**Example 1:**
**Input:** s = "10203004", queries = [[0,7],[1,3],[4,6]]
**Output:** [12340, 4, 9]
**Explanation:**
- `s[0..7] = "10203004"`
- `x = 1234`
- `sum = 1 + 2 + 3 + 4 = 10`
- Therefore, answer is `1234 * 10 = 12340`.
- `s[1..3] = "020"`
- `x = 2`
- `sum = 2`
- Therefore, the answer is `2 * 2 = 4`.
- `s[4..6] = "300"`
- `x = 3`
- `sum = 3`
- Therefore, the answer is `3 * 3 = 9`.
**Example 2:**
**Input:** s = "1000", queries = [[0,3],[1,1]]
**Output:** [1, 0]
**Explanation:**
- `s[0..3] = "1000"`
- `x = 1`
- `sum = 1`
- Therefore, the answer is `1 * 1 = 1`.
- `s[1..1] = "0"`
- `x = 0`
- `sum = 0`
- Therefore, the answer is `0 * 0 = 0`.
**Example 3:**
**Input:** s = "9876543210", queries = [[0,9]]
**Output:** [444444137]
**Explanation:**
- `s[0..9] = "9876543210"`
- `x = 987654321`
- `sum = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45`
- Therefore, the answer is `987654321 * 45 = 44444444445`.
- We return `44444444445 modulo (109 + 7) = 444444137`.
This problem asks to calculate some specific sum of a subarray. I was able to come up with using presum but it was still too slow because I didn’t know the tricks to handle MOD operation and POW operation.
Get the sum of digits are easy to solve by directly using presum. The trick is how to get the non-zero digits concatenation.
My original approach. I pre-calculated the concatenation in string and record the corresponding index of i at the concatenation. And using int to convert it back to number.
concat = "".join([x for x in s if x != '0'])
presum = [0]
for v in s:
presum.append(presum[-1] + (1 if v != '0' else 0))
## This is too slow
x = int(concat[presum2[l]: presum2[r+1]])
However, this is too slow because int function will be $O(r-l)$
Optimum: The trick is about how to get the number within the range. Without considering 0, we can save the number until i as preNum[i]. For example $s = 12345$
To get the number within range $[l, r]$, we can do
\[preNum[r+1] - preNum[l]\times 10^{r+1-l}\]For example, $[2, 3] \rightarrow 34$ = $1234 - 12 \times 10^{2}$
Here $2$ comes from the diff(number of digits) which is (3+1) - 2 = 2
Considering 0, we can use another ct to calculate the number of non-zero digits between two indexes, and the number within range will be calculated as
presum is commonly used in count. Here is the solution:
n = len(s)
presum_d = [0]
presum_num = [0]
presum_count = [0]
MOD = 1_000_000_007
for v in s:
v = int(v)
presum_d.append(presum_d[-1] + v)
presum_num.append((presum_num[-1] * 10 + v) % MOD
if v else presum_num[-1])
presum_count.append(presum_count[-1] + bool(v))
ret = []
for l, r in queries:
summ = (presum_d[r+1] - presum_d[l]) % MOD
length = presum_count[r+1] - presum_count[l]
x = (presum_num[r+1] - presum_num[l] * 10**length) % MOD
ret.append((x * summ) % MOD)
return re
Trick 1: However, above code still run out of time, because calculate 10**length is slow (This is an interesting discussion about why pow is slow in Python)
The solution is to pre-calculate pow if you need to use it frequently. MAX_N comes from the constraints in problem description.
pow10 = [1] * MAX_N
for i in range(1, MAX_N):
pow10[i] = (pow10[i - 1] * 10) % MOD
## Use precalcuated pow10
x = (presum_num[r+1] - presum_num[l] * pow10[length]) % MOD
Rank 8568/26806. Solved 2.
You are given a positive integer `n` and an integer `target`.
Return the **lexicographically smallest** array of integers of size `n` such that:
- The **sum** of its elements equals `target`.
- The **absolute values** of its elements form a **permutation** of size `n`.
If no such array exists, return an empty array.
A **permutation** of size `n` is a rearrangement of integers `1, 2, ..., n`.
**Example 1:**
**Input:** n = 3, target = 0
**Output:** [-3,1,2]
**Explanation:**
The arrays that sum to 0 and whose absolute values form a permutation of size 3 are:
- `[-3, 1, 2]`
- `[-3, 2, 1]`
- `[-2, -1, 3]`
- `[-2, 3, -1]`
- `[-1, -2, 3]`
- `[-1, 3, -2]`
- `[1, -3, 2]`
- `[1, 2, -3]`
- `[2, -3, 1]`
- `[2, 1, -3]`
- `[3, -2, -1]`
- `[3, -1, -2]`
The lexicographically smallest one is `[-3, 1, 2]`.
**Example 2:**
**Input:** n = 1, target = 10000000000
**Output:** []
**Explanation:**
There are no arrays that sum to 10000000000 and whose absolute values form a permutation of size 1. Therefore, the answer is `[]`.
**Constraints:**
- `1 <= n <= 105`
- `-1010 <= target <= 1010`
This question basically asks to assign any values from $S = {1,…,n}$ to be negative to get $sum(S) = target$, and find the assignment which is lexicographically smallest.
Original idea: I didn’t come up with any efficient solution, so I tried brute force by searching each position of $S$ by DFS, and search in the lexicographical order. The firstly searched value will be the smallest one. The complexity will be $O(n!)$.
path = []
used = set()
ret = []
def dfs(i, sum):
nonlocal path, used, ret
if i == n:
if sum == target:
ret = path[:]
return True
else:
return False
for v in range(-n, n+1):
if v != 0 and abs(v) not in used:
used.add(abs(v))
path.append(v)
if dfs(i+1, sum + v):
return True
path.pop()
used.remove(abs(v))
return False
dfs(0, 0)
return ret
Optimum solution: This problem can be solved by greedy algorithm by converting to subset sum problem in $O(n)$.
I feel this problem is more like brainteaser to me because the keywords permutation and lexicographically the smallest kind of misleading me to think about backtracking.
Noticing following property. Define
We have
$PosS + NegS = Sum$ $PosS - NegS = target$
Thus
$NegS = \frac{Sum - target}{2}$
Since we can calculate $NegS$, this problem becomes to select some numbers from $S$ which have sum as $NegS$. We can use greedy algorithm to pick the largest absolute values to minimize the result.
S = (n * (n+1)) // 2
if (S - target) % 2 != 0 or abs(target) > S:
return []
negS = (S - target) // 2
ret = []
ret2 = []
for v in range(n, 0, -1):
if v <= negS:
ret.append(-v)
negS -= v
else:
ret2.append(v)
return ret + ret2[::-1]
Insight 1: Why the greedy algorithm from large to small can always find the solution? i.e., $negS$ will be reduced to $0$.
The intuition comes from when you fill the floor with tiles, you start from the largest possible tile, and you always have the smaller tile to use. In the end you can always perfectly fill the area as you always have smaller tile to fill those small gaps.
I remember there is also similar insights in resource management and scheduling theory, that you can get better utilization by scheduling longest task first.
Formally, we can prove that for any positive integer $n$, the subset sums of ${1, \dots, n}$ can form every integer in the range $[0, \frac{n(n+1)}{2}]$. Since negS is defined as $\frac{S_{total} - target}{2}$ and we have checked that $0 \le negS \le S_{total}$, it is guaranteed that there exists a subset summing exactly to negS.
You are given two integers num1 and num2 representing an inclusive range [num1, num2].
The waviness of a number is defined as the total count of its peaks and valleys:
A digit is a peak if it is strictly greater than both of its immediate neighbors.
A digit is a valley if it is strictly less than both of its immediate neighbors.
The first and last digits of a number cannot be peaks or valleys.
Any number with fewer than 3 digits has a waviness of 0.
Return the total sum of waviness for all numbers in the range [num1, num2].
Example 1:
Input: num1 = 120, num2 = 130
Output: 3
Explanation:
In the range [120, 130]:
120: middle digit 2 is a peak, waviness = 1.
121: middle digit 2 is a peak, waviness = 1.
130: middle digit 3 is a peak, waviness = 1.
All other numbers in the range have a waviness of 0.
Thus, total waviness is 1 + 1 + 1 = 3.
Example 2:
Input: num1 = 198, num2 = 202
Output: 3
Explanation:
In the range [198, 202]:
198: middle digit 9 is a peak, waviness = 1.
201: middle digit 0 is a valley, waviness = 1.
202: middle digit 0 is a valley, waviness = 1.
All other numbers in the range have a waviness of 0.
Thus, total waviness is 1 + 1 + 1 = 3.
Example 3:
Input: num1 = 4848, num2 = 4848
Output: 2
Explanation:
Number 4848: the second digit 8 is a peak, and the third digit 4 is a valley, giving a waviness of 2.
Constraints:
1 <= num1 <= num2 <= 1015
This problem asks to find the number of waves (some kind of pattern like $a < b > c$ or $a > b < c$) between lower bound and upper bound, which seems to be a classical digit DP problem.
I didn’t get enough time to see this problem as I was stucked at Q3.
class Solution:
def totalWaviness(self, num1: int, num2: int) -> int:
upper_bound = [int(x) for x in str(num2)]
lower_bound = [int(x) for x in str(num1)]
diff = len(upper_bound) - len(lower_bound)
lower_bound = [0] * (diff) + lower_bound
n = len(upper_bound)
@cache
def dfs(i, wave, lld, ld, limit_low, limit_high, isnum):
if i == n:
return wave
low = lower_bound[i] if limit_low else 0
high = upper_bound[i] if limit_high else 9
ret = 0
for d in range(low, high + 1):
wave_n = wave
if isnum and i >= 2 and lld < ld > d or lld > ld < d:
wave_n += 1
ret += dfs(i+1, wave_n, ld, d,
limit_low and d == low,
limit_high and d == high,
isnum or ld != 0
)
return ret
return dfs(0, 0, 0, 0, True, True, False)
There are two tricks for this digit DP:
is_num to check if the left side of wave is leading zero isnum or ld != 0wave to following dfs call. This makes the solution slower but easier to write.Following is the implementation without using wave
@cache
def dfs(i, lld, ld, limit_low, limit_high, isnum):
if i == n:
return 0, 1
low = lower_bound[i] if limit_low else 0
high = upper_bound[i] if limit_high else 9
total_wave = 0
total_count = 0
for d in range(low, high + 1):
is_new_wave = False
if isnum and i >= 2 and (lld < ld > d) or (lld > ld < d):
is_new_wave = True
sub_wave, sub_count = dfs(i + 1, ld, d,
limit_low and d == low,
limit_high and d == high,
isnum or ld != 0)
total_wave += sub_wave
total_count += sub_count
if is_new_wave:
total_wave += sub_count
return total_wave, total_count
Rank 279/28885. 3 Solved.
You are given a **cyclic** array `nums` and an integer `k`.
**Partition** `nums` into **at most** `k` subarrays. As `nums` is cyclic, these subarrays may wrap around from the end of the array back to the beginning.
The **range** of a subarray is the difference between its **maximum** and **minimum** values. The **score** of a partition is the sum of subarray **ranges**.
Return the **maximum** possible **score** among all cyclic partitions.
**Example 1:**
**Input:** nums = [1,2,3,3], k = 2
**Output:** 3
**Explanation:**
- Partition `nums` into `[2, 3]` and `[3, 1]` (wrapped around).
- The range of `[2, 3]` is `max(2, 3) - min(2, 3) = 3 - 2 = 1`.
- The range of `[3, 1]` is `max(3, 1) - min(3, 1) = 3 - 1 = 2`.
- The score is `1 + 2 = 3`.
**Example 2:**
**Input:** nums = [1,2,3,3], k = 1
**Output:** 2
**Explanation:**
- Partition `nums` into `[1, 2, 3, 3]`.
- The range of `[1, 2, 3, 3]` is `max(1, 2, 3, 3) - min(1, 2, 3, 3) = 3 - 1 = 2`.
- The score is 2.
**Example 3:**
**Input:** nums = [1,2,3,3], k = 4
**Output:** 3
**Explanation:**
Identical to Example 1, we partition `nums` into `[2, 3]` and `[3, 1]`. Note that `nums` may be partitioned into fewer than `k` subarrays.
This problem aims to find the optimum partition that the sum of difference of each sub-array can be maximized. The difference is defined as the maximum value minus the minimum value of sub-array.
There are two challenges:
Challenge 1: My beginning idea: One classical way to handle cyclic is duplicating array and appending to the end of the original array, and iterate from each element as start. This will multiply $\times O(n)$ complexity.
For example, for array [a,b,c], duplicate it to [a,b,c,a,b,c] then start from each element:
[a,b,c][b,c,a][c,a,b]Optimum: In this problem, we can have a more efficient way to handle the cyclic by utilizing the property of problem, where the maximum value will always be at the boarder of subarray. This only multiply $\times 2$ complexity. %%TODO: Add the key idea explaination%%
For example, for array [1,2,4,1,3], there must be an optimum partition with subarray [...,4] or [4,...]. This can be proved by exchange argument, see insight 1.
Thus, we can handle the array twice with [..., Max] and [Max, ...] to solve the cyclic
Challenge 2: My beginning idea: I didn’t come up with any good idea, so I just used brute force search by divide and conquer, where I defined
\[f(i, j, k) = max_{s\in[i, j), v \in (0,k)}(f(i, s, k-v), f(s+1, j, v), d(i, j))\]Where $i \leq j \lt n$, $d(i,j)$ can be preprocessed by $O(n^2)$, the complexity will be $O(kn^2)$.
Optimum: The optimum solution is using state-machine dynamic programming. The original problem is equal to the stock trading problem LC2573. Best Time to Buy and Sell Stock V, where we can trade at most $k$ times by either long or short.
"""
i -> The i-th day
j -> 0: empty, 1: long, 2: short
k -> The left transaction times
"""
@cache
def dfs(i, j, k):
if i == len(nums):
return 0 if j == 0 else -inf
if k < 0:
return -inf
mx = 0
v = nums[i]
if j == 0:
mx = max(dfs(i+1, j, k), dfs(i+1, 2, k)+v,
dfs(i+1, 1, k)-v, mx)
elif j == 1:
mx = max(dfs(i+1, j, k), dfs(i+1, 0, k-1)+v)
else:
mx = max(dfs(i+1, j, k), dfs(i+1, 0, k-1)-v)
return m
Solution:
i = nums.index(max(nums))
nums1 = nums[i:] + nums[:i]
nums2 = nums[i+1:] + nums[:i+1]
mx = 0
nums = nums1
mx = max(dfs(0, 0, k), mx)
dfs.cache_clear()
nums = nums2
mx = max(dfs(0, 0, k), mx)
dfs.cache_clear()
Insight 1: Why we can break cyclic by maximum value.
Since the score of a subarray is calculated by $max(A) - min(A)$, we have this monotonicity:
Adding elements to a subarray can never decrease its score. $\text{Score}(A \cup B) \ge \text{Score}(A)$
Thus, for any partition $P$ that maximum value $M$ is strictly inside a subarray
\(S = [\dots, A, \mathbf{M}, B, \dots]\) And $Score(S) = M - min(S)$
We have $min(S)$ is in either $S_{left}$ or $S_{right}$
By merge the subarray without $min(S)$ to its another neighbor subarray in partition as a new partition $P’$, we always have $Score(P’) \geq Score(P)$
Insight 2: Why this is equal to stock trading problem.
The objective of the partition problem is to calculate the score of a subarray as:
\[\text{Score} = \max(Subarray) - \min(Subarray)\]If we look at this algebraically, the score is simply the summation of a positive term and a negative term:
\[\text{Score} = (+1 \times \text{MaxVal}) + (-1 \times \text{MinVal})\]In any given subarray, the intermediate numbers (those that are neither max nor min) contribute 0 to the score.
Therefore, finding the optimum $k$-partition is equivalent to finding at most $k$-pairs of $(+A, -B)$ from the array following.
Rank 13547/27939. 2 Solved.
You are given an integer array `nums`.
You are allowed to replace **at most** one element in the array with any other integer value of your choice.
Return the length of the **longest non-decreasing subarray** that can be obtained after performing at most one replacement.
An array is said to be **non-decreasing** if each element is greater than or equal to its previous one (if it exists).
**Example 1:**
**Input:** nums = [1,2,3,1,2]
**Output:** 4
**Explanation:**
Replacing `nums[3] = 1` with 3 gives the array [1, 2, 3, 3, 2].
The longest non-decreasing subarray is [1, 2, 3, 3], which has a length of 4.
**Example 2:**
**Input:** nums = [2,2,2,2,2]
**Output:** 5
**Explanation:**
All elements in `nums` are equal, so it is already non-decreasing and the entire `nums` forms a subarray of length 5.
**Constraints:**
- `1 <= nums.length <= 105`
- `-109 <= nums[i] <= 109`
The key challenge of this problem is it allows replacing one element with any value. Without this relaxation, we can simply solve it by iterate the array once by $O(n)$.
Solution 1: One solution is to use prefix-suffix decomposition. We can define
prefix[i]: The longest non-dec array ends at isuffix[i]: The longest non-dec array starts at iThe final result is \(\forall nums[i-1]\leq nums[i+1]: max(prefix[i-1] + suffix[i+1] + 1)\)
Both prefix and suffix can be built in $O(n)$
Solution 2: Another solution is using state-machine DP. We can define
$f(i,j)$: The longest non-dec array ends at i with state
Note: Assume nums[i] is not replaced, e.g., replacement can only happens at $\lt i$.
For $j=0$ , we have \(f[i][0] = \begin{cases} f[i-1][0] + 1, & \text{if } nums[i] \ge nums[i-1] \\ 1, & \text{otherwise} \end{cases}\) For $j=1$, we have
Case1: Consider $f[i-1][1]$, replaced before $i-1$ \(L_1 = \begin{cases} f[i-1][1] + 1, & \text{if } nums[i] \ge nums[i-1] \\ -\infty \text{ (invalid)} \end{cases}\)
Case2: Consider $f[i-2][0]$, replaced at $i-1$ \(L_2 = \begin{cases} f[i-2][0] + 2, & \text{if } nums[i] \ge nums[i-2] \text{ (and } i \ge 2) \\ 2, & \text{otherwise} \end{cases}\) Combining two cases: \(f[i][1] = max(L_1, L_2)\)
Since we consider $nums[i]$ cannot be replaced, the final result will be \(Ans = \max_{\text{over all } i} \Big( \underbrace{f[i][1]}_{\text{Replace before } i}, \quad \underbrace{f[i-1][0] + 1}_{\text{Replace at } i} \Big)\)
You are given an integer array `nums` and an integer `target`.
Return the number of **subarrays** of `nums` in which `target` is the **majority element**.
The **majority element** of a subarray is the element that appears **strictly more than half** of the times in that subarray.
**Example 1:**
**Input:** nums = [1,2,2,3], target = 2
**Output:** 5
**Explanation:**
Valid subarrays with `target = 2` as the majority element:
- `nums[1..1] = [2]`
- `nums[2..2] = [2]`
- `nums[1..2] = [2,2]`
- `nums[0..2] = [1,2,2]`
- `nums[1..3] = [2,2,3]`
So there are 5 such subarrays.
**Example 2:**
**Input:** nums = [1,1,1,1], target = 1
**Output:** 10
**Explanation:**
****All 10 subarrays have 1 as the majority element.
**Example 3:**
**Input:** nums = [1,2,3], target = 4
**Output:** 0
**Explanation:**
`target = 4` does not appear in `nums` at all. Therefore, there cannot be any subarray where 4 is the majority element. Hence the answer is 0.
This problem asks to count number of subarrays which target is majority elements.
There are two challenges:
target is the majority of a subarrayChallenge 1: One classical way to count the number of elements is to convert it as presum problem. For example, leetcode 525. Contiguous Array.
We can convert \(\begin{align} nums[i] = target \rightarrow 1 \\ nums[i] \neq target \rightarrow -1 \end{align}\) Then target is the majority of subarray $\Leftrightarrow$ $sum(subarray) > 0$
We can use presum to quickly get the sum of a subarray.
Challenge 2: My beginning idea: Check every pair of (i, j), the complexity will be $O(n^2)$
for j, v in enumerate(presum):
for vpre in presum[:j]:
if v > vpre:
count += 1
Optimum: A better solution is we can dynamically maintain the presum to get $O(nlogn)$ complexity.
From above code, we observe that we basically want to get the number of presum[i] < presum[j] where i < j. This is the classical sequential pairs problem.
To achieve this, we can use binary indexed tree (BIT), which is commonly used to efficiently update/count the number of elements less/large than a value.
We firstly map the presum to the index of tree $idx = presum + len(nums) + 1$ due to $presum \in [-n, n]$. (Note BIT requires 1-based index). Then we use BIT for updating and searching.
class Solution:
def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
## Define the BIT
tree = [0] * (2 * len(nums) + 2)
offset = 1 + len(nums)
def pre(i):
res = 0
while i > 0:
res += tree[i]
i -= i & -i
return res
def update(i, v):
while i < len(tree):
tree[i] += v
i += i & -i
summ = 0
update(0 + offset, 1)
nums = [1 if x == target else -1 for x in nums]
count = 0
for v in nums:
summ += v
count += pre(summ + offset - 1)
update(summ + offset, 1)
return count
An even simpler method in Python is to use SortedList:
sl = SortedList([0])
summ = 0
count = 0
for v in nums:
summ += v
count += sl.bisect_left(summ)
sl.add(summ)
return count
Rank 4732/31548. Solved 2
You are given two integer arrays of size 2: `d = [d1, d2]` and `r = [r1, r2]`.
Two delivery drones are tasked with completing a specific number of deliveries. Drone `i` must complete `di` deliveries.
Each delivery takes **exactly** one hour and **only one** drone can make a delivery at any given hour.
Additionally, both drones require recharging at specific intervals during which they cannot make deliveries. Drone `i` must recharge every `ri` hours (i.e. at hours that are multiples of `ri`).
Return an integer denoting the **minimum** total time (in hours) required to complete all deliveries.
**Example 1:**
**Input:** d = [3,1], r = [2,3]
**Output:** 5
**Explanation:**
- The first drone delivers at hours 1, 3, 5 (recharges at hours 2, 4).
- The second drone delivers at hour 2 (recharges at hour 3).
**Example 2:**
**Input:** d = [1,3], r = [2,2]
**Output:** 7
**Explanation:**
- The first drone delivers at hour 3 (recharges at hours 2, 4, 6).
- The second drone delivers at hours 1, 5, 7 (recharges at hours 2, 4, 6).
**Example 3:**
**Input:** d = [2,1], r = [3,4]
**Output:** 3
**Explanation:**
- The first drone delivers at hours 1, 2 (recharges at hour 3).
- The second drone delivers at hour 3.
This question is my favorite one so far I have met in LC contest, I feel I learned a lot from this one. I didn’t come up with any idea and this one looks like a DP problem to me at the time (I have never known the trick using binary search for finding target until this question).
My original thought was that this can be solved by greedy algorithm, and I tried simulating the makespan by trying different scheduling policies (e.g., fixed priority and earliest deadline first), which is totally off the track.
Solution: The basic idea is using binary search to search within the bound. We can get lower bound lb and upper bound ub, by designing a check function, we can use binary search to efficiently find the smallest number that satisfy check within the range.
bisect_left(range(lb, ub+1), True, key=check)
Then what comes next is how to design an efficient check function. We actually need to find a $\lt O(d)$ solution for this question based on the input data scale $d_i \leq 10^9$, thus simulation won’t work.
The trick here is using a mathematical solution (inclusion-exclusion principle) to implement the check function.
def check(t):
return d1 + t // r1 <= t \
and d2 + t // r2 <= t \
and d1 + d2 <= t - t // L
The key idea is the time domain can be divided in 4 situations. Consider drone A, B within time $t$ we have the partition:
The optimum solution is to let A use $t_A$ first then use the time left in $t_C$. This is kind of greedy algorithm. So we must have \(d_1 \leq t_A + t_C = t - \lfloor \frac{t}{r_1} \rfloor\) Similarly, for B: \(d_2 \leq t_B + t_C = t - \lfloor \frac{t}{r_1} \rfloor\) Because A and B use in total $d_1 + d_2$ hours, we have
\(d_1 + d_2 \leq t_A + t_B + t_C = t - \lfloor \frac{t}{lcm(r_1, r_2)} \rfloor\) The above three conditions are necessary condition. But we can prove that above three conditions are also sufficient conditions.
d1, d2 = d
r1, r2 = r
L = lcm(r1, r2)
def check(t):
return d1 + t // r1 <= t \
and d2 + t // r2 <= t \
and d1 + d2 <= t - t // L
lb = 0
ub = (d1 + d2) * 2
return bisect_left(range(lb, ub + 1), True, key=check)
Proof
Let’s calculate the spillover (demand remaining after using exclusive slots):
The Sufficient Condition: The schedule is valid if and only if: \(O_1+O_2≤t_C\)
We verify this inequality by checking all four possible cases of “spillover”:
Case 1: No Spillover ($d1≤tA$ and $d2≤tB$)
Case 2: Only Drone 1 Spills Over (d1>tA and d2≤tB)
…
skewcy@gmail.com