Dynamic Paths — HackTheBox

Description

"On your way to the vault, you decide to follow the underground tunnels, a vast and complicated network of paths used by early humans before the great war. From your previous hack, you already have a map of the tunnels, along with information like distances between sections of the tunnels. While you were studying it to figure your path, a wild super mutant behemoth came behind you and started attacking. Without a second thought, you run into the tunnel, but the behemoth came running inside as well. Can you use your extensive knowledge of the underground tunnels to reach your destination fast and outrun the behemoth?"

Connection: nc 154.57.164.65 30945

Analysis

Protocol Reconnaissance

Connecting to the server revealed the following protocol:

1. 100 rounds (grids) to solve sequentially
2. Each round provides dimensions i x j (2 <= i,j <= 100) and a flat list of numbers representing the grid
3. Goal: find the minimum path sum from top-left to bottom-right, moving only right or down
4. Server provides an example: 4x3 grid with answer 17 (path: 2 -> 5 -> 2 -> 1 -> 3 -> 4)

Key Insight

The challenge name "Dynamic Paths" directly hints at Dynamic Programming. This is a classic minimum path sum problem (equivalent to LeetCode #64):

• Given an m x n grid of non-negative integers
• Find a path from top-left to bottom-right
• Can only move right or down at each step
• Minimize the total sum of values along the path

Algorithm

Classic 2D DP with recurrence:

...