For this problem, if an divider has $$$k$$$ outlets, then it provides $$$k-1$$$ outlets since it has to plug into an already existing outlet. So in order to minimize the number of outlets we are using we can keep taking the divider with the largest number of outlets until the sum of their outlets ($$$-1$$$ for each divider) is above or equal to the number of students.

An edge case to be aware of is if the number of students is less or equal to 2, whereby we don't need any additional dividers.

Time Complexity: $$$O(nlgn)$$$ with normal sorting, $$$O(n + p)$$$ with counting sort ($$$p$$$ being $$$max(outlets)$$$).

This questions can generally be approached in two ways.

By starting at the front of the array, we can maintain a monotonic stack $$$s$$$ holds the students that are visible to Yisehak. Iterating over the students in the array, we will pop elements in the stack that are shorter than the current element (signifying that they are not visible to Yisehak because the current student will block them). Thus $$$s$$$ will be monotonically decreasing, and by the end the number of elements popped will be our answer.

By starting from the last element in the array, we only need to keep track of the tallest student we've seen so far, $$$t$$$, and a counter $$$c$$$. Iterating over the students, if the student's height is larger than $$$t$$$, we'll update $$$t$$$. If the student's height is smaller than $$$t$$$, we'll increment $$$c$$$. In the end, the answer will be $$$c$$$.

Time Complexity: O(n)

Space Complexity: O(n)

There are several different ways to approach the problem.

Binary Search Since the size of the matrix is relatively small (100x100), we can create an array of 101 arrays, $$$arr$$$, where $$$arr_i$$$ contains all the chairs that are in $$$i$$$-$$$th$$$ x coordinate in sorted order.

For example: For chairs on coordinates: [(1, 10), (1, 4), (2, 41), (1, 1), (2, 22), (3, 0)] then $$$arr$$$=[[], [1, 4, 10], [22, 41], [0], [], ...]. In this example, there are no chairs in $$$x=0$$$, 3 chairs in $$$x=1$$$ coordinate (at $$$y$$$ coordinates 1, 4, and 10), 2 chairs in $$$x=2$$$ (at $$$y$$$ coordinates 22, 41), and 1 chair in $$$x=3$$$ coordinate (at $$$y$$$ coordinate 0) and the rest have no chairs.

Once we have constructed $$$arr$$$, for every query, $$$sx_i$$$, $$$sy_i$$$, $$$ex_i$$$, $$$ey_i$$$, we will iterate from $$$arr_{sx_i}$$$ to $$$arr_{ex_i}$$$ and for each row, we'll use binary search to count y-coordinates between $$$sy_i$$$ and $$$ey_i$$$.

Time Complexity: O($$$nlgn + m*s*lg(s)$$$) $$$s$$$ being the size of the matrix (at worst 100)

Space Compexity: O($$$s + n$$$)

Prefix Matrix

This is a trivial implementation of a 2D Prefix Matrix. Read about it here.

Time Complexity: O($$$n + s^2 + m$$$)

Space Complexity: O($$$s^2$$$) $$$s$$$ being the size of the matrix (at worst 100)

Lazy Propagated 2D Segment Tree

This is also a trivial implementation of a 2D Segment Tree. It performs better when the size of the grid is bigger (not more optimal than prefix matrix in this case). When the grid size expands to $$$10^6 * 10^6$$$, we'd have to use lazy propagation to improve the space complexity. Read about it here or here.

Time Complexity: O($$$n(lgs)(lgs) + m(lgs)(lgs)$$$) $$$s$$$ being the size of the matrix (at worst 100)

Space Complexity: O($$$n(lgs)(lgs)$$$) with lazy propagation.

We'll have a multi-dimensional array $$$dp$$$ whereby:

$$$dp[i][p][q]$$$ holds the answer to the question, if we start from index $$$i$$$ with $$$p$$$ 100s and $$$q$$$ 200s, what's the minimum number of 50s required to distribute the stipend?

So therefore,

$$$dp[i][p][q] = min(1 + dp[i+1][p][q], dp[i+2][p-1][q], dp[i+4][p][q-1])$$$

By the end, check if $$$dp[0][b][c] \lt = a$$$ and if so, print ''YES'' else print ''NO''.

Note: For each of the terms, make sure that $$$i$$$, $$$p$$$, and $$$q$$$ are valid.

Time Complexity: O($$$n * b * c$$$)

Space Complexity: O($$$n * b * c$$$)

The important thing to note in this question is it's always optimal to go until the last day and then time travel back to the first day.

In order to prove this, let's assume there's another optimal option, $$$e_i$$$ and $$$s_i$$$, time-travelling from day $$$e_i$$$ to $$$s_i$$$. Therefore we can think of the array $$$p$$$=[$$$p_0$$$, ...., $$$p_{s_i}$$$, ...., $$$p_{e_i}$$$, $$$p_{s_i}$$$, ...., $$$p_{e_i}$$$, ...., $$$p_{n-1}$$$], and solve leave out the time travel aspect of the question. Note how we added [$$$p_{s_i}$$$, ...., $$$p_{e_i}$$$] after $$$p_{e_i}$$$ in the original array $$$p$$$.

Once we know this, we can append the contents of $$$p$$$ to $$$p$$$ and treat it like the buy and sell stock II question on Leetcode.

Time Complexity: O(n)

Space Complexity: O(n)