Algorithmic Problem Solutions from Competitive Programming Training
Shortest Path DAG and Convex Hull Optimization
This problem involves processing a transportation network where we need to compute both the shortest travel time and the maximum possible delay while still arriving on time.
Solution Approach
First, we construct the shortest path DAG by running Dijkstra's algorithm from the source node. Any edge no ...
Posted on Fri, 19 Jun 2026 17:23:03 +0000 by mamoman
Finding the K-th Bit in Recursively Generated Binary Strings
Problem Analysis
Given an integer n, a binary string sequence is defined where:
S1 = "0"
Si = Si-1 + "1" + reverse(invert(Si-1)) for i > 1
The task is to find the k-th character in Sn.
Key Observations
Examining the pattern reveals a recursive structure:
S1 has length 1
S2 has length 3
S3 has length 7
In general, |Sn| ...
Posted on Mon, 25 May 2026 20:54:38 +0000 by worldworld
Counting Array Inversions Efficiently
Problem Specification
Given a sequence of n integers, compute the total number of inversions contained within the array. An inversion is formally defined as a pair of indices (i, j) satisfying i < j and A[i] > A[j].
Constraints & Limits
Sequence length: 1 ≤ n ≤ 10<sup>5</sup>
Element values: 0 ≤ A[i] ≤ 10<sup>9</ ...
Posted on Sat, 23 May 2026 18:36:57 +0000 by garydt
Implementing Divide-and-Conquer Algorithms in C++: Closest Pair, Tournament Scheduling, Sorting, and Chessboard Covering
Experiment Objectives
Deepen the understanding of the divide-and-conquer design paradigm, including its core ideas, steps, and methodologies.
Enhance the ability to apply theoretical knowledge to solve practical computing problems.
Improve comprehensive skills in integrating various algorithmic concepts to resolve complex tasks.
Task Overview ...
Posted on Sun, 10 May 2026 20:21:51 +0000 by ame12