← All solutions

Shortest judge solution: 1310 bytes. Shortest team solution (during contest): 1359 bytes.

This problem has two rather independent components. The first component is to compute the shortest paths between the headquarters and every branch (in both directions). This part is completely standard and can be solved using Dijkstra’s algorithm.

The second part is to find an optimal partitioning of branches into subgroups. First let us formulate the problem more concretely. For branch i, let a_i denote the distance from headquarters to branch i, and b_i the distance from branch i to headquarters. Then, if we assign a set G ⊆ {1, …, b} of branches to the same sub-projects, the total distance travelled to deliver the messages within this group equals (|G| − 1) ∑_i∈G (a_i + b_i) (because each branch needs to send messages to and receive messages from the |G| − 1 other branches in the group). Since this only depends on the sum a_i + b_i, let us write c_i = a_i + b_i for brevity.

In other words, our goal is to partition {1, …, b} into s subsets G₁, …, G_s such that ∑_j=1^s (|S_j| − 1) ∑_i∈Sj c_i is minimized. This can be solved using dynamic programming.

Another way of phrasing the objective we are minimizing is ∑_i=1^b c_i · (g(i) − 1), where g(i) denotes the size of the group to which we allocate branch i. From this, we can observe that if c_i < c_j for some branches i and j, then we should have g(j) ≤ g(i) (otherwise, we can swap groups for i and j and get a better assignment). This also implies that we can assume without loss of generality that the smallest group contains the t₁ branches with largest c_i values (for some t₁), the second smallest group contains the t₂ branches with the remaining largest c_i values, and so on.

This gives a natural dynamic programming algorithm where we define D(i, j) to be the minimum distance of partitioning the i largest branches into j different groups. A straightforward dynamic programming algorithm using these ideas might use the recursive identity

D(i, j) = min_{1≤ k ≤ i} D(i − k, j − 1) + (k − 1) ∑<sub>i−k < ` ≤ i</sub> c`  (1)

representing that we can try all possibilities for the size k of the last group. However, this leads to an Ω(b² s) running time which is too slow. The final observation to make this fast enough is almost immediate given our observations and setup so far (but depending on exactly how one arrives at and formulates the b² s time solution, the last step may be hard to see): since we may assume that the group using the largest elements is the smallest groups, we may bound k in (1) above by i/j instead of i. This little change changes the running time of the resulting dynamic program to O(∑_i=1^b ∑_j=1^s i/j) = O(b² log s).