2023.10.19 Full Simulation Exam Summary Overview Schedule Exam Results Exam Reflection Problems T1 T2 T3 T4 Overview Schedule 8 : 00 ∼ 8 : 20 \qquad 8:00\sim 8:20 8:00∼8:20 Read through the problem statements, and got a general idea of each question in my mind, thinking briefly. The exam felt very f...
Combination Sum Given a collection of distinct integers and a target value, identify all unique combinations where the chosen numbers sum to the target. Each candidate may be used an unlimited number of times. The solution employs depth-first search with backtracking. First, sort the input array to...
1. Topological Sorting Definition: Let $G = (V, E)$ be a directed graph with $n$ vertices. A vertex sequence from $V$ is called a topological sequence if and only if: for any path from vertex $u$ to $v$, $u$ appears before $v$ in the sequence. Basic Idea: Select a vertex with no predecessors (in-deg...
CF40E The problem involves a combinatorial proof regarding parity conditions. Lemma 1: If the answer is non-zero, then n and m must have the same parity. Proof: Considering each row and column sums to 1, multiplying all entries yields (-1)^n = (-1)^m, hence n ≡ m (mod 2). Lemma 2: Under Lemma 1's co...
"Little by little, a little becomes a lot; grain by grain, a heap is formed. Seconds may be short, yet they compose the great eras of eternity. — Fletcher" Key Topics Covered 1. Depth-First Search (DFS) Fibonacci Triple Sum Problem Problem Description: Given an integer t test cases, for e...
Graph Coloring Count Problem Problem Statement Given an undirected graph, color each vertex such that no two adjacent vertices share the same color. Calculate the total number of valid coloring schemes using a specified number of colors. Input Format First line: Two positive integers n and m (0 <...
Depth-first search is a fundamental graph traversal algorithm. A grasp of recursion is beneficial before learning DFS. Implementing Graph Traversal with DFS Contagion Spread Problem Problem Statemnet A simulation involves N entities, each existing at a unique coordinate point. These entities functio...
Depth-first search (DFS) is characterized by advancing as far as possible along a single branch before retreating. This retreat occurs only upon encountering a dead end, which arises either from hitting a boundary or from reaching a previously visited location. Upon backtracking, the algorithm retur...
DFS Trees in Graph Theory A DFS tree is formed during a depth-first search traversal of a graph or tree structure. Starting from a root vertex, the algorithm explores as far as possible along each branch before backtracking. In this process, edges traversed to unvisited nodes become tree edges, whil...