Tree Median (median)
3 teams scored 48 points on this task, for a maximum score of 16, an average score of 16 and a median score of 16.
Highlights
- M. Buonarroti, Trento is the institute with the most points (16).
- Trentino is the region with the most points (16).
Statement
You are given a tree with N nodes, numbered from 1 to N. The edges are numbered from 1 to N-1, and edge i has a weight w_i. Consider a simple path connecting two different nodes. If the weights on this path are w_i_0 ≤ w_i_1 ≤ … ≤ w_i_k (not necessarily in this order), then we define its median as w_i_\lfloor k / 2 \rfloor. Let M be the list of medians of all such simple paths (that is, |M| = (N (N-1))/2). What is the Kth smallest element of M?
Rank
Team
Institute
Region
Score
