Description Link to heading

1223. Dice Roll Simulation (Hard)

A die simulator generates a random number from 1 to 6 for each roll. You introduced a constraint to the generator such that it cannot roll the number i more than rollMax[i] ( 1-indexed) consecutive times. Given an array of integers rollMax and an integer n, return the number of distinct sequences that can be obtained with exact n rolls. Since the answer may be too large, return it modulo 10⁹ + 7. Two sequences are considered different if at least one element differs from each other. Example 1:

Input: n = 2, rollMax = [1,1,2,2,2,3]
Output: 34
Explanation: There will be 2 rolls of die, if there are no constraints on the die, there are 6 * 6 =
36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most
once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 =
34.

Example 2:

Input: n = 2, rollMax = [1,1,1,1,1,1]
Output: 30

Example 3:

Input: n = 3, rollMax = [1,1,1,2,2,3]
Output: 181

Constraints:

  • 1 <= n <= 5000
  • rollMax.length == 6
  • 1 <= rollMax[i] <= 15

Solution Link to heading

Sort the properties by attack from lowest to highest. If the two roles have the same, the one with the lower defense is on top.

We can traverse the sorted properties,

  • if properties[i][0] < properties[0][0] && properties[i][1] < defend_max, res++;
  • if properties[i][1] > defend_max, update defend_max;

Code Link to heading 

class Solution {
  public:
    int numberOfWeakCharacters(vector<vector<int>> &properties) {
        std::sort(properties.begin(), properties.end(), [&](vector<int> &vec1, vector<int> &vec2) {
            if (vec1[0] == vec2[0])
                return vec1[1] <= vec2[1];
            return vec1[0] > vec2[0];
        });
        int cnt = 0;
        int attack_max = properties[0][0];
        int defend_max = properties[0][1];
        for (int i = 1; i < properties.size(); i++) {
            if (properties[i][0] < attack_max && properties[i][1] < defend_max) {
                cnt++;
            } else if (properties[i][1] > defend_max) {
                defend_max = properties[i][1];
            }
        }
        return cnt;
    }
};