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)$$$).

public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        int t = sc.nextInt(); 
        for(int i = 0; i < t; i++){
           int n = sc.nextInt();
           int m = sc.nextInt();
           
           ArrayList<Integer> outlets = new ArrayList<>();
           for (int j = 0; j < m; j++){
               outlets.add(sc.nextInt());
           } 
           
           outlets.sort((i1, i2) -> i2 - i1);
           int current = 2;
           int j;
           for (j = 0; j < m && current < n; j++){
               current += outlets.get(j) - 1;
           }
           if (current < n) {
                out.println(-1);
           } else {
               out.println(j);
           }
        }
        out.close();
}

Good problem:

Ok problem:

Bad problem:

Did not attempt:

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)

n = int(input())

for i in range(n):
    input()
    nums = list(map(int, input().split()))
    stack = []
    count = 0
    for num in nums:
        while stack and stack[-1] < num:
            stack.pop()
            count += 1
        stack.append(num)
    print(count)

Good problem:

Ok problem:

Bad problem:

Did not attempt:

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.

# Prefix matrix
n, m = list(map(int, input().split()))
end = 101
original = [[0 for i in range(end)] for j in range(end)]

for i in range(n):
    x, y = list(map(int, input().split()))
    original[x + 1][y + 1] += 1

queries = [list(map(int, input().split())) for _ in range(m)]

prefix = [[0 for i in range(end)] for j in range(end)]

for i in range(end):
    count = 0
    for j in range(end):
        count += original[i][j]
        prefix[i][j] += count

for j in range(end):
    count = 0
    for i in range(end):
        prefix[i][j] += count
        count = prefix[i][j]

for sx, sy, ex, ey in queries:
    print(prefix[ex + 1][ey + 1] - prefix[ex + 1][sy] - prefix[sx][ey + 1] + prefix[sx][sy])

    

# Segment Tree
class Node:
    def __init__(self, val = 0, left = None, right = None) -> None:
        self.val = val
        self.left = left
        self.right = right


def add_to_y(node, start, end, val):
    if not node:
        node = Node()
    node.val += 1
    if start == end:
        return node
    elif val > (start + end) // 2:
        node.right = add_to_y(node.right, ((start + end) // 2) + 1, end, val)
    else:
        node.left = add_to_y(node.left, start, (start + end) // 2, val)
    return node

def add_to_tree(node, start, end, val_x, val_y):
    if not node:
        node = Node(None)
    node.val = add_to_y(node.val, START, END, val_y)
    if start == end:
        return node
    elif val_x > (start + end) // 2:
        node.right = add_to_tree(node.right, ((start + end) // 2) + 1, end, val_x,  val_y)
    else:
        node.left = add_to_tree(node.left, start, (start + end) // 2, val_x, val_y)
    return node

def get_y_range(node, start, end, val_start, val_end):
    if not node:
        return 0
    if start == val_start and end == val_end:
        return node.val
    result = 0
    if val_end > (start + end) // 2:
        result += get_y_range(node.right, ((start + end) // 2) + 1, end, max(((start + end) // 2) + 1, val_start), val_end)
    if val_start <= (start + end) // 2:
        result += get_y_range(node.left, start, (start + end) // 2, val_start, min((start + end) // 2, val_end))
    return result

def get_x_range(node, start, end, x_start, x_end, y_start, y_end):
    if not node:
        return 0
    if start == x_start and end == x_end:
        return get_y_range(node.val, START, END, y_start, y_end)
    result = 0
    if x_end > (start + end) // 2:
        result += get_x_range(node.right, ((start + end) // 2) + 1, end, max(((start + end) // 2) + 1, x_start), x_end, y_start, y_end)
    if x_start <= (start + end) // 2:
        result += get_x_range(node.left, start, (start + end) // 2, x_start, min((start + end) // 2, x_end), y_start, y_end)
    return result

START = 0
END = 1 << 7
start_node = Node(None)
n, m = list(map(int, input().split()))

chairs = [list(map(int, input().split())) for i in range(n)]
for cx, cy in chairs:
    add_to_tree(start_node, START, END, cx, cy)


queries = [list(map(int, input().split())) for _ in range(m)]
for sx, sy, ex, ey in queries:
    print(get_x_range(start_node, START, END, sx, ex, sy, ey))

Good problem:

Ok problem:

Bad problem:

Did not attempt:

For this problem, we have to traverse the graph while keeping track of the current bandwidth and whenever we find an opening for Kidus to connect to, we'll check if that is the best bandwidth for him. Either DFS or BFS would work for this question, but for this tutorial we'll only look at the BFS solution.

For the BFS approach, we can treat all the routers and hotspots as nodes. We'll start by adding all of the routers to the queue with the state (router_index, router_bandwidth). For each node (node_ind, curr_bandwidth) we pop, we do the following:

• If children[node_ind] < capacity, then compare curr_bandwidth / (len(children[node_ind]) + 1) with the current maximum bandwidth that Kidus can connect to.
  • If it is greater than the current maximum bandwidth, then store node_ind and update the maximum bandwidth
• Add all the children of node_ind to the queue with state (child_ind, curr_bandwidth / len(children[node_ind]))

By the end of the iteration, return the node_ind with the maximum bandwidth. If there isn't any then return -1.

Time Complexity: O(n + m)

Space Complexity: O(n + m)

# BFS approach
from collections import deque


n, m = list(map(int, input().split()))

graph = [[] for i in range(n + m)]
speeds = []
capacities = []
for i in range(n):
    c, s = list(map(int, input().split()))
    speeds.append(s)
    capacities.append(c)

for i in range(m):
    c, p = list(map(int, input().split()))
    graph[p].append(i + n)
    capacities.append(c)

best_speed = best_node = -1

q = deque([(i, speeds[i]) for i in range(n)])
while q:
    node, curr_speed = q.popleft()
    if len(graph[node]) < capacities[node] and curr_speed // (len(graph[node]) + 1) > best_speed:
        best_speed = curr_speed // (len(graph[node]) + 1)
        best_node = node
    for child in graph[node]:
        q.append((child, curr_speed // len(graph[node])))
print(best_node)

Good problem:

Ok problem:

Bad problem:

Did not attempt:

Try to get rid of the idea of time travel and think of it as a different array depending on which day Segni jumps to and from. If Segni is time-travelling from day $$$e_i$$$ to $$$s_i$$$ $$$(e_i \gt s_i)$$$, 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 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$$$.

Greedy

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 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$$$.

If $$$e_i$$$ is not the last day, let's see the consequence of moving $$$e_i$$$ to $$$e_i + 1$$$. This is the same as adding $$$p_{e_{i+1}}$$$ after $$$p_{e_i}$$$ in our modified array. This makes our new modified array $$$p$$$=[$$$p_0$$$, ...., $$$p_{s_i}$$$, ...., $$$p_{e_i}$$$, $$$p_{e_{i+1}}$$$, $$$p_{s_i}$$$, ...., $$$p_{e_i}$$$, ...., $$$p_{n-1}$$$]. We can show that with the greedy approach we can get the same answer or an even better answer with the addition of $$$p_{e_{i+1}}$$$ to the array. We can prove the same from moving $$$s_i$$$ one step back. And with this we show that setting $$$s_i = 0$$$ $$$e_i = n - 1$$$ will yield an optimal answer.

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)

n = int(input())

prices = list(map(int, input().split()))

# The important part
prices += prices

best_price = 10 ** 4
profit = 0

for price in prices:
    if price < best_price:
        best_price = price
    else:
        profit += price - best_price
        best_price = price
print(profit)

Good problem:

Ok problem:

Bad problem:

Did not attempt:

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$$$)

// Bottom up dp
public static void main(String[] args){
    MyScanner sc = new MyScanner();
    var out = new PrintWriter(new BufferedOutputStream(System.out));
    int n = sc.nextInt(), m = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
    
    int[] friends = new int[n];
    Arrays.fill(friends, 1 << 4);

    for (int i = 0; i < m; i++){
        int x = sc.nextInt(), y = sc.nextInt();
        if (y - x < 4){
            friends[x] |= 1 << ((x - y) + 4);
            friends[y] |= 1 << ((y - x) + 4);
        }
    }
    // dp[i][p][q] = if we start from index i with p 100s and q 200s, what's the minimum number of 50s required to distribute the stipend
    // dp[i][p][q] = min(1 + dp[i+1][p][q], dp[i+2][p-1][q], dp[i+4][p][q-1]) if valid for each expression in min
    int[][][] dp = new int[friends.length+1][b+1][c+1];
    int next = 1 << 3, prev = 1 << 5, all = (1 << 5) - 2;
    for (int[] row : dp[friends.length - 1])
        Arrays.fill(row, 1);
    
    for (int i = friends.length - 2; i >= 0; i--){
        for(int p = 0; p <= b; p++){
            for (int q = 0; q <= c; q++){
                int ans = 1 + dp[i+1][p][q];
                if (p > 0 && ((next & friends[i]) != 0 || (prev & friends[i+1]) != 0)){
                    ans = Math.min(ans, dp[i+2][p-1][q]);
                } 
                int curr = all;
                if (q != 0){
                    for (int k = 0; k < 4; k++){
                        if ((i + k < friends.length) && (friends[i+k] & curr) == curr){
                            ans = Math.min(ans, dp[Math.min(friends.length, i + 4)][p][q - 1]);
                            break;
                        }
                        curr <<= 1;
                    }
                }
                dp[i][p][q] = ans;
            }
        }
    }
    

    if (dp[0][b][c] <= a){
        out.println("YES");
    } else {
        out.println("NO");
    }
    out.close();
}

Good problem:

Ok problem:

Bad problem:

Did not attempt:

For this solution, we iterate over the array $$$a$$$ and maintain a few data structures. Here are the values that each data structure will hold at index $$$i$$$ which are:

• running sum: an integer that holds the current sum of all the numbers until index $$$i$$$, $$$modulo$$$ $$$k$$$.

• $$$first$$$: an array of size $$$k$$$ of which the $$$j$$$-$$$th$$$ index holds the index of the first instance where the $$$running$$$ $$$sum = j$$$.

• $$$running$$$ $$$window$$$: an integer that holds the longest subarray that's divisible by $$$k$$$ without jump. You can calculate it for index $$$i$$$ by comparing $$$i - first[running$$$ $$$sum]$$$ with the current $$$running$$$ $$$window$$$ and updating it if necessary.

• The next two arrays are very closely related:

  • $$$best$$$ $$$before$$$: an array of size $$$k$$$ of which the $$$j$$$-$$$th$$$ index holds the $$$running$$$ $$$window$$$ right before index $$$best[j]$$$.
  • $$$best$$$: an array of size $$$k$$$ that holds the best index to have a subarray after a gap in order to get the largest total length. $$$best[j]$$$ is initially set to $$$first[j]$$$ and for index $$$i$$$, $$$best[i]$$$ is updated if

running window > i - best[running sum] + best before[running sum]

• and it is updated to:

$$$best[running$$$ $$$sum] = i$$$

$$$best$$$ $$$before[running$$$ $$$sum] = running$$$ $$$window$$$

• $$$result$$$: is an integer that holds the longest subarray that' divisible by $$$k$$$ with gap. It is initialized to 0 and is updated at index $$$i$$$ as:

  • $$$result = max(result, i - best[running$$$ $$$sum] + best$$$ $$$before[running$$$ $$$sum]) $$$

By the end of the iteration, the answer is going to be $$$max(result, running$$$ $$$window)$$$.

Time Complexity: O(n + k)

Space Complexity: O(k)

n, k = list(map(int, input().split()))

nums = list(map(int, input().split()))

first = [-2] * k
extra, best = first[:], first[:]

first[0] = best[0] = -1
extra[0] = running_best = running_sum = best_with_gap = 0

for i, num in enumerate(nums):
    running_sum = (running_sum + num) % k
    if first[running_sum] == -2:
        first[running_sum] = best[running_sum] = i
        extra[running_sum] = running_best
    else:
        best_with_gap = max(best_with_gap, i - best[running_sum] + extra[running_sum])
        if running_best > i - best[running_sum] + extra[running_sum]:
            best[running_sum] = i
            extra[running_sum] = running_best
        if i - first[running_sum] > running_best:
            running_best = i - first[running_sum]
    
print(max(best_with_gap, running_best))

Good problem:

Ok problem:

Bad problem:

Did not attempt: