Freaks City

The Ternary Goldbach Conjecture asserts that any odd integer greater than 7 can be represented as the sum of three prime numbers. While proven for sufficiently large numbers, verifying this for smaller integers requires an effiicent computational approach. Given an odd integer n (9 < n < 20,000), our objective is to find a triplet of prim ...

Introduction Heavy-light decomposition (HLD) is a sophisticated algorithmic technique used to partition tree structures into linear sequences, enabling efficient query and update operations. This method is particularly effective for handling subtree and path queries on trees. Core Definitions Heavy Child: For any node, its heavy child is the c ...

Problem: Finding the K-th Smallest Number Given an array of n integers (n < 5,000,000, odd) and an integer k, find the k-th smallest element where the smallest element is considered the 0-th. Initial Approach with Standard Sort An initial solution using standard sorting: #include<iostream> #include<algorithm> using namespace std; ...

A persistent segment tree maintains a complete history of all structural modifications applied to the data structure. Unlike standard implementations that overwrite previous states, this variant preserves every version, enabling direct queries on historical configurations. The core technique relies on path copying, where only nodes along the mo ...

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; ...

Point decomposition, also known as centroid decomposition, is a powerful technique for efficiently solving path-related problems on trees. By recursively splitting the tree around its centroid, it ensures logarithmic depth of recursion, leading to optimal time complexity for many tree queries. The algorithm follows three core steps: Find the c ...

Given a base tree and a subset of its nodes, the virtual tree preserves the ancestral relationships among these nodes by including all pairwise LCAs and cnonecting them appropriately. This structure maintains relative node relationships while being linear in size relative to the input set. When nodes are sorted by their Euler tour order, the se ...

1. Prefix Sum Technique 1.1 One-Dimensional Prefix Sum The prefix sum algorithm is an optimization technique used to calculate the sum of elements within a specific range $[L, R]$ in $O(1)$ time after an $O(N)$ preprocessing step. In a naive approach, calculating range sums repeatedly would result in $O(N \times M)$ complexity for $M$ queries; ...

The objective is to compute the diameter of a given binary tree. In this context, the diameter is defined as the length of the longest path between any two nodes within the structure. This path does not necessarily need to pass through the root node. The length of a path is quantified by the number of edges connecting the nodes. Algorithmic Str ...

Problem Statement Given a sequence \(a_1, a_2, \dots, a_n\), select elements to delete such that the remaining subsequence maximizes the count of indices \(i\) where \(a_i = i\). The goal is to compute this maximum value. Initial Solution and Limitations A dynamic programming approach tracks the longest subsequence satisfying \(a_j = j\) after ...