Overview

This is a problem of minimizing the total travel cost among all routes that visit each of \(N\) houses exactly once. The travel cost is calculated as the product of the elevation difference and the house number difference.

Analysis

Since the number of houses \(N\) is at most 20, trying all permutations would result in \(19! \approx 1.2 \times 10^{17}\) possibilities, making brute force infeasible. Therefore, we consider an efficient solution using dynamic programming.

The key observation is that the minimum cost from any state is uniquely determined by just the set of visited houses and the last visited house. This allows us to reduce the number of states to \(2^N \times N\) (approximately \(20 \times 2^{20} \approx 20 \times 10^6\)).

Algorithm

We apply dynamic programming with bitmasks (Bit DP).

• State: dp[state][last] = the minimum cost when the set of visited houses is state (bitmask) and the last visited house is last
• Initial state: Only house 1 is visited (state=1<<0), the last house is house 1 (last=0), with cost 0
• Transition: From the current state (state, last), move to an unvisited house next_node
  • Travel cost: abs(V[last] - V[next_node]) * abs(last - next_node)
  • New state: state | (1<<next_node), with the last house being next_node
• Answer: The minimum cost among all states where all houses have been visited (state=(1<<n)-1)

Complexity

• Time complexity: \(O(2^N \times N^2)\)
• Space complexity: \(O(2^N \times N)\)

For \(N=20\), this results in \(2^{20} \times 20^2 = 1048576 \times 400 \approx 4.2 \times 10^8\) computations, which is sufficiently executable even in Python.

Implementation Notes

• Manage the states using a two-dimensional array of size \(2^N \times N\)

• Initialize with a sufficiently large value (INF)

• Use bit operations to efficiently update states

• Finally, find the minimum value among all states where all houses have been visited

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    V = list(map(int, data[1:1+n]))
    
    total_states = 1 << n
    INF = 10**18
    dp = [[INF] * n for _ in range(total_states)]
    
    dp[1][0] = 0
    
    for state in range(total_states):
        for last in range(n):
            if dp[state][last] == INF:
                continue
            for next_node in range(n):
                if state & (1 << next_node):
                    continue
                next_state = state | (1 << next_node)
                cost = abs(V[last] - V[next_node]) * abs(last - next_node)
                if dp[next_state][next_node] > dp[state][last] + cost:
                    dp[next_state][next_node] = dp[state][last] + cost
                    
    ans = min(dp[total_states-1])
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by deepseekv3.