Posts tagged as “simulation”

花花酱 LeetCode 1900. The Earliest and Latest Rounds Where Players Compete

By zxi on August 11, 2021

There is a tournament where n players are participating. The players are standing in a single row and are numbered from 1 to n based on their initial standing position (player 1 is the first player in the row, player 2 is the second player in the row, etc.).

The tournament consists of multiple rounds (starting from round number 1). In each round, the i^th player from the front of the row competes against the i^th player from the end of the row, and the winner advances to the next round. When the number of players is odd for the current round, the player in the middle automatically advances to the next round.

For example, if the row consists of players 1, 2, 4, 6, 7
- Player 1 competes against player 7.
- Player 2 competes against player 6.
- Player 4 automatically advances to the next round.

After each round is over, the winners are lined back up in the row based on the original ordering assigned to them initially (ascending order).

The players numbered firstPlayer and secondPlayer are the best in the tournament. They can win against any other player before they compete against each other. If any two other players compete against each other, either of them might win, and thus you may choose the outcome of this round.

Given the integers n, firstPlayer, and secondPlayer, return an integer array containing two values, the earliest possible round number and the latest possible round number in which these two players will compete against each other, respectively.

Example 1:

Input: n = 11, firstPlayer = 2, secondPlayer = 4
Output: [3,4]
Explanation:
One possible scenario which leads to the earliest round number:
First round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Second round: 2, 3, 4, 5, 6, 11
Third round: 2, 3, 4
One possible scenario which leads to the latest round number:
First round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Second round: 1, 2, 3, 4, 5, 6
Third round: 1, 2, 4
Fourth round: 2, 4

Example 2:

Input: n = 5, firstPlayer = 1, secondPlayer = 5
Output: [1,1]
Explanation: The players numbered 1 and 5 compete in the first round.
There is no way to make them compete in any other round.

Constraints:

2 <= n <= 28
1 <= firstPlayer < secondPlayer <= n

Solution 1: Simulation using recursion

All possible paths,
Time complexity: O(n²*2ⁿ)
Space complexity: O(logn)

dfs(s, i, j, d) := let i battle with j at round d, given s (binary mask of dead players).

C++

// Author: Huahua

class Solution {

public:

vector<int> earliestAndLatest(int n, int a, int b) {

vector<int> ans{INT_MAX, INT_MIN};

function<void(int, int, int, int)> dfs = [&](int s, int i, int j, int d) {

while (i < j && s >> i & 1) ++i;

while (i < j && s >> j & 1) --j;

if (i >= j) {

return dfs(s, 1, n, d + 1);

} else if (i == a && j == b) {

ans[0] = min(ans[0], d);

ans[1] = max(ans[1], d);

} else {

if (i != a && i != b)

dfs(s | (1 << i), i + 1, j - 1, d);

if (j != a && j != b)

dfs(s | (1 << j), i + 1, j - 1, d);

}

};

dfs(0, 1, n, 1);

return ans;

}

};

花花酱 LeetCode 1886. Determine Whether Matrix Can Be Obtained By Rotation

By zxi on August 8, 2021

Given two n x n binary matrices mat and target, return true if it is possible to make mat equal to target by rotating mat in 90-degree increments, or false otherwise.

Example 1:

Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
Output: true
Explanation: We can rotate mat 90 degrees clockwise to make mat equal target.

Example 2:

Input: mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
Output: false
Explanation: It is impossible to make mat equal to target by rotating mat.

Example 3:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
Output: true
Explanation: We can rotate mat 90 degrees clockwise two times to make mat equal target.

Constraints:

n == mat.length == target.length
n == mat[i].length == target[i].length
1 <= n <= 10
mat[i][j] and target[i][j] are either 0 or 1.

Solution: Simulation

Time complexity: O(n²)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {

const int n = mat.size();

auto rot = [n](vector<vector<int>>& mat) {

for (int i = 0; i < n; ++i)

for (int j = i; j < n; ++j)

swap(mat[i][j], mat[j][i]);

for (int j = 0; j < n; j++)

for (int i = 0; i < n / 2; ++i)

swap(mat[i][j], mat[n - i - 1][j]);

return mat;

};

for (int i = 0; i < 4; ++i)

if (rot(mat) == target) return true;

return false;

}

};

花花酱 LeetCode 1882. Process Tasks Using Servers

By zxi on August 8, 2021

You are given two 0-indexed integer arrays servers and tasks of lengths n and m respectively. servers[i] is the weight of the i^th server, and tasks[j] is the time needed to process the j^th task in seconds.

Tasks are assigned to the servers using a task queue. Initially, all servers are free, and the queue is empty.

At second j, the j^th task is inserted into the queue (starting with the 0^th task being inserted at second 0). As long as there are free servers and the queue is not empty, the task in the front of the queue will be assigned to a free server with the smallest weight, and in case of a tie, it is assigned to a free server with the smallest index.

If there are no free servers and the queue is not empty, we wait until a server becomes free and immediately assign the next task. If multiple servers become free at the same time, then multiple tasks from the queue will be assigned in order of insertion following the weight and index priorities above.

A server that is assigned task j at second t will be free again at second t + tasks[j].

Build an array ans of length m, where ans[j] is the index of the server the j^th task will be assigned to.

Return the array ans.

Example 1:

Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]
Output: [2,2,0,2,1,2]
Explanation: Events in chronological order go as follows:
- At second 0, task 0 is added and processed using server 2 until second 1.
- At second 1, server 2 becomes free. Task 1 is added and processed using server 2 until second 3.
- At second 2, task 2 is added and processed using server 0 until second 5.
- At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.
- At second 4, task 4 is added and processed using server 1 until second 5.
- At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.

Example 2:

Input: servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
Output: [1,4,1,4,1,3,2]
Explanation: Events in chronological order go as follows: 
- At second 0, task 0 is added and processed using server 1 until second 2.
- At second 1, task 1 is added and processed using server 4 until second 2.
- At second 2, servers 1 and 4 become free. Task 2 is added and processed using server 1 until second 4. 
- At second 3, task 3 is added and processed using server 4 until second 7.
- At second 4, server 1 becomes free. Task 4 is added and processed using server 1 until second 9. 
- At second 5, task 5 is added and processed using server 3 until second 7.
- At second 6, task 6 is added and processed using server 2 until second 7.

Constraints:

servers.length == n
tasks.length == m
1 <= n, m <= 2 * 10⁵
1 <= servers[i], tasks[j] <= 2 * 10⁵

Solution: Simulation / Priority Queue

Two priority queues, one for free servers, another for releasing events.
One FIFO queue for tasks to schedule.

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {

const int n = servers.size();

const int m = tasks.size();

using P = pair<long, int>;

priority_queue<P, vector<P>, greater<P>> frees, release;

for (int i = 0; i < n; ++i)

frees.emplace(servers[i], i);

vector<int> ans(m);

queue<int> q;

int l = 0;

long t = 0;

int count = 0;

while (count != m) {

// Release servers.

while (!release.empty() && release.top().first <= t) {

auto [rt, i] = release.top(); release.pop();

frees.emplace(servers[i], i);

}

// Enqueue tasks.

while (l < m && l <= t) q.push(l++);

// Schedule tasks.

while (q.size() && frees.size()) {

const int j = q.front(); q.pop();

auto [w, i] = frees.top(); frees.pop();

release.emplace(t + tasks[j], i);

ans[j] = i;

++count;

}

// Advance time.

if (frees.empty() && !release.empty()) {

t = release.top().first;

} else {

++t;

}

return ans;

}

};

花花酱 LeetCode 1860. Incremental Memory Leak

By zxi on June 1, 2021

You are given two integers memory1 and memory2 representing the available memory in bits on two memory sticks. There is currently a faulty program running that consumes an increasing amount of memory every second.

At the i^th second (starting from 1), i bits of memory are allocated to the stick with more available memory (or from the first memory stick if both have the same available memory). If neither stick has at least i bits of available memory, the program crashes.

Return an array containing [crashTime, memory1_crash, memory2_crash], where crashTime is the time (in seconds) when the program crashed and memory1_crash and memory2_crash are the available bits of memory in the first and second sticks respectively.

Example 1:

Input: memory1 = 2, memory2 = 2
Output: [3,1,0]
Explanation: The memory is allocated as follows:
- At the 1^st second, 1 bit of memory is allocated to stick 1. The first stick now has 1 bit of available memory.
- At the 2^nd second, 2 bits of memory are allocated to stick 2. The second stick now has 0 bits of available memory.
- At the 3^rd second, the program crashes. The sticks have 1 and 0 bits available respectively.

Example 2:

Input: memory1 = 8, memory2 = 11
Output: [6,0,4]
Explanation: The memory is allocated as follows:
- At the 1^st second, 1 bit of memory is allocated to stick 2. The second stick now has 10 bit of available memory.
- At the 2^nd second, 2 bits of memory are allocated to stick 2. The second stick now has 8 bits of available memory.
- At the 3^rd second, 3 bits of memory are allocated to stick 1. The first stick now has 5 bits of available memory.
- At the 4^th second, 4 bits of memory are allocated to stick 2. The second stick now has 4 bits of available memory.
- At the 5^th second, 5 bits of memory are allocated to stick 1. The first stick now has 0 bits of available memory.
- At the 6^th second, the program crashes. The sticks have 0 and 4 bits available respectively.

Constraints:

0 <= memory1, memory2 <= 2³¹ - 1

Solution: Simulation

Time complexity: O(max(memory1, memory2)^0.5)
Space complexity: O(1)

Python3

class Solution:

def memLeak(self, memory1: int, memory2: int) -> List[int]:

for i in range(1, 2**30):

if max(memory1, memory2) < i:

return [i, memory1, memory2]

elif memory1 >= memory2:

memory1 -= i

else:

memory2 -= i

return None

花花酱 LeetCode 1854. Maximum Population Year

By zxi on May 8, 2021

You are given a 2D integer array logs where each logs[i] = [birth_i, death_i] indicates the birth and death years of the i^th person.

The population of some year x is the number of people alive during that year. The i^th person is counted in year x‘s population if x is in the inclusive range [birth_i, death_i - 1]. Note that the person is not counted in the year that they die.

Return the earliest year with the maximum population.

Example 1:

Input: logs = [[1993,1999],[2000,2010]]
Output: 1993
Explanation: The maximum population is 1, and 1993 is the earliest year with this population.

Example 2:

Input: logs = [[1950,1961],[1960,1971],[1970,1981]]
Output: 1960
Explanation: 
The maximum population is 2, and it had happened in years 1960 and 1970.
The earlier year between them is 1960.

Constraints:

1 <= logs.length <= 100
1950 <= birth_i < death_i <= 2050

Solution: Simulation

Time complexity: O(n*y)
Space complexity: O(y)

C++

// Author: Huahua

class Solution {

public:

int maximumPopulation(vector<vector<int>>& logs) {

vector<int> pop(2051);

for (const auto& log : logs) {

for (int y = log[0]; y < log[1]; ++y)

++pop[y];

}

int ans = -1;

int max_pop = 0;

for (int y = 1950; y <= 2050; ++y) {

if (pop[y] > max_pop) {

max_pop = pop[y];

ans = y;

}

return ans;

}

};