Uplink — HackTheBox

Description

You, the Manager, control a network of computers, filled with information about your enemies. However, transferring data from one computer to your computer is taking too long. Figure out the least amount of time required to transfer information from a computer to your computer for all computers.

The challenge is served as a web-based coding environment (Monaco editor) at a given host:port. You submit code (Python/C/C++/Rust) via a /run API endpoint that accepts JSON with code and language fields, then runs the code against hidden test cases.

Problem details:

• Network is a rooted tree (root = node 1, your computer).
• Each node i has: parent[i], dist[i] (edge distance to parent), transfer[i] (transfer speed), prep[i] (preparation time), receive[i] (receiving time).
• A node can "jump" (send data) to any ancestor. Cost of jumping from node i to ancestor a = Distance(i,a) × transfer[i] + prep[i] + receive[a].
• Distance(i,a) = sum of edge weights on the path from i to a.
• Goal: For each node 2..N, find the minimum total time to send data to root through a chain of jumps.
• Constraints: N up to 500,000; all values up to 1,000,000.

Analysis

DP Formulation

Define:

• depth[i] = sum of edge distances from root to node i
• dp[i] = minimum total time for node i's data to reach root
• dp[1] = 0

For node i jumping directly to ancestor a, the single-hop cost is:

transfer[i] × (depth[i] - depth[a]) + prep[i] + receive[a]

The total cost through a chain of jumps is minimized by:

dp[i] = min over ancestors a of:
    transfer[i] × (depth[i] - depth[a]) + prep[i] + receive[a] + dp[a]

Expanding and rearranging:

...