Overview

Starting from house \(1\), we need to find the visiting order (Hamiltonian path) that visits every house exactly once while minimizing the total travel cost \(|V_i-V_j|\times|i-j|\). Since \(N\le 20\), this can be solved with subset DP (bit DP).

Analysis

Key Observations

• Since “you can move directly to any unvisited house,” the only constraint on the path is the visiting order.
• In essence, this is “the shortest Hamiltonian path on a weighted complete graph (fixed start, free endpoint).”
• The cost is symmetric, and the weight of each edge can be precomputed as: $\( w(i,j)=|V_i-V_j|\times|i-j| \)$

Why Brute Force Doesn’t Work

Exhaustively searching all visiting orders yields \((N-1)!\) permutations (rearrangements of all houses except house 1).
For example, when \(N=20\), \(19!\approx 1.2\times 10^{17}\), which is far too large.

Solution Approach

Only “which set of houses has been visited” and “the last house visited” are needed for the next transition (the entire past order is unnecessary).
Using this property, we perform state-compressed DP (bit DP).

Algorithm

State

Since house \(1\) is already visited from the start, we track the visitation status of houses \(2..N\) using bits.

• \(M=N-1\) (the number of houses \(2..N\))
• mask: an \(M\)-bit integer
  
  • bit \(k\) (\(0\)-indexed) is 1 ⇔ house \((k+2)\) has been visited
• last: the current house (0-indexed, \(0..N-1\))
  • last=0 represents house 1, last=1 represents house 2, …

The DP is defined as: $\( dp[\text{mask}][\text{last}] = \text{"minimum cost to start from house 1, visit all houses in mask, and end at last"} \)$

Initial state: - Houses \(2..N\) have not been visited yet, so mask=0 - The current location is house 1, so last=0 - Therefore \(dp[0][0]=0\)

Transition

Choose one unvisited house nxt and move to it. - newmask = mask | (bit corresponding to nxt) - The transition cost is the precomputed \(w(last,nxt)\)

Written as a formula: $\( dp[newmask][nxt] = \min\left(dp[newmask][nxt],\ dp[mask][last] + w(last,nxt)\right) \)$

Answer

The fully visited state is full = (1<<M)-1. Since the endpoint is free: $\( \min_{last\in\{2..N\}} dp[full][last] \)\( is the answer (when \)N=1$, there is no movement, so the answer is 0).

Concrete Example (\(N=3\))

The visitation status of houses 2 and 3 is stored in 2 bits: - Start from mask=00 (no one visited yet) - For example, going to house 2 gives mask=01, last = house 2 - Then going to house 3 gives mask=11, last = house 3
In this way, updates depend only on the visited set and the last house.

Complexity

• Time complexity: \(O(N^2 \cdot 2^{N-1})\)
  For each mask (\(2^{N-1}\) possibilities), we transition from last (up to \(N\) choices) to nxt (up to \(N\) choices).
• Space complexity: \(O(N \cdot 2^{N-1})\)
  The DP table size is proportional to the number of states.

Implementation Details

• Managing only houses \(2..N\) with bits naturally handles the starting condition (house 1 already visited) and halves the number of states.

• In the transition, rem = full ^ mask is used to extract the unvisited set, then
  b = r & -r (lowest set bit) is used for fast enumeration.

• The DP array is flattened to one dimension as dp[mask*N + last] for speed and memory optimization.

• The cost \(w(i,j)\) is precomputed for all pairs (\(O(N^2)\)), so only additions are needed during DP.

  Source Code

import sys
from array import array

def main():
    input = sys.stdin.readline
    N = int(input())
    V = list(map(int, input().split()))
    if N == 1:
        print(0)
        return

    w = [[0] * N for _ in range(N)]
    for i in range(N):
        vi = V[i]
        ii = i + 1
        row = w[i]
        for j in range(N):
            row[j] = abs(vi - V[j]) * abs(ii - (j + 1))

    M = N - 1
    full = (1 << M) - 1
    INF = 10**18

    size = (1 << M) * N
    dp = array('Q', [INF]) * size
    dp[0] = 0  # mask=0, last=0

    for mask in range(1 << M):
        base = mask * N
        rem = full ^ mask

        if mask == 0:
            cur = dp[0]
            if cur != INF:
                r = rem
                w0 = w[0]
                while r:
                    b = r & -r
                    nxt = (b.bit_length() - 1) + 1
                    newmask = b
                    idx = newmask * N + nxt
                    val = cur + w0[nxt]
                    if val < dp[idx]:
                        dp[idx] = val
                    r -= b
            continue

        tmp = mask
        while tmp:
            b_last = tmp & -tmp
            last = (b_last.bit_length() - 1) + 1
            cur = dp[base + last]
            if cur != INF and rem:
                wl = w[last]
                r = rem
                while r:
                    b = r & -r
                    nxt = (b.bit_length() - 1) + 1
                    newmask = mask | b
                    idx = newmask * N + nxt
                    val = cur + wl[nxt]
                    if val < dp[idx]:
                        dp[idx] = val
                    r -= b
            tmp -= b_last

    base = full * N
    ans = INF
    tmp = full
    while tmp:
        b = tmp & -tmp
        last = (b.bit_length() - 1) + 1
        val = dp[base + last]
        if val < ans:
            ans = val
        tmp -= b

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.