Freaks City

Intersection Calculation Given two line segments [L1, R1] and [L2, R2], determine their overlapping length. A simple approach uses a frequency array to mark covered positions. #include <iostream> using namespace std; int main() { int L1, R1, L2, R2; int coverage[101] = {0}, overlap = 0; cin >> L1 >> R1 >> L2 ...

Problem A: Digit Frequency Analysis Given a functon (f(x)) that counts the frequency of the most common digit in number (x), compute (\sum_{i=l}^{r}f(i)) for large ranges (up to (10^{18})). Approach: Represent digit counts as a state vector (S = {c_0, \dots, c_9}) Transform into frequency-of-counts representation (S' = {a_0, \dots, a_{18}}) Us ...

Binary search extends far beyond locating values in sorted arrays. The core requirement for applying this technique is identifying a monotonic relationship between an independent variable and a computed result. When a problem can be modeled as finding an input x such that a monotonic function f(x) equals a specific target, binary search becomes ...

Tree-based dynamic programming relies on post-order traversal (processing children before parents). The standard recursive skeleton ensures proper state aggregation without cyclic revisits: void traverse(int current_node, int parent_node) { // Process leaf/base case initialization if necessary for (auto& edge : adjacency_list[c ...

We are given an n × m integer matrix. In one operation, we may select a single row and a single column, subtract 1 from every element in that row and every element in that column — except the intersection cell, which is only decremented once (i.e., no double subtraction). Our goal is to minimize the maximum value in the resulting matrix. Key In ...

Problem Analysis The challenge involves cutting bamboo stalks of varying heights down to a uniform height of 1 using magical operations. Each spell can simultaneously reduce multiple consecutive bamboo pieces of identical height. When applied to bamboo of height H, the new height becomes ⌊√(⌊H/2⌋ + 1)⌋. The goal is to determine the minimum numb ...

SMU Summer 2024 Contest Round 8 - Problem Solutions Problem 1: Product Approach Observing that the constraint \(\prod_{i=1}^N L_i \le 10^5\) implies that N cannot exceed 16, since \(2^{17} > 10^5\). This allows us to solve the problem using straightforward brute force enumeration of all possible combinations. Implementation #include <bits ...

The contest comprised 11 problems with varying difficulty levels based on technical depth: High Solvability (8/11): Problems A, B, C, D, H, I, J, K generally follow standard patterns. Low Solvability (3/11): E, F, G involve complex nested algorithms or obscure insights. The following sections detail the solutions for the most instructive prob ...

Probabilistic Path Enumeration in Directed Acyclic Graphs Given a directed acyclic graph (DAG) consisting of $V$ vertices and $E$ edges, each edge $e_k$ possesses an independent activation probability $p_k$. The objective is to compute the expected number of functional paths originating from vertex $0$ and terminating at vertex $V-1$. A path is ...

Problem A: Equilibrium Distribution The objective requires calculating the maximum uniform amount two participants can receive by redistributing three initial piles. The mathematical foundation relies on summing all available items across the piles and performing integer division by two. Since any remainder must remain undistributed to satisfy ...