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↵
~~~~~↵
↵
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↵
~~~~~↵
↵
