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(1) (constant additional space)

We can also use DP to solve this question: written by seraph14

Let's forget about going back in time for now. For each stock prices we have a choice either to buy or sell with the current price. Assuming that we can't sell if we've not bought before and vice versa. Which is the same as this problem https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ This can be solved using dynamic programming.

The recurrence relation will be

dp(True, i) = max(-p[i] + dp(False, i+1), dp(True, i+1))
dp(False, i) = max(p[i] + dp(True, i+1), dp(False, i+1))

• the boolean is for whether we can buy or sell with the $$$i$$$-$$$th$$$ price

Given p = [p1, p2, p3, ....,pn-1, pn] Let's say the best solution is to buy till $$$(n-1)_{th}$$$ and go back in time to $$$2_{th}$$$. If we modify our prices array to [p1, p2, p3, ....,pn-1, p2, p3, ....,pn-1, pn], this is basically the same problem as the above.

More generally, the modified prices array is np = [p1, p2, p3, ....,pn-1, pn, p1, p2, p3, ....,pn-1, pn] In the end, the answer will be in dp(True, 0).

Time Complexity: O(n)

Space Complexity: O(n)

#greedy solution
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)

# with DP
n = input()
p = list(map(int, input().split()))
p += p
dp = [[0] * (n*2+1) for _ in range(2)]
for i in reversed(range(n*2)):
    dp[True][i] = max(-p[i] + dp[False][i+1], dp[True][i+1])
    dp[False][i] = max(p[i] + dp[True][i+1], dp[False][i+1])
print(dp[True][0])

# DP Solution

def best_profit(prices):
    memo = [[-float('inf'), 0]]
    for price in prices:
        memo.append(memo[-1].copy())
        memo[-1][0] = max(memo[-1][0], memo[-2][1] - price)
        memo[-1][1] = max(memo[-1][1], memo[-2][0] + price)
    best = memo[-1][1]
    
    memo2 = [[0, -float('inf')]]
    for price in prices[::-1]:
        memo2.append(memo2[-1].copy())
        memo2[-1][0] = max(memo2[-1][0], memo2[-2][1] - price)
        memo2[-1][1] = max(memo2[-1][1], memo2[-2][0] + price)
    memo2 = memo2[::-1]
    
    bought, sold = memo[-1]
    for i, price in enumerate(prices):
        best = max(best, bought + price + memo2[i + 1][0], sold + memo2[i][0])
    return best


if __name__ == "__main__":
    _, inputs = input(), list(map(int, input().split()))
    print(best_profit(inputs))

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. To check if 2 students are friends, you can convert the pair list into a set and check the existence of $$$i$$$, $$$i+1$$$. You can check brute force if a group of 4 students are friends (check if each one is friends with the other 3).

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 && (i + 4 < friends.length)){
                    for (int k = 0; k < 4; k++){
                        if ((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:

There are two approaches we can use, the simpler one is presented first:

For this solution, we will need two arrays: - best until: an array of size $$$n$$$, which holds the length of the longest subarray until (but not including) index $$$i$$$. - best after: an array of size $$$n$$$, which holds the length of the longest subarray after (not including) index $$$i$$$. In order to obtain best until, we'll iterate over the array and keep track of inds, the earliest index where sum % k == p. For best until[j] if the sum until j is p, then best until[j] = max(best until[j - 1], j - inds[p]). best after is the same but in reverse.

In the end, the answer will be the maximum among best until[i] + best after[i] for all $$$i$$$.

Time complexity: O(n)

Space complexity: O(n)

There is also a one pass solution, although it's a bit more complicated. 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 j = running sum, best[j] 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)

# multiple pass solution
def longest_div(arr, k):
        count_dict = {0:-1}
        ans = [0]
        total = curr = 0
        for ind, value in enumerate(arr):
            total = (total + value) % k
            if total not in count_dict:
                count_dict[total] = ind
            curr = max(curr, ind - count_dict[total])
            ans.append(curr)
        return ans

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

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

front = longest_div(nums, k)
back = longest_div(nums[::-1], k)[::-1]

print(max(map(sum, zip(front, back))))

# one pass solution
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: