codingfreehard

Uplink

HackTheBox

Task: rooted tree network where each node can jump to any ancestor with cost = distance × transfer_speed + prep + receive; find minimum total cost to relay data to root for all nodes. Solution: tree DP with Convex Hull Trick (Li Chao Tree with rollback) to optimize over ancestor choices in O(N log MAX_VAL).

$ ls tags/ techniques/
optimizationshortest_pathdynamic_programmingtree_dpconvex_hull_trickli_chao_treerooted_treerollback
li_chao_tree_with_rollbacktree_dp_convex_hull_trickiterative_dfsdynamic_node_allocation

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

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:

...