No. Of decreasing places among set of points

general
1

I have an idea for a problem but i am not too sure of the solution myself. I have a complicated solution which should work(i think).But there might be a more efficient solution. So check this out and tell me if you get a better solution.

You are given n points in k dimensional space. You have to arrange the points in such a way that no. of decreases of coordinate values among adjacent pair of points is minimum.
Here is an example

For n =4 k =3 and points being (1,4,100), (2,3,5), (4,11,15) , (10,20,30)

Given order is one of the minimal orders and answer is 2 because of 4 to 3 and 100 to 5

About constraints

For k=2 i strongly believe that there must be some adhoc solution though i could not come up with one yet.
My soln is for constraints like n=100 k can be anything but i think setting k=5 would make it tricky.

2

Note: This is similar to 2015 World finals problem C.

@anudeep: Can you please check problem C in https://icpc.baylor.edu/worldfinals/problems/icpc2015.pdf and tell if this is different enough to be asked?

Here is the solution for any K.

Consider a graph with n nodes .

Let C[i][j] be the no. of decreasing values from point i to point j.

Then add an edge from vertex i to vertex j with Cost C[i][j].

Now the problem reduces to finding a hamiltonian path in this graph with minimum cost.

This can be done with mincost maxflow with the following graph.

For every vertex i in original graph have 2 copies, in-i and out-i.

Have 2 temporary vertices temp-source and temp-sink.

From source to temp-source add an edge of cap = 1 , cost = 0.

For temp-sink to sink add an edge of cap = 1, cost = 0

For all i , add an edge from temp-source to in-i with capacity = 1 , cost = 0.

For all i , add an edge from out-i to temp-sink with capacity = 1 , cost = 0.

For all i , add an edge from in-i to out-i with capacity = 1, cost = -infininty.

For all i,j(i != j) add an edge from out-i to in-j with capacity = 1, cost = C[i][j].

Now maxflow in this graph is 1 and mincost + infinity*(n) will give the required cost.

Cost = -infinity is required to ensure that the flow actually visits all vertices

temp-source and temp-sink are required to ensure that maxflow is 1.

3

The general problem is “Finding least cost hamiltonian path” which can be repeated i guess. The outer idea of construction of graph makes the problem different from the other one. I would put it in set.

4

Cool! We can use it then.