Freaks City

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

Tree-Based Resource Distribution When distributing a fixed quantity of resources across a tree structure where each node must eventually hold an equal amount, removing any edge partitions the graph into two independent substructures. Let the total resource sum be $S$ and the number of nodes be $N$. The target allocation per node is $k = S / N$. ...

DP optimization often feels like an arcane art. The question arises: can anyone actually devise such solutions during a programming contest? (Perhaps I'm still learning this skill.) The core ideas I've encountered fall into these categories: When transitioning from state i to i+1, the number of states that change is small, so we can inherit val ...