1.
Pigeon Orientation: Given a string of 'L' and 'R' representing pigeons facing left or
right, find the minimum number of pigeons to flip so that no two pigeons face each
other.
2. Distinct Swaps: Given an array, find the number of distinct "good arrays" you can
form by swapping any two elements such that $A[0] > A[n-1]$.
3. Good Strings (Prefix Sum): Given a string of 'G' and 'R', count how many subarrays of
the form "GGRR" or "RRGG" can be formed using prefix sums.
4. Binary Search on Fruits: Find the minimum "essence" to add to a fruit array (where
adding to $W_i$ affects all $W_j \ge W_i$) such that there's a subarray of size $C$
where flavored fruits outnumber unflavored ones.
5. K-th Occurrence Queries: Given an array and $Q$ queries of $(x, k)$, find the index
of the $k$-th occurrence of $x$ in the array efficiently.
6. Subarray Square Sum: Divide an array into $k$ subarrays to minimize the sum of the
squares of the sums of each subarray: $\sum (Sum_{subarray})^2$.
7. LIS with Reversal: Find the Longest Increasing Subsequence of an array where you
are allowed to reverse exactly one subarray.
8. GCD Score Maximization: You have $2A$ integers and $A$ rounds. In each round,
pick two numbers $x, y$ and delete them. Score = $GCD(x, y) \times
\text{round\_number}$. Maximize the total score.
9. Matrix Chain Modification: A variation of Matrix Chain Multiplication where the cost
function involves bitwise operations instead of standard multiplication.
10. Special Partition: Given an array, partition it into three subarrays (prefix, middle,
suffix) such that the sum of elements is maximized and no element is used twice.
11. Closest Node on Path: Given a tree and $Q$ queries of $(U, V, W)$, find the node on
the path between $U$ and $V$ that is closest to node $W$.
12. Non-Decreasing Moves: In one move, you can remove all $A[i]$ such that $A[i] < A[i-
1]$. Find the minimum moves to make the array non-decreasing.
13. Graph Bridges: Identify all "critical connections" in a network (bridges) and return
them sorted.
14. Dijkstra with Constraints: Find the shortest path in a graph where some edges can
only be traversed if you have a specific "key" collected from a previous node.
15. Tree Diameter & Path: Find the diameter of a binary tree and return the actual path
(nodes) that forms it.
16. Range Bitwise Updates: Implement a segment tree that supports range updates (Set
$X$ to $V$ or $X$ OR $V$) and queries for the sum of bitwise AND of all subarrays in
a range $[l, r]$.
17. Disjoint Set with Weights: Implement DSU where each set also maintains the total
weight of its elements and the maximum element in that set.
18. Segment Points: Given multiple segments $[start, end]$, find the coordinate covered
by the maximum number of segments.
19. Lazy Propagation Range Min: A standard Segment Tree problem but with a twist:
updates are $A[i] = A[i] \pmod K$.
20. Prime Box Factorials: Given $n$ boxes where box $i$ contains $i! + b$. Count how
many boxes contain a prime number (where $b$ is small, e.g., $2 \le b \le 15$).