Noam527's blog

Unsolved problem — just sharing
By Noam527, history, 7 years ago, In English

Here is a problem I thought of. This is just for others' interest, maybe to help them pass the time. I thought of this problem initially because I wanted to put it in a contest, however it turned to be too hard for me and a few others so it shouldn't be in a contest:

you need to construct a permutation of length N. you're given M pairs of integers (each pair contains 2 distinct elements, both are between 1 and N). the permutation you construct needs to have the following value minimized: for each pair {X1, X2}, add up to the total sum the distance (indicies distance) between the values {X1, X2}. you can print any correct answer is multiple ones exist.

input:
N M
M pairs, described in the statement
output:
the minimized value described in the statement on the 1st line, and the permutation on the 2nd one.

examples:
input:
3 2
1 2
3 1
output:
2
3 1 2

input:
4 4
1 2
4 2
3 1
3 4
output:
6
2 1 4 3
  • Vote: I like it
  • +75
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Noam527 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
← Rev. 7   Vote: I like it -70 Vote: I do not like it

It seems that this interesting combinatorial optimization problem can be solved naively by exhaustive search when the permutation length N and the number of distinct pairs M are small.

The feasible domain of all permutations is N!, and it is possible for small N to compute the value of the objective function for all these permutations.

The minimum value of the objective function over all these permutations is the answer given in the first line of the program output, and any of the optimal permutation(s) can be written in the second line of the program output.

As M cannot exceed N.(N-1)/2, have you considered:

  1. an upper limit for M and N.
  2. that the optimization problem may be intractable, i.e. no polynomial-time exact algorithm for the solving the problem exists.

Best wishes

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    I thought it was pretty clear I was looking for a better solution than bruteforce in O(n! * (n + m)).

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -75 Vote: I do not like it

The following is a C++14 implementation of an exhaustive search algorithm for solving the problem when N and M are small:

#include <bits/stdc++.h>

using namespace std;

class Optimal_Permutation
{
    typedef pair< size_t, size_t > pair_t;

    size_t M, N, *P, *Q;

    pair_t *R;

    unsigned long long permutation_cost()
    {
        map< size_t, int > location;

        for( size_t i = 1; i <= N; i++ )
            location[ P[ i ] ] = i;

        unsigned long long cost = 0;

        for( size_t i = 0; i < M; i++ )
            cost += abs( location[ R[ i ].first ] - location[ R[ i ].second ] );

        return cost;
    }

public:

    unsigned long long min_cost;

    Optimal_Permutation() : min_cost( ULLONG_MAX )
    {
        cin >> N >> M;

        P = new size_t[ N + 1 ], Q = new size_t[ N + 1 ], R = new pair_t[ M ];

        for( size_t i = 0; i < M; i++ )
            cin >> R[ i ].first >> R[ i ].second;

        for( size_t i = 0; i <= N; i++ )
            P[ i ] = i;
    }

    void solve()
    {
        unsigned long long cost;

        do
            if ( ( cost = permutation_cost() ) < min_cost )
            {
                min_cost = cost;

                for( size_t i = 1; i <= N; i++ )
                    Q[ i ] = P[ i ];
            }

        while ( next_permutation( P + 1, P + N + 1 ) );
    }

    void write_result()
    {
        cout << min_cost << endl;

        for( size_t i = 1; i <= N; i++ )
            cout << Q[ i ] << " ";
    }
};

int main()
{
    Optimal_Permutation problem;

    problem.solve();

    problem.write_result();
}
→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -46 Vote: I do not like it

Many thanks, anonymous down voters.

You just made my day more interesting, witnessing patiently how much just trying to share comments and remarks that maybe helpful to someone may be unlikable to someone else.

Best wishes

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

There is a soution with O(2^N*N) complexity,

You can practice here — https://www.codechef.com/problems/RRSERVER

→ Reply