Skip to content

3802. Number of Ways to Paint Sheets πŸ”’

Description

You are given an integer n representing the number of sheets.

You are also given an integer array limit of size m, where limit[i] is the maximum number of sheets that can be painted using color i.

You must paint all n sheets under the following conditions:

  • Exactly two distinct colors are used.
  • Each color must cover a single contiguous segment of sheets.
  • The number of sheets painted with color i cannot exceed limit[i].

Return an integer denoting the number of distinct ways to paint all sheets. Since the answer may be large, return it modulo 109 + 7.

Note: Two ways differ if at least one sheet is painted with a different color.

 

Example 1:

Input: n = 4, limit = [3,1,2]

Output: 6

Explanation:​​​​​​​

For each ordered pair (i, j), where color i is used for the first segment and color j for the second segment (i != j), a split of x and 4 - x is valid if 1 <= x <= limit[i] and 1 <= 4 - x <= limit[j].

Valid pairs and counts are:

  • (0, 1): x = 3
  • (0, 2): x = 2, 3
  • (1, 0): x = 1
  • (2, 0): x = 1, 2

Therefore, there are 6 valid ways in total.

Example 2:

Input: n = 3, limit = [1,2]

Output: 2

Explanation:

For each ordered pair (i, j), where color i is used for the first segment and color j for the second segment (i != j), a split of x and 3 - x is valid if 1 <= x <= limit[i] and 1 <= 3 - x <= limit[j].

Valid pairs and counts are:

  • (0, 1): x = 1
  • (1, 0): x = 2

Hence, there are 2 valid ways in total.

Example 3:

Input: n = 3, limit = [2,2]

Output: 4

Explanation:

For each ordered pair (i, j), where color i is used for the first segment and color j for the second segment (i != j), a split of x and 3 - x is valid if 1 <= x <= limit[i] and 1 <= 3 - x <= limit[j].

Valid pairs and counts are:

  • (0, 1): x = 1, 2
  • (1, 0): x = 1, 2

Therefore, there are 4 valid ways in total.

 

Constraints:

  • 2 <= n <= 109
  • 2 <= m == limit.length <= 105
  • 1 <= limit[i] <= 109

Solutions

Solution 1

Thinking

We must use exactly two colors, each on a contiguous block, without exceeding \(\textit{limit}\). \(n \le 10^9\) forbids enumerating cut positions sheet by sheet.

For an ordered pair \((i,j)\), valid cuts \(x\) form an integer interval determined by \(n\) and the two limits, whose length is \(O(1)\).

With \(m \le 10^5\), pairing every two colors is \(O(m^2)\) even after the cut is closed-form. The bottleneck is counting many limits at once.

Each color's contribution depends only on how its limit sits relative to \(n\). Sorting \(\textit{limit}\) and accumulating interval lengths with prefix sums yields the answer modulo \(10^9+7\).

1


1


1


1

Comments