Job Lookup (Codeforces 1666J)
Tags: Others, shortest paths

Julia's $$$n$$$ friends want to organize a startup in a new country they moved to. They assigned each other numbers from 1 to $$$n$$$ according to the jobs they have, from the most front-end tasks to the most back-end ones. They also estimated a matrix $$$c$$$, where $$$c_{ij} = c_{ji}$$$ is the average number of messages per month between people doing jobs $$$i$$$ and $$$j$$$.Now they want to make a hierarchy tree. It will be a binary tree with each node containing one member of the team. Some member will be selected as a leader of the team and will be contained in the root node. In order for the leader to be able to easily reach any subordinate, for each node $$$v$$$ of the tree, the following should apply: all members in its left subtree must have smaller numbers than $$$v$$$, and all members in its right subtree must have larger numbers than $$$v$$$.After the hierarchy tree is settled, people doing jobs $$$i$$$ and $$$j$$$ will be communicating via the shortest path in the tree between their nodes. Let's denote the length of this path as $$$d_{ij}$$$. Thus, the cost of their communication is $$$c_{ij} \cdot d_{ij}$$$.Your task is to find a hierarchy tree that minimizes the total cost of communication over all pairs: $$$\sum_{1 \le i < j \le n} c_{ij} \cdot d_{ij}$$$.

Input: The first line contains an integer $$$n$$$ ($$$1 \le n \le 200$$$) – the number of team members organizing a startup.The next $$$n$$$ lines contain $$$n$$$ integers each, $$$j$$$-th number in $$$i$$$-th line is $$$c_{ij}$$$ — the estimated number of messages per month between team members $$$i$$$ and $$$j$$$ ($$$0 \le c_{ij} \le 10^9; c_{ij} = c_{ji}; c_{ii} = 0$$$).

Output: Output a description of a hierarchy tree that minimizes the total cost of communication. To do so, for each team member from 1 to $$$n$$$ output the number of the member in its parent node, or 0 for the leader. If there are many optimal trees, output a description of any one of them.

Note: The minimal possible total cost is $$$566 \cdot 1+239 \cdot 1+30 \cdot 1+1 \cdot 2+1 \cdot 2=839$$$:  

Sample Inputs:
4
0 566 1 0
566 0 239 30
1 239 0 1
0 30 1 0

Sample Outputs:
2 4 2 0

Solution (Python):
from sys import stdin
input = stdin.readline
inp = lambda : list(map(int, input().split()))
''

def query(x1, x2, y1, y2):
    if x1 > n or x2 > n or y1 > n or (y2 > n):
        return 0
    if x1 <= 0 or x2 <= 0 or y1 <= 0 or (y2 <= 0):
        return 0
    ans = prefix[x2][y2] - prefix[x2][y1 - 1] - prefix[x1 - 1][y2] + prefix[x1 - 1][y1 - 1]
    return ans

def dfs(l, r):
    if l > r:
        return 0
    if dp[l][r] != -1:
        return dp[l][r]
    toadd = query(l, r, 1, l - 1) + query(l, r, r + 1, n)
    ans = float('inf')
    for mid in range(l, r + 1):
        value = dfs(l, mid - 1) + dfs(mid + 1, r)
        value += toadd
        if ans > value:
            ans = value
            best[l][r] = mid
    dp[l][r] = ans
    return ans

def path(l, r, p):
    if l > r:
        return
    ans[best[l][r]] = p
    path(l, best[l][r] - 1, best[l][r])
    path(best[l][r] + 1, r, best[l][r])
for T in range(1):
    n = int(input())
    prefix = [[0 for i in range(n + 1)]]
    for i in range(n):
        prefix.append([0])
        prefix[-1] += inp()
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            prefix[i][j] += prefix[i][j - 1]
    for j in range(1, n + 1):
        for i in range(1, n + 1):
            prefix[i][j] += prefix[i - 1][j]
    dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
    best = [[-1 for i in range(n + 1)] for j in range(n + 1)]
    dfs(1, n)
    ans = [-1 for i in range(n + 1)]
    path(1, n, 0)
    print(*ans[1:])

Solution (Python):
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('debug') not in [None, '0']
if DEBUG:
    from inspect import currentframe, getframeinfo
    from re import search

def debug(*args):
    if not DEBUG:
        return
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search('\\((.*)\\)', s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')
from collections import deque

def main():
    N = int(input())
    C = [list(map(int, input().split())) for _ in range(N)]
    pref = [[0] * (N + 1) for _ in range(N + 1)]
    for r in range(N):
        for c in range(N):
            pref[r + 1][c + 1] = pref[r + 1][c] + pref[r][c + 1] - pref[r][c] + C[r][c]

    def get_cost(l, r):
        res = pref[r + 1][N] - pref[l][N]
        res -= pref[r + 1][r + 1] - pref[r + 1][l] - pref[l][r + 1] + pref[l][l]
        return res
    dp = [[INF] * N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0
    split = [list(range(N)) for _ in range(N)]
    for ln in range(1, N):
        for i in range(N - ln):
            j = i + ln
            for k in range(i, j + 1):
                l = r = 0
                if i <= k - 1:
                    l = dp[i][k - 1] + get_cost(i, k - 1)
                if k + 1 <= j:
                    r = dp[k + 1][j] + get_cost(k + 1, j)
                if l + r < dp[i][j]:
                    dp[i][j] = l + r
                    split[i][j] = k
    par = [0] * N
    queue = deque([(0, N - 1, -1)])
    while queue:
        (l, r, p) = queue.popleft()
        k = split[l][r]
        par[k] = p + 1
        if l <= k - 1:
            queue.append((l, k - 1, k))
        if k + 1 <= r:
            queue.append((k + 1, r, k))
    print(*par)
if __name__ == '__main__':
    main()

Solution (Python):
import io
import os
import heapq
from collections import deque, Counter
FILE_INPUT_MODE = 0
if FILE_INPUT_MODE >= 0:
    if FILE_INPUT_MODE == 1:
        CURRENT_DIR = os.path.dirname(os.path.abspath(__file__))
        FD = os.open(f'{CURRENT_DIR}\\input.txt', os.O_RDONLY)
    elif FILE_INPUT_MODE == 0:
        FD = 0
    DATA = io.BytesIO(os.read(FD, os.fstat(FD).st_size))
    if FD != 0:
        os.close(FD)

    def input():
        return DATA.readline().decode().rstrip('\r\n')

def solve():

    def get(x1, y1, x2, y2):
        nonlocal s
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

    def dfs(u, v, p):
        nonlocal root, ans
        w = root[u][v]
        ans[w] = p
        if u < w:
            dfs(u, w - 1, w)
        if w < v:
            dfs(w + 1, v, w)
    n = int(input())
    c = [[0 for j in range(n + 1)] for i in range(n + 1)]
    s = [[0 for j in range(n + 1)] for i in range(n + 1)]
    for i in range(1, n + 1):
        a = [int(word) for word in input().split()]
        for j in range(1, n + 1):
            c[i][j] = a[j - 1]
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + c[i][j]
    dp = [[0 for j in range(n + 1)] for i in range(n + 1)]
    root = [[0 for j in range(n + 1)] for i in range(n + 1)]
    for u in range(1, n + 1):
        for j in range(u, n + 1):
            i = j - u + 1
            dp[i][j] = float('inf')
            for k in range(i, j + 1):
                cur = 0
                if k != i:
                    cur += get(i, 1, k - 1, n) - get(i, i, k - 1, k - 1) + dp[i][k - 1]
                if k != j:
                    cur += get(1, k + 1, n, j) - get(k + 1, k + 1, j, j) + dp[k + 1][j]
                if cur < dp[i][j]:
                    dp[i][j] = cur
                    root[i][j] = k
    ans = [-1 for i in range(n + 1)]
    dfs(1, n, 0)
    return ' '.join(map(str, ans[1:]))

def main():
    print(solve())
if __name__ == '__main__':
    main()