Expert.
Put your skills to the test.

Problem summary

A frog starts at the origin and can jump by (±1,±1). Among 2n given points, visit at least n in any order using the fewest jumps.

Constraints

1 ≤ n ≤ 6; coordinates are integers strictly between −1000 and 1000; each point has coordinates of equal parity; all points are distinct and nonzero.

Worked example

Official statement example.

2
1 1
3 5
4 6
8 2

5

Solution analysis

1. Between reachable points, the shortest jump distance is max(|dx|,|dy|). Both coordinate differences have the same parity, so after satisfying the larger displacement, alternating signs can satisfy the smaller one in the same number of jumps.
2. Use Held–Karp subset dynamic programming: dp[mask][v] is the minimum distance from the origin visiting the listed points in mask and ending at v. Initialize singleton masks with origin distances and extend by an unselected point until n points have been selected.
3. Minimize over all size-n masks and endpoints. For the sample, reaching (1,1) costs one jump and then reaching (3,5) costs four, totaling five. A shortest segment may pass through other given points; those extra visits only help the requirement.

Why it works

Any route visiting at least n targets has a first sequence of n distinct visited targets; its length is at least the sum of shortest distances between those successive targets, represented in the DP. Conversely concatenating shortest segments for a DP solution visits its n selected targets using its computed length. Thus neither incidental target visits nor omitted larger masks affect the optimum.

Watch out. Use Chebyshev distance, not Manhattan distance.,No return to the origin is required.

An independently written complete program with standard headers.

// Key idea: Any route visiting at least n targets has a first sequence of n distinct visited targets;
// its length is at least the sum of shortest distances between those successive targets, represented
// in the DP. Conversely concatenating shortest segments for a DP solution visits its n selected
// targets using its computed length.
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    int m=2*n;
    vector<int>x(m),y(m);
    for(int i=0;i<m;++i){
        cin>>x[i]>>y[i];
    }
    int states=1<<m,inf=1000000000;
    vector<vector<int>>dp(states,vector<int>(m,inf));
    vector<int>count(states,0);
    for(int mask=1;mask<states;++mask){
        count[mask]=count[mask>>1]+(mask&1);
    }
    for(int i=0;i<m;++i){
        dp[1<<i][i]=max(abs(x[i]),abs(y[i]));
    }
    int answer=inf;
    for(int mask=1;mask<states;++mask){
        if(count[mask]>n){
            continue;
        }
        for(int u=0;u<m;++u){
            if(dp[mask][u]==inf){
                continue;
            }
            if(count[mask]==n){
                answer=min(answer,dp[mask][u]);
                continue;
            }
            for(int v=0;v<m;++v){
                if(!(mask&(1<<v))){
                    int distance=max(abs(x[u]-x[v]),abs(y[u]-y[v]));
                    dp[mask|(1<<v)][v]=min(dp[mask|(1<<v)][v],dp[mask][u]+distance);
                }
            }
        }
    }
    cout<<answer<<'\n';
}