Freaks City

Introduction During the summer vacation, I systematically studied various operations on trees through Teacher Tuo's sharing and discovered many useful techniques, which I now summarize. Teacher Tuo is amazing! One Problem Type: Batch processing queries of the form f(dep(lca(x,y))), where f(x) is a function of x. Approach: First perform tree ...

1. Gymnastic Team Formation Given the small input constraints, a brute-force approach with backtracking and pruning is suitable. The solution uses depth-first search (DFS) to explore valid permutations while eliminating invalid paths early. #include <iostream> using namespace std; int constraints[11] = {0}; bool used[11] = {false}; int v ...

Given an $n \times m$ grid where each cell is either empty (.) or blocked (*), place the minimum number of $1 \times 2$ or $2 \times 1$ dominoes such that no two adjacent empty cells remain — i.e., it's impossible to place any additional domino. Constraints: $1 \leq n \leq 70$, $1 \leq m \leq 7$. Due to the small value of $m$, a dynamic program ...

Problem 1: Optimized Dynamic Programming with Prefix Sums This problem involves a basic dynamic programming approach where we process from the end to the beginning. The naive solution has a time complexity of O(n²), but we can optimize it using prefix sums and binary search. We maintain a prefix sum array and for each position, use binary searc ...

Potion-making Solution This problem requires solving the equation i/(i+j) = k/100 to find the minimal total ingredients. The solution involves iterating through possiblle values of i and j. #include <iostream> #include <cmath> using namespace std; void solvePotion() { int target_percentage; cin >> target_percentage; ...

Longest Increasing Subsequence (LIS) The Longest Increasing Subsequence problem involves findinng the maximum length of a strictly increasing subsequence from a given sequence of length n. The subsequence elements need not be contiguous in the original sequence. Dynamic Programming Approach (O(n²)) State Representation DP array: Stores the len ...

Range Minimum/Maximum Query (RMQ) The RMQ problem involves finding the minimum or maximum value within a specified range of an array of length n. Given multiple queries of the form RMQ(A, i, j), where i and j are indices in the array, the task is to return smallest or largest element between positions i and j. Sparse Table Algorithm The Sparse ...

Problem A: Large-Scale Simulation A pure simulation problem centered on game theory mechanics. The implementation involves directly modeling the described rules and state transitions. Problem B: Maximum Total Range for k-Partition Define the weight of a subarray as its range (maximum element minus minimum element). For each k from 1 to n, compu ...

We are given a tree of (n) nodes, each carrying an integer weight (which may be negative). The task is to select a connected subgraph that forms a subtree and maximise the sum of the node weights inside it. The problem appears with two common variants: one that allows an empty selection (answer at least 0) and one that requires at least one nod ...

When solving this problem, precision errors in floating-point comparisons led to multiple failed submissions despite correct algorithmic logic. The challenge lies in grouping monsters by their directional vectors and efficiently computing the number of targets hit by a laser fired in a specific direction. Monsters are represented as coordinate ...