Since $$$m$$$ only needs to be between $$$1$$$ and $$$1000$$$, can we just guess values for $$$m$$$ and check if $$$n \cdot m + 1$$$ is composite? Alternatively, is there an algebraic way to force the expression to become a perfect square?

There are two highly effective ways to solve this problem:

Approach 1: Brute Force Since the constraints are extremely small ($$$n \le 1000$$$ and we only need $$$m \le 1000$$$), the maximum number we will ever check is $$$1000 \times 1000 + 1 \approx 10^6$$$. We can simply loop $$$m$$$ from 1 to 1000, calculate $$$val = n \cdot m + 1$$$, and check if $$$val$$$ is prime in $$$O(\sqrt{val})$$$ time. The first $$$m$$$ that yields a composite number is our answer.

Approach 2: $$$O(1)$$$ Math (Forcing a Square) If we can make $$$n \cdot m + 1$$$ equal to a perfect square like $$$(n-1)^2$$$, it will definitely be composite. $$$(n - 1)^2 = n^2 - 2n + 1$$$ Setting them equal: $$$n \cdot m + 1 = n^2 - 2n + 1 \implies n \cdot m = n^2 - 2n \implies m = n - 2$$$. So, for any $$$n \gt 2$$$, $$$m = n - 2$$$ is a guaranteed $$$O(1)$$$ answer. For the special cases $$$n=1$$$ and $$$n=2$$$, we can just output $$$m=3$$$ and $$$m=4$$$ respectively.

• Time Complexity: $$$O(m \sqrt{nm})$$$ for brute force, or $$$O(1)$$$ for math.
• Space Complexity: $$$O(1)$$$

import sys

def is_prime(x):
    if x <= 1:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

def solve():
    n = int(sys.stdin.read().strip())
    
    # Approach 1: Brute Force
    for m in range(1, 1001):
        if not is_prime(n * m + 1):
            print(m)
            break
            
    # Approach 2 (O(1) Math Alternative):
    # if n == 1: print(3)
    # elif n == 2: print(4)
    # else: print(n - 2)

if __name__ == "__main__":
    solve()

You can solve this using pure coordinate geometry based on how chess pieces move, or you can model the chessboard as an unweighted graph and use Breadth-First Search (BFS) to find the shortest path layer by layer.

Approach 1: O(1) Geometry * Rook: Moves in straight lines. If it shares a row or column with the target, 1 move. Otherwise, 2 moves. * Bishop: Moves diagonally. Squares on the same diagonal share either $$$r+c$$$ or $$$r-c$$$. If parities $$$(r1+c1) \pmod 2 \neq (r2+c2) \pmod 2$$$, the target is unreachable (0). If it's on the exact same diagonal, 1 move. Otherwise, 2 moves. * King: Can move in all 8 directions. The shortest path is the Chebyshev distance: $$$\max(|r1-r2|, |c1-c2|)$$$.

Approach 2: Shortest Path (BFS) Since a chessboard is a small $$$8 \times 8$$$ grid, we can represent it as an unweighted graph where edges are the legal moves of a piece. By pushing the starting coordinate into a queue and exploring level-by-level, BFS mathematically guarantees that the first time we hit the target square, we have found the absolute minimum number of moves. We just define three different "move generators" (neighbors) for each piece and run standard BFS.

• Time Complexity: $$$O(1)$$$ for math, $$$O(V+E)$$$ (which is at most 64) for BFS.
• Space Complexity: $$$O(1)$$$ for math, $$$O(V)$$$ for BFS queue and visited set.

from collections import deque
import sys

def bfs(start, target, get_moves):
    if start == target:
        return 0
    
    queue = deque([(start[0], start[1], 0)])
    visited = {start}
    
    while queue:
        r, c, dist = queue.popleft()
        if (r, c) == target:
            return dist
            
        for nr, nc in get_moves(r, c):
            if (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))
    return 0

def solve():
    r1, c1, r2, c2 = map(int, sys.stdin.read().split())
    start, target = (r1, c1), (r2, c2)
    
    # Move generators
    def rook_moves(r, c):
        return [(r, i) for i in range(1, 9) if i != c] + [(i, c) for i in range(1, 9) if i != r]
        
    def bishop_moves(r, c):
        moves = []
        for dr, dc in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
            nr, nc = r, c
            while 1 <= nr + dr <= 8 and 1 <= nc + dc <= 8:
                nr += dr; nc += dc
                moves.append((nr, nc))
        return moves
        
    def king_moves(r, c):
        dirs = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
        return [(r+dr, c+dc) for dr, dc in dirs if 1 <= r+dr <= 8 and 1 <= c+dc <= 8]

    print(bfs(start, target, rook_moves), bfs(start, target, bishop_moves), bfs(start, target, king_moves))

if __name__ == "__main__":
    solve()

Think of the students as nodes and shoelaces as edges. We are looking for "leaves" (nodes with exactly 1 edge). How can we simulate removing all leaves simultaneously, layer by layer?

This is a graph simulation problem that introduces the concept of graph peeling.

We can store the graph using an array of sets to allow for $$$O(1)$$$ removal of edges. At each iteration (representing a reprimand phase): 1. Scan all nodes to find those with exactly 1 connection (len(adj[i]) == 1). 2. If we find no such nodes, the process stops. 3. If we find them, store them in a temporary list. We must gather them all first before kicking them out so we don't accidentally remove a chain sequentially in one step. 4. Iterate through our temporary list, remove the student from their neighbor's set, and clear the student's set. 5. Increment our groups kicked counter and repeat.

• Time Complexity: $$$O(n^3)$$$ worst-case if using lists, but $$$O(n^2)$$$ using sets to remove edges. Given $$$n \le 100$$$, this is incredibly fast.
• Space Complexity: $$$O(n + m)$$$ to store the graph.

from collections import defaultdict

n, m = map(int, input().split())
graph = defaultdict(list)
degree = [0] * n
for _ in range(m):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    graph[u].append(v)
    graph[v].append(u)
    degree[u] += 1
    degree[v] += 1

removed = [False] * n
cnt = 0

leaves = [i for i in range(n) if degree[i] == 1 and not removed[i]]
while leaves:
    cnt += 1
    for node in leaves:
        removed[node] = True
    for node in leaves:
        for neighbor in graph[node]:
            degree[neighbor] -= 1
    leaves = [i for i in range(n) if degree[i] == 1 and not removed[i]]

print(cnt)

Because $$$k$$$ can be up to $$$2 \cdot 10^5$$$, peeling the graph manually like in the previous problem will cause a Time Limit Exceeded (TLE) error. How can we use a queue to track the "peeling layers" efficiently, similar to Topological Sorting?

This requires Multi-source BFS (a variation of Kahn's Algorithm for Topological Sort). Instead of searching the whole graph repeatedly, we push the work strictly inward from the leaves.

1. Initialize: Create an array rem to track the degree of each node. Find all initial leaves (rem[v] <= 1) and push them into a queue. Record their "deletion layer" as 1 in a layer array.
2. Process: While the queue is not empty, pop a node $$$u$$$. For every neighbor $$$v$$$, simulate the removal of $$$u$$$ by decreasing rem[v] by 1.
3. Queue new leaves: If $$$v$$$'s remaining degree drops exactly to 1, it has just become a leaf! Its deletion layer will be layer[v] = layer[u] + 1. Push $$$v$$$ into the queue.
4. Count Answer: After the queue is empty, the graph has been fully peeled. The surviving nodes are simply those where layer[v] > k.

• Time Complexity: $$$O(V + E)$$$ where $$$V = n$$$ and $$$E = n - 1$$$. Each node and edge is processed at most twice.
• Space Complexity: $$$O(V)$$$ for adjacency list, queue, and degree/layer arrays.

import sys
from collections import deque

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
        
    t = int(input_data[0])
    ptr = 1
    
    out = []
    for _ in range(t):
        n = int(input_data[ptr])
        k = int(input_data[ptr+1])
        ptr += 2
        
        if n == 1:
            # Special case: single node is removed on layer 1
            out.append("0" if k >= 1 else "1")
            continue
            
        adj = [[] for _ in range(n + 1)]
        rem = [0] * (n + 1)
        layer = [0] * (n + 1)
        
        for _ in range(n - 1):
            u, v = int(input_data[ptr]), int(input_data[ptr+1])
            adj[u].append(v)
            adj[v].append(u)
            rem[u] += 1
            rem[v] += 1
            ptr += 2
            
        queue = deque()
        for i in range(1, n + 1):
            if rem[i] == 1:
                queue.append(i)
                layer[i] = 1
                
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if rem[v] != 1:
                    rem[v] -= 1
                    if rem[v] == 1:
                        layer[v] = layer[u] + 1
                        queue.append(v)
                        
        ans = sum(1 for i in range(1, n + 1) if layer[i] > k)
        out.append(str(ans))
        
    print("\n".join(out))

if __name__ == "__main__":
    solve()

Consider rooks as directed edges in a graph where an edge goes from the rook's column to its row ($$$x \to y$$$). How does the presence of cycles in this graph affect the number of moves needed to place them on the main diagonal?

Because no rooks share a row or column, every node in our graph has an in-degree of at most 1 and an out-degree of at most 1. This means the graph decomposes perfectly into disjoint paths, cycles, and loops.

Moving a rook to the diagonal $$$(v \to v)$$$ is equivalent to turning its edge into a self-loop. * Loops: Already on the diagonal. Cost = 0 moves. * Paths: We can resolve them starting from the endpoint without conflicts. A path of $$$k$$$ rooks takes exactly $$$k$$$ moves. * Cycles: To resolve a cycle, we must temporarily move one rook off its intended target into an empty row/col to unblock the others. This breaks the cycle into a path, wasting exactly 1 extra move. A cycle of $$$k$$$ rooks takes $$$k + 1$$$ moves.

Therefore, the total optimal moves is: Total Rooks $$$-$$$ (Rooks already on diagonal) $$$+$$$ (Number of Cycles)

We can count cycles easily using a 3-state graph traversal (0: unvisited, 1: visiting, 2: processed).

• Time Complexity: $$$O(n)$$$. Each node is visited and backtracked exactly once.
• Space Complexity: $$$O(n)$$$ for the adjacency array and visited states.

import sys

# Increase recursion depth just in case, though iterative is used below
sys.setrecursionlimit(200000)

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
        
    t = int(input_data[0])
    ptr = 1
    
    out = []
    for _ in range(t):
        n = int(input_data[ptr])
        m = int(input_data[ptr+1])
        ptr += 2
        
        adj = [0] * (n + 1)
        moves = 0
        
        for _ in range(m):
            u, v = int(input_data[ptr]), int(input_data[ptr+1])
            ptr += 2
            if u == v:
                continue
            adj[u] = v
            moves += 1
            
        vis = [0] * (n + 1)
        cycles = 0
        
        for i in range(1, n + 1):
            if adj[i] != 0 and vis[i] == 0:
                curr = i
                # Traverse current path
                while curr != 0 and vis[curr] == 0:
                    vis[curr] = 1
                    curr = adj[curr]
                    
                # Cycle detected
                if curr != 0 and vis[curr] == 1:
                    cycles += 1
                    
                # Backtrack and mark as processed (State 2)
                curr = i
                while curr != 0 and vis[curr] == 1:
                    vis[curr] = 2
                    curr = adj[curr]
                    
        out.append(str(moves + cycles))
        
    print("\n".join(out))

if __name__ == "__main__":
    solve()

What kind of grouping makes the sum of squares smallest: one big group or many small balanced groups?

Since every group must contain at least 2 numbers, the best choice is to make every group contain exactly 2 numbers.

If a group has more than 2 numbers, splitting it into smaller groups decreases the total cost because the square function is convex. So the problem becomes pairing the numbers.

To minimize

[ \sum (s_j)^2 ]

we should pair the smallest number with the largest number, the second smallest with the second largest, and so on.

So the steps are:

• sort the array

• use two pointers

• pair nums[l] with nums[r]

• add ((nums[l] + nums[r])^2) to the answer

• Time Complexity: (O(n \log n))

• Space Complexity: (O(1))

m = int(input().strip())
arr = list(map(int, input().split()))

def solve(m, arr):
    arr.sort()
    total = 0

    left, right = 0, m - 1

    while left <= right:
        total += (arr[left] + arr[right]) ** 2
        left += 1
        right -= 1

    return total

print(solve(m, arr))

After sorting, which player gets the 1st, 2nd, 3rd, ... largest items in optimal play?

If the array is sorted in descending order, then optimal play is simple: - Eve takes the 1st, 3rd, 5th, ... largest elements - Noah takes the 2nd, 4th, 6th, ... largest elements

So the initial score is the difference between consecutive pairs in the sorted order.

Noah can increase some values with total budget at most k.
The best way is to use this budget on Noah’s picked elements so that they become as large as possible, but only up to the previous Eve element in the pair. Any extra increase beyond that does not help the score.

So: - sort descending - compute Eve’s sum and Noah’s sum - for every Noah element, use as much remaining k as possible to close the gap with the previous element - print the final score

• Time Complexity: (O(n \log n))
• Space Complexity: (O(1))

test_cases = int(input().strip())

for _ in range(test_cases):
    size, budget = map(int, input().split())
    values = list(map(int, input().split()))

    eve_sum = 0
    noah_sum = 0

    values.sort()
    previous = None

    for idx, value in enumerate(values[::-1]):
        if idx % 2 == 0:
            eve_sum += value
        else:
            gain = min(budget, previous - value)
            budget -= gain
            noah_sum += value + gain
        previous = value

    print(eve_sum - noah_sum)

When is the labeling impossible?

First, count how many times each value appears.

If some value appears more than k times, then it is impossible, because equal values cannot share the same label and there are only k labels.

Otherwise, the construction is easy:

• sort the values together with their indices
• assign labels cyclically from 1 to k

This works because:

• equal values appear at most k times, so they get different labels

• every label is used at least once

• Time Complexity: (O(n \log n))

• Space Complexity: (O(n))

from collections import defaultdict

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

def solve(n, k, sequence):
    freq = defaultdict(int)

    for x in sequence:
        freq[x] += 1

    for cnt in freq.values():
        if cnt > k:
            return []

    indexed = []
    for pos, val in enumerate(sequence):
        indexed.append([val, pos])

    indexed.sort()

    label = 1
    for val, pos in indexed:
        sequence[pos] = label
        label += 1
        if label > k:
            label = 1

    return sequence

answer = solve(n, k, sequence)

if answer:
    print("YES")
    print(*answer)
else:
    print("NO")

What should we do when the MEX is already inside the array, and what should we do when it is not?

We repeatedly use the MEX operation to make the array non-decreasing.

The greedy idea is: - If mex < n, then set a[mex] = mex. This fixes one position directly. - If mex == n, then there is no missing value among 0..n-1, so the array still has some wrong position. In that case, choose the first index where a[i] != i and set it to n.

This guarantees progress every time.

We stop once the array becomes non-decreasing, and the number of operations is always at most 2n.

• Time Complexity: (O(n^2)) in the straightforward implementation
• Space Complexity: (O(n))

test_cases = int(input().strip())

for _ in range(test_cases):
    n = int(input().strip())
    array = list(map(int, input().split()))

    def is_sorted(arr):
        for i in range(1, len(arr)):
            if arr[i] < arr[i - 1]:
                return False
        return True

    def mex_value(arr, n):
        present = set(arr)
        for x in range(n + 1):
            if x not in present:
                return x

    def first_wrong(arr):
        for i in range(n):
            if arr[i] != i:
                return i

    ops = []
    for _ in range(2 * n):
        if is_sorted(array):
            break

        mex = mex_value(array, n)

        if mex < n:
            array[mex] = mex
            ops.append(mex + 1)
        else:
            pos = first_wrong(array)
            array[pos] = mex
            ops.append(pos + 1)

    print(len(ops))
    print(*ops)

If we fix how many catamarans we take, how do we choose the best kayaks?

We have two types of vehicles: - kayaks with volume 1 - catamarans with volume 2

We want the maximum total carrying capacity without exceeding the truck volume v.

The greedy idea is:

• separate kayaks and catamarans
• sort each list by capacity in descending order
• build prefix sums for both lists

Then try every possible number of catamarans:

• if we take c catamarans, they use 2c volume

• the remaining volume can be filled with the best kayaks

• compute the total capacity and keep the maximum

• Time Complexity: (O(n \log n))

• Space Complexity: (O(n))

import sys

def solve():
    input = sys.stdin.readline
    n, capacity = map(int, input().split())

    small_boats = []
    big_boats = []

    for idx in range(1, n + 1):
        boat_type, boat_power = map(int, input().split())
        if boat_type == 1:
            small_boats.append((boat_power, idx))
        else:
            big_boats.append((boat_power, idx))

    small_boats.sort(reverse=True)
    big_boats.sort(reverse=True)

    pref_small = [0]
    for power, _ in small_boats:
        pref_small.append(pref_small[-1] + power)

    pref_big = [0]
    for power, _ in big_boats:
        pref_big.append(pref_big[-1] + power)

    best_score = 0
    best_big = 0
    best_small = 0

    max_big = min(len(big_boats), capacity // 2)

    for cnt_big in range(max_big + 1):
        used_space = 2 * cnt_big
        remaining = capacity - used_space
        cnt_small = min(len(small_boats), remaining)
        current_score = pref_big[cnt_big] + pref_small[cnt_small]

        if current_score > best_score:
            best_score = current_score
            best_big = cnt_big
            best_small = cnt_small

    chosen = []
    for i in range(best_big):
        chosen.append(big_boats[i][1])
    for i in range(best_small):
        chosen.append(small_boats[i][1])

    print(best_score)
    print(*chosen)

if __name__ == "__main__":
    solve()

Since we can only utilize either the length or width of all the blankets, the best choice for creating the longest possible rope is to first utilize all the blankets and use the longest side (length or width) of each blanket.

• Time Complexity: $$$O(n)$$$
• Space Complexity: $$$O(1)$$$

import sys
input = lambda : sys.stdin.readline().strip()


for _ in range(int(input())):
    n, h = map(int, input().split())
   
    rope = 0
    for i in range(n):
        l, w = map(int, input().split())
        rope += max(l, w)
   
    if rope >= h:
        print('YES')
    else:
        print('NO')

Output binary search.

The key insight is that if we have a wagon size greater than or equal to $$$\max(d_1, d_2, \dots, d_n)$$$, we only need to go once for every village. Hence, the sum of all $$$a_i$$$ is the minimum achievable time to deliver the water with any size.

If $$$\sum_{i=1}^{n} a_i$$$ is already greater than $$$k$$$, we can't make Empress Taytu happy with any size. If not, starting from 1 (left) up to $$$\max(d_1, d_2, \dots, d_n)$$$ (right), we can perform a binary search by checking whether it's achievable with a given size within $$$k$$$ hours.

For a single village, we can calculate the number of trips the wagon has to make by ceil dividing its demand by the wagon size. Then, we can calculate the total time needed for one village by multiplying the number of trips with the time it takes for one trip ($$$a_i$$$). After adding the total time for all villages, we will check if it is less than or equal to $$$k$$$. Overall, the complexity of the checker is $$$O(n)$$$.

The complexity of the binary search algorithm used in this solution is $$$O(\log(\max(d_1, d_2, \dots, d_n)))$$$. Since we need to check for each possible size of the wagon, the overall complexity of the algorithm is $$$O(n \log m)$$$, where $$$m = \max(d_1, d_2, \dots, d_n)$$$.

• Space Complexity: $$$O(1)$$$

from math import ceil
from sys import stdin


def input(): return stdin.readline().strip()

T = int(input())
for _ in range(T):
    N, K = map(int, input().split())
    d = list(map(int, input().split()))
    a = list(map(int, input().split()))

    if sum(a) > K:
        print(-1)
        continue

    def checker(size):
        time = 0
        for i in range(N):
            time += ceil(d[i]/size)*a[i]
        return time <= K
    
    left = 1
    right = max(d)
    while left <= right:
        mid = left + (right - left)//2
        if checker(mid):
            right = mid - 1
        else:
            left = mid + 1
    print(left)

Observation: After an increment operation, there is always a corresponding decrement operation.

Let's represent the characters with numerical values, such as their ASCII values. During an increment operation, the ASCII value of that character increases by $$$1$$$, and during a decrement operation, it decreases by $$$1$$$. Importantly, after an increment operation, the total sum of ASCII values of the word decreases by $$$1$$$, and after a decrement operation, the total sum increases by $$$1$$$. However, since one operation combines both increment and decrement, the total ASCII sum remains unchanged.

Therefore, to decrypt the message, we only need to check if there exists a substring with a size equal to the size of the sensitive word (let's denote it as $$$m$$$) and the sum of ASCII values of its characters is equal to that of the sensitive word. For this, we can employ a fixed-size sliding window approach with size $$$m$$$.

• Time Complexity: $$$O(n)$$$ where $$$n$$$ is the size of the decrypted message.
• Space Complexity: $$$O(1)$$$

from sys import stdin


def input(): return stdin.readline().strip()

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    s = input()
    w = input()

    target = 0
    window_sum = 0
    for i in range(M):
        target += ord(w[i])
        window_sum += ord(s[i])
    
    found = False
    for i in range(M, N):
        if window_sum == target:
            found = True
            break
        window_sum += ord(s[i])
        window_sum -= ord(s[i - M])
    
    if window_sum == target or found:
        print("YES")
    else:
        print("NO")

In the first round, each group consists of two teams. Then, in the second round, every two consecutive groups are merged, and so on. This problem resembles a typical divide and conquer approach. Now, the question is, given the left group and the right group, how can we merge them and calculate the number of wins for every team efficiently?

One possible solution is to perform a binary search on the right team for each team in the left group, determining the number of players with strength strictly less than the current player's strength. Repeat this process for all players in the right group. Then, combine the two arrays using two pointers. The time complexity for this solution is $$$O(2^n * log^2(2^n))$$$, where $$$2^n$$$ is the size of the array.

Another approach is to use two pointers to calculate the wins. After calculating and updating both arrays, we can merge them together. This approach has a time complexity of $$$O(2^n*log(2^n)))$$$.

• Space Complexity: $$$O(2^n)$$$

def mergeSort(arr,l,r):
    if l == r:
   	 return
    
    # get the mid point of the current array and merge sort it
    mid = (l + r)//2
    mergeSort(arr,l,mid)
    mergeSort(arr,mid + 1, r)
    # merge the two halves after sorting them and calculating the answer
    merge(arr,l,mid,r)
 
def merge(arr,l,mid, r):
    # wins array to hold the number of wins each team have
 
    wins = [0]*(r - l + 1)
    # array to hold merged list
    merged = []
    
    # calculate the wins for the first group
    ptr = mid + 1
 
    # for every element of the first group
    for i in range(l,mid + 1):
   	 # move the second groups point to an element which is greater or equal to it
  	 
   	 while ptr <= r and arr[ptr][1] < arr[i][1]:
   		 ptr += 1
 
   	 # the total numbe of wins for the current element
   	 #is the nubmer of element in the second group
   	 #that is lower than it
   	 wins[i - l] = ptr - (mid + 1)
 
    # same thing for the second group
    ptr = l
    for i in range(mid + 1,r+1):
   	 while ptr <= mid and arr[ptr][1] < arr[i][1]:
   		 ptr += 1
   	 wins[i - l] = ptr - l
 
    # merge the two groups based on the new value
    pt1 = l
    pt2 = mid + 1
 
    while pt1 <= mid or pt2 <= r:
   	 if (pt2 > r) or (pt1 <= mid and arr[pt1][1] + wins[pt1 - l] < arr[pt2][1] + wins[pt2 - l]):
   		 arr[pt1][1] += wins[pt1 - l]
   		 merged.append(arr[pt1])
   		 pt1 += 1
   	 else:
   		 arr[pt2][1] += wins[pt2 - l]
   		 merged.append(arr[pt2])
   		 pt2 += 1
 
    arr[l:r + 1] = merged
 
 
 
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    arr = [[i,j] for i,j in enumerate(arr)]
    mergeSort(arr,0,2**n - 1)
    ans = [i[1] for i in sorted(arr,key = lambda x: x[0])]
    
    print(*ans)
 
t = int(input())
for _ in range(t):
    solve()

Find the time each gun explodes then you can take the maximum one.

Use monotonic stack to track the damage a gun receives for a gun behind him.

To determine the time it takes for each gun to explode, we can employ a monotonic stack approach. Starting from the first gun, which we know for sure will explode at infinity, we can represent each gun as a tuple $$$(t_i, p_i)$$$, where $$$t_i$$$ is the life of the $$$i$$$-th gun and $$$p_i$$$ is its power. These tuples are then pushed onto the stack.

For each gun $$$i$$$, we can understand that it receives a hit from the last gun on the stack. The damage it receives can be calculated as stack[-1][-1] * (stack[-1][0] - d), where stack[-1][0] and stack[-1][-1] represent the life and power of the gun at the end of the stack, respectively. Here, $$$d$$$ represents the duration of gun $$$i$$$ before it encounters the gun at the end of the stack. If the gun at the end of the stack cannot reduce the health of gun $$$i$$$ to zero, we decrement the received damage with the gun's health and pop from the stack.

• Time Complexity: $$$O(n)$$$
• Space Complexity: $$$O(n)$$$

import sys
from math import ceil, inf
input = lambda : sys.stdin.readline().strip()


for t in range(int(input())):
    n = int(input())
    health = list(map(int, input().split()))
    power = list(map(int, input().split()))


    stack = [(inf, power[0])]
    ans = 0
    for i in range(1, n):
        duration = 0
        while health[i] - (stack[-1][0] - duration)*stack[-1][-1] > 0:
            t, p = stack.pop()


            health[i] -= (t-duration)*p
            duration += (t-duration)
       
        duration += ceil(health[i]/stack[-1][-1])
        stack.append((duration, power[i]))
        ans = max(ans, duration)
   
    print(ans)

What if we have every sorted prefix.

Do we need every sorted prefix? and is there a fast way to compute it?

If we had every sorted prefix of the array, answering queries would be trivial, we could simply use binary search to count elements less than $$$X$$$ in the first $$$K$$$ elements. However, storing all sorted prefixes would require:

• $$$O(n² log n)$$$ time to preprocess
• $$$O(n²)$$$ space to store

This is clearly very inefficient.

An observation that will help us is that any positive integer $$$K$$$ can be represented as a sum of distinct powers of 2. This is essentially the binary representation of $$$K$$$. For example:

• $$$K = 5 = 4 + 1 (2² + 2⁰)$$$
• $$$K = 7 = 4 + 2 + 1 (2² + 2¹ + 2⁰)$$$
• $$$K = 10 = 8 + 2 (2³ + 2¹)$$$

This property allows us to decompose any prefix of length $$$K$$$ into $$$log K$$$ segments, each being a power of 2 in length,So we don't need every sorted prefix. Okay so now we only need to make these segments sorted.

If we can save this structure we will be able to calculate on each segment that makes up $$$K$$$, how many elements are less than $$$X$$$.

Complexity Analysis

Preprocessing

• Time: $$$O(N log N)$$$ — Each element appears in $$$O(log N)$$$ sorted segments
• Space: $$$O(N log N)$$$ — Storing all sorted segments

Queries

• Time: $$$O(log² N)$$$ per query ($$$O(log N)$$$ segments × $$$O(log N)$$$ binary search)
• Total for Q queries: $$$O(Q log² N)$$$

from bisect import bisect_left

for _ in range(int(input())):
    n, Q = map(int, input().split())
    soldiers = list(map(int, input().split()))
    
    '''
    calculate size as the smallest power of 2 
    greater than or equal to n
    '''
    size = 1
    level = 0
    while size * 2 < n:
        size *= 2
        level += 1
        
    size *= 2
    level += 2
    
    # lets extend the given array's size to a power of 2 
    while len(soldiers) < size:
        soldiers.append(float('inf'))
    
    n = len(soldiers) # Update n

    tree = [[] for _ in range(level)]
    tree[0].append(sorted(soldiers)) # the first leve(0) is the whole sorted array



    def merge(left, right):
        # standard merge of two sorted lists
        # we can do other things here if needed :)
        return sorted(left + right)




    def mergeSort(left, right, arr, level):
        if left == right:
            return [arr[left]]
        
        mid = (left + right) // 2
        
        left_half = mergeSort(left, mid, arr, level + 1)
        right_half = mergeSort(mid + 1, right, arr, level + 1)
        
        # save each sorted segment at its corresponding level
        tree[level].append(left_half) 
        tree[level].append(right_half)

        return merge(left_half, right_half)

    '''
    query function takes:
    k - number of elements to consider
    level - current level in the tree
    node - current node/segment index
    x - warriors strength value

    Each level contains segments of length 2^level
    We recursively find which segments make up the prefix of length k
    For each segment, we use binary search to count elements < x
    '''

    def query(k, level, node, x):
        # base case: no more elements or exceeded tree levels
        if level >= len(tree) or not k:
            return 0
        
        # calculate segment length at current level
        length = n 
        for _ in range(level):
            length //= 2 
        
        if length <= k:
            #count elements < x in this segment
            lesser_elements = bisect_left(tree[level][node-1], x)
            
            #recurse for remaining elements
            return lesser_elements + query(k - length, level + 1, (node*2) + 1, x)

        # if segment is larger than needed, go deeper
        return query(k, level + 1, 2*node - 1, x)
            
    # build the merge sort tree starting from level 1
    mergeSort(0, n-1, soldiers, 1)


    #Finally now we can process queries
    for _ in range(Q):
        k, x = map(int, input().split())
        print(query(k, 0, 1, x)) 

For each query, we need to count how many elements in a prefix A[0..K-1] are strictly less than $$$X$$$. Naively, for each query, iterating through the prefix would cost $$$O(K)$$$ per query, which is too slow when $$$Q$$$ and $$$K$$$ are large. We need something faster, ideally logarithmic time per query.

A powerful way to handle such queries efficiently is to use divide and conquer, or specifically merge sort logic. We are going to apply a modified merge sort on the array. The main idea is to group queries based on their indices (that is, the prefix limit $$$K$$$). For each index $$$i$$$, collect all the different values $$$X$$$ that will be queried against the prefix up to $$$i$$$.

A standard merge sort is used to both, sort the array, and merge and count how many left-side elements are less than $$$X$$$ for every query on the right side. This allows for efficiently processing all queries offline. We can store the answer for every possible ($$$K$$$, $$$X$$$) pairs. And then we will iterate through all the queries and then print the answer.

For the time complexity of this approach the operations is similar to regular merge sort, in the sense that we have $$$O(\log N)$$$ layers, and on each layer we will have $$$O(N + Q)$$$ operations per layer. Therefore, the overall time complexity will be $$$O((N + Q) \log N)$$$.

For the space complexity, since merge sort is not in-place, we will have $$$O(N)$$$ memory consumption for sorting. And there is also $$$O(Q)$$$ memory for storing the queries, and the dictionary that stores the $$$X$$$s. Therefore, the overall space complexity will be $$$O(N + Q)$$$.

from collections import Counter
import sys


def input():
    return sys.stdin.readline().strip()


# Utility to read list of integers
def readList():
    return list(map(int, input().split()))


def solve():
    array_length, query_count = readList()
    array = readList()

    queries = []
    for _ in range(query_count):
        index, value = readList()
        queries.append((index - 1, value))  # 0-based indexing

    # Track required query values per index
    query_values_at_index = [set() for _ in range(array_length)]
    for index, value in queries:
        query_values_at_index[index].add(value)

    # Sort required values for each index for binary search/merge purposes
    for index in range(array_length):
        query_values_at_index[index] = sorted(query_values_at_index[index])

    # Dictionary to store the result of each (index, value) query
    query_results = Counter()

    def merge_sort_count(start, end):
        """
        Recursive divide and conquer function that returns:
        - a sorted list of elements in array[start:end+1]
        - a sorted list of (value, index) query pairs for that segment
        Also populates query_results with counts of elements less than 'value' to the left of 'index'.
        """
        if start == end:
            current_elements = [array[start]]
            current_queries = [(value, start) for value in query_values_at_index[start]]

            for value, idx in current_queries:
                if array[start] < value:
                    query_results[(idx, value)] += 1

            return current_elements, current_queries

        mid = (start + end) // 2
        left_elements, left_queries = merge_sort_count(start, mid)
        right_elements, right_queries = merge_sort_count(mid + 1, end)

        merged_elements = []
        merged_queries = []

        # Count how many left_elements are < each right query's value
        i = j = count = 0
        while i < len(left_elements) and j < len(right_queries):
            value, idx = right_queries[j]
            if left_elements[i] < value:
                count += 1
                i += 1
            else:
                query_results[(idx, value)] += count
                j += 1

        # For remaining right queries
        while j < len(right_queries):
            value, idx = right_queries[j]
            query_results[(idx, value)] += count
            j += 1

        # Merge the sorted arrays
        i = j = 0
        while i < len(left_elements) and j < len(right_elements):
            if left_elements[i] <= right_elements[j]:
                merged_elements.append(left_elements[i])
                i += 1
            else:
                merged_elements.append(right_elements[j])
                j += 1

        merged_elements.extend(left_elements[i:])
        merged_elements.extend(right_elements[j:])

        # Merge the sorted query lists
        i = j = 0
        while i < len(left_queries) and j < len(right_queries):
            if left_queries[i] <= right_queries[j]:
                merged_queries.append(left_queries[i])
                i += 1
            else:
                merged_queries.append(right_queries[j])
                j += 1

        merged_queries.extend(left_queries[i:])
        merged_queries.extend(right_queries[j:])

        return merged_elements, merged_queries

    # Run the divide and conquer process
    merge_sort_count(0, array_length - 1)

    # Print the answers in the order of input queries
    for index, value in queries:
        print(query_results[(index, value)])


t = int(input())
for _ in range(t):
    solve()

What does "book with the highest number" mean? Does it mean the highest number of pages, or the highest index? Read the note carefully!

"Book with the highest number" refers to the book's index ($$$1$$$-st, $$$2$$$-nd, $$$\dots$$$, $$$n$$$-th), not the number of pages it contains.

When we divide the $$$n$$$ books into two non-empty piles, the absolute highest index $$$n$$$ must end up in one of the piles. Therefore, the maximum index in that pile will always be $$$n$$$, meaning Temesgen will always read the $$$n$$$-th book and read $$$a_n$$$ pages from it.

For the other pile, we want its highest index, let's call it $$$k$$$, to have the maximum possible pages $$$a_k$$$. Can we make $$$k$$$ be any index from $$$1$$$ to $$$n-1$$$? Yes! We can simply place our chosen book $$$k$$$ into the second pile, and put all other books (including $$$n$$$) into the first pile. Thus, the second pile only contains book $$$k$$$, making $$$k$$$ its highest index.

Therefore, the maximum total number of pages Temesgen can read is $$$a_n + \max(a_1, a_2, \dots, a_{n-1})$$$.

1. Read the array of books $$$a$$$.
2. The pages from the first pile will always be $$$a_n$$$ (the last element in the array).
3. The pages from the second pile will be the maximum value among the first $$$n-1$$$ elements.
4. Add these two values together and print the sum.

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    
    # a[-1] is the n-th book
    # max(a[:-1]) is the max pages among the first n-1 books
    print(a[-1] + max(a[:-1]))

• Time Complexity: $$$O(n)$$$ per test case to find the maximum in the first $$$n-1$$$ elements.
• Space Complexity: $$$O(n)$$$ to store the array.

There are no zeros in the string. How does the number of digits affect the integer value of a string?

Since the digits are only from $$$1$$$ to $$$9$$$ (no leading zeros to worry about), any number with $$$2$$$ or more digits will always be strictly greater than a $$$1$$$-digit number.

This means if we split the string immediately after the first character, the first part has length $$$1$$$, and the second part has length $$$n-1$$$. If $$$n \ge 3$$$, the second part will have at least $$$2$$$ digits and will inherently be greater than the first part. The only edge case is when $$$n = 2$$$, where both parts have length $$$1$$$. In that case, we just need to ensure the first digit is strictly less than the second digit.

1. If $$$n = 2$$$ and the first digit is greater than or equal to the second digit, output NO.
2. Otherwise, output YES, set the number of splits to $$$2$$$, and print the first character followed by the rest of the string.

q = int(input())
for _ in range(q):
    n = int(input())
    s = input().strip()
    
    if n == 2 and s[0] >= s[1]:
        print("NO")
    else:
        print("YES")
        print(2)
        print(s[0], s[1:])

• Time Complexity: $$$O(n)$$$ per test case for string slicing.
• Space Complexity: $$$O(n)$$$ to store the substrings.

A bulb flips its state for every divisor of its index. Which numbers have an odd number of divisors?

A bulb $$$j$$$ starts ON and is flipped exactly $$$d(j)$$$ times, where $$$d(j)$$$ is the number of divisors of $$$j$$$. It will end up OFF if it is flipped an odd number of times.

The only numbers with an odd number of divisors are perfect squares. Therefore, out of the first $$$n$$$ bulbs, the number of bulbs that end up OFF is exactly $$$\lfloor \sqrt{n} \rfloor$$$. This means the number of bulbs remaining ON is $$$n - \lfloor \sqrt{n} \rfloor$$$.

Since the function $$$f(n) = n - \lfloor \sqrt{n} \rfloor$$$ is monotonically non-decreasing, we can find the minimum $$$n$$$ that yields exactly $$$k$$$ ON bulbs using binary search.

1. Set the binary search range: low = 1 and high = 2 * 10^18.
2. Calculate $$$mid$$$ and find how many bulbs are ON: $$$mid - \lfloor \sqrt{mid} \rfloor$$$.
3. If the number of ON bulbs is $$$\ge k$$$, update our answer to $$$mid$$$ and search the left half (high = mid — 1) to minimize $$$n$$$.
4. Otherwise, search the right half (low = mid + 1).

import math
import sys

input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        k = int(input())
        
        low, high = 1, 2000000000000000000
        ans = high
        
        while low <= high:
            mid = (low + high) // 2
            on_bulbs = mid - math.isqrt(mid)
            
            if on_bulbs >= k:
                ans = mid
                high = mid - 1
            else:
                low = mid + 1
                
        print(ans)

solve()

• Time Complexity: $$$O(\log(\text{MAX\_N}))$$$ per query. With $$$MAX\_N \approx 2 \cdot 10^{18}$$$, this takes around 60 iterations, making it extremely fast overall.
• Space Complexity: $$$O(1)$$$.

If you know the maximum number of elements $$$k$$$ you can keep in the array, which elements from array $$$a$$$ and array $$$b$$$ should you pick to maximize the chances that $$$a_i \lt b_i$$$?

To minimize the number of operations (deletions), we need to maximize the final array length $$$k$$$. To maximize the probability of forming $$$k$$$ valid pairs $$$(a_i, b_i)$$$ where $$$a_i \lt b_i$$$, we should pair the $$$k$$$ smallest elements of array $$$a$$$ with the $$$k$$$ largest elements of array $$$b$$$.

Notice that $$$m=1$$$ in the constraints, so we only need to consider the case where the first element of $$$a$$$ is set to $$$1$$$. Once $$$a$$$ is updated and both arrays are sorted, the property of "being able to form $$$k$$$ pairs" is monotonic. If we can form $$$k$$$ pairs, we can also form $$$k-1$$$ pairs. Thus, we can use binary search on the answer!

1. Construct array $$$a$$$ by prepending $$$1$$$ to the given $$$n-1$$$ elements.
2. Sort both array $$$a$$$ and array $$$b$$$ in ascending order.
3. Binary search the maximum possible $$$k$$$ in the range $$$[0, n]$$$.
4. To check if a specific $$$k$$$ is valid: compare the first $$$k$$$ elements of $$$a$$$ with the last $$$k$$$ elements of $$$b$$$. If $$$a[i] \lt b[n - k + i]$$$ holds true for all $$$0 \le i \lt k$$$, then this $$$k$$$ is valid.
5. If valid, try to look for a larger $$$k$$$ by searching the right half. Otherwise, search the left half.
6. The minimum operations needed will be the total elements minus the maximum paired ones: $$$n - k$$$.

import sys

input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n, m = map(int, input().split())
        a = [1] + list(map(int, input().split()))
        b = list(map(int, input().split()))
        
        a.sort()
        b.sort()
        
        def check(k):
            # check if first k elements of 'a' are strictly less than the last k elements of 'b'
            for i in range(k):
                if a[i] >= b[n - k + i]:
                    return False
            return True
            
        low, high = 0, n
        max_k = 0
        
        while low <= high:
            mid = (low + high) // 2
            if check(mid):
                max_k = mid       # valid, store answer
                low = mid + 1     # try to find a larger k
            else:
                high = mid - 1    # invalid, try a smaller k
                
        # the minimum deletions is n minus the max elements we could keep
        print(n - max_k)

solve()

• Time Complexity: $$$O(n \log n)$$$. Sorting both arrays takes $$$O(n \log n)$$$. The binary search iterates $$$\log n$$$ times, and each `check` function takes $$$O(n)$$$ time in the worst case, contributing another $$$O(n \log n)$$$.
• Space Complexity: $$$O(n)$$$ to store the inputs.

For a given voucher, you need another non-overlapping voucher with a specific remaining duration that has the minimum possible cost. How can you efficiently query this using binary search?

Since the two chosen vouchers must equal exactly $$$x$$$ in total duration, a voucher of duration $$$dur$$$ strictly requires a partner voucher of duration $$$x - dur$$$.

We can group all the vouchers by their duration. Inside each group, if we sort the vouchers by their start time $$$l$$$, we can quickly find a non-overlapping partner! Specifically, for a voucher ending at $$$r_i$$$, we can binary search (using bisect_right) in the target duration group for the first voucher whose start time $$$l_j$$$ is strictly greater than $$$r_i$$$.

To quickly get the minimum cost among all valid partners that start at or after this index, we can precalculate a suffix minimums array for costs in each duration group.

1. Group all vouchers in a dictionary mapped by their duration: $$$r - l + 1$$$.
2. For each duration group, sort the vouchers by their start time $$$l$$$.
3. For each sorted group, create an array of just the start times (to be used for binary search) and a `suffix_mins` array that stores the minimum cost from that index to the end of the group.
4. Iterate over all vouchers. For a voucher with duration $$$dur$$$, end time $$$r$$$, and cost $$$c$$$, the target complementary duration is $$$rem = x - dur$$$.
5. If the $$$rem$$$ group exists, use binary search to find the first index where the start time is $$$ \gt r$$$.
6. If such an index exists, add $$$c$$$ to the value in the `suffix_mins` at that index, and update the global minimum total cost.
7. If the global minimum remains infinity, output -1.

import sys
from bisect import bisect_right
from collections import defaultdict

input = sys.stdin.readline

def solve():
    n, x = map(int, input().split())
    
    vouchers = []
    groups = defaultdict(list)
    
    for _ in range(n):
        l, r, cost = map(int, input().split())
        dur = r - l + 1
        vouchers.append((l, r, cost, dur))
        groups[dur].append((l, r, cost))
        
    start_times = {}
    suffix_mins = {}
    
    # Sort each duration group and build suffix minimums for O(1) minimum queries
    for dur in groups:
        groups[dur].sort(key=lambda v: v[0])
        st = [v[0] for v in groups[dur]]
        start_times[dur] = st
        
        # Build suffix minimums
        sm = [0] * len(st)
        sm[-1] = groups[dur][-1][2]
        for i in range(len(st)-2, -1, -1):
            sm[i] = min(sm[i+1], groups[dur][i][2])
        suffix_mins[dur] = sm
        
    ans = float('inf')
    
    for l, r, cost, dur in vouchers:
        rem = x - dur
        
        if rem in groups:
            st = start_times[rem]
            # Binary search for the first valid voucher that starts after this one ends
            pos = bisect_right(st, r)
            
            if pos < len(st):
                ans = min(ans, cost + suffix_mins[rem][pos])
                
    print(ans if ans != float('inf') else -1)

solve()

• Time Complexity: $$$O(n \log n)$$$. Grouping and sorting the vouchers takes $$$O(n \log n)$$$. Iterating through $$$n$$$ vouchers and performing a binary search on the start times takes $$$O(n \log n)$$$ as well.
• Space Complexity: $$$O(n)$$$ to store the dictionary groups, start times, and suffix minimums.

If you had all numbers from 1 to n, what would their total sum be?

Subtract the numbers Daniel already played from that total. The remaining number is the missing level.

Sum of 1..n = n*(n+1)//2. Subtract the sum of given numbers → missing level. Time: O(n)

n = int(input())
arr = list(map(int, input().split()))
total = n * (n + 1) // 2
print(total — sum(arr))

From a free cell you can jump at most k cells ahead. If there is a block of consecutive obstacles, you must be able to jump over it — what is required from k relative to the block size?

If a block of # is too long and the robot cannot jump that far, he will get stuck.

Count consecutive #. If any group has length ≥ k, the robot cannot pass. Otherwise, he can reach the end.
Time Complexity: O(n)

n, k = map(int, input().split())
s = input().strip()

count = 0
for ch in s:
    if ch == '#':
        count += 1
        if count >= k:
            print("NO")
            break
    else:
        count = 0
else:
    print("YES")

Go from left to right. Keep track of the maximum height allowed for the current book.

For each book, try the larger side if possible. If not, use the smaller side.

• Set prev to a very large number.
• For each book: — Let big = max(w, h), small = min(w, h). — If big <= prev, choose big.
  — Else if small <= prev, choose small.
  — Else answer is NO.
• If all books work, answer is YES.
  Time Complexity: O(n)

n = int(input())
prev = 10**18
for _ in range(n):
    w, h = map(int, input().split())
    big = max(w, h)
    small = min(w, h)

    if big <= prev:
        prev = big
    elif small <= prev:
        prev = small
    else:
        print("NO")
        break
else:
    print("YES")

Check the total size without compression first. Then, if needed, compress files that reduce the most size.

Sort files by how much size they reduce. Apply the biggest reductions first.

• Let total = sum(all original sizes).
• If total <= m, answer is 0.
• Else, compute how much each file reduces, sort reductions decreasing, apply them one by one until total <= m.
• If even after compressing all files, total > m, print -1.
  Time Complexity: O(n log n)

n, m = map(int, input().split())
total = 0
saves = []

for _ in range(n):
    a, b = map(int, input().split())
    total += a
    saves.append(a — b)

if total <= m:
    print(0)
else:
    saves.sort(reverse=True)
    count = 0
    for s in saves:
        total -= s
        count += 1
        if total <= m:
            print(count)
            break
    else:
        print(-1)

Sort all blocks from smallest to largest. Some may already be next to each other in a tower.

If two consecutive numbers in sorted order are already next to each other in one tower, we don’t need to split them.

Count how many consecutive pairs we can keep. The rest may need splits.

• Record each block’s tower and position.
• Sort all blocks.
• Count “good adjacencies”: consecutive sorted blocks in the same tower.
• splits = (total_blocks - good_adj) - number_of_towers
• combines = splits + (number_of_towers - 1)
  Time Complexity: O(N log N)

n = int(input())

pos = {}
vals = []
for t in range(n):
    data = list(map(int, input().split()))
    k = data[0]
    blocks = data[1:]
    for i, v in enumerate(blocks):
        pos[v] = (t, i)
        vals.append(v)

vals.sort()

good = 0
for i in range(len(vals) — 1):
    t1, p1 = pos[vals[i]]
    t2, p2 = pos[vals[i+1]]
    if t1 == t2 and p2 == p1 + 1:
        good += 1

N = len(vals)
segments = N — good
splits = segments — n
combines = segments — 1

print(splits, combines)