A. [POI2004] SZP Description Given a directed graph with cycles, where each node has exactly one outgoing edge (non-self-loop), select the maximum number of nodes such that every selected node has at least one immediate predecessor that is not selected. Solution Observe that each weakly connected co...
Problem Analysis The objective is to cover all occupied stalls in a linear arrangement using a maximum of M boards, minimizing the total length of the boards. If only one board is available, it must span from the leftmost occupied stall to the rightmost. Adding more boards allows leaving gaps betwee...
The problem involves selecting the maximum number of students for recommendation under specific constraints: Only students with a score of atleast 175 are eligible. Exactly K recommendation batches are allowed. Within each batch, student scores must be non-decreasing, and strictly increasing unless...
Optimal Fishing Strategy: A Greedy Algorithm Approach Problem Description There are n fishing lakes arranged horizontally along a road, numbered 1 to n from left to right. A person has H hours of free time and wants to catch as many fish as possible. They start at lake 1 and move right, choosing to...
The problem involves determining the lexicographically largest binary string that can be constructed under constraints derived from a set of pattern strings containing '0', '1', and '-' (wildcard) characters. Each query provides a target string, and the solution must find the maximal answer consiste...
Problem Description There are n piles of cards, numbered from 1 to n. Each pile contains a certain number of cards, and the total number of cards is guaranteed to be a multiple of n. You can take any number of cards from a pile and move them according to the following rules: Cards taken from pile 1...
What is Greedy? The essence of greedy is to choose the local optimum at each stage, aiming to achieve the global optimum. Greedy Strategy Try to find a counterexample; if none exists, then greedy is worth trying. Steps Decompose the problem into subproblems. Find a suitable greedy strategy. Solve ea...
Linear Programming Formulation Let (\cdot) denote the dot product, with (b,c,x,y) as row vectors. For matrix (A), vectors (u,v) satisfy (u \leq v) if (\forall i, u_i \leq v_i), and similar for (\geq). The standard linear programming (LP) problem is: [\max c \cdot x \quad \text{s.t.} \quad \begin{cas...