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
```

Auto comment: topic has been updated by Noam527 (previous revision, new revision, compare).It seems that this interesting combinatorial optimization problem can be solved naively by exhaustive search when the permutation length

Nand the number of distinct pairsMare small.The feasible domain of all permutations is

N!, and it is possible for smallNto 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

Mcannot exceedN.(N-1)/2, have you considered:MandN.polynomial-timeexact algorithm for the solving the problem exists.Best wishes

I thought it was pretty clear I was looking for a better solution than bruteforce in

O(n! * (n+m)).Not really. If something has been pretty clear in Codeforces during the past 9 months, it is that

no assumptioncan be made about any problem.Not me!

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

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

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

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