# RRSERVER - Editorial

Practice

Contest

Author: Roman Rubanenko

Tester: Tuan Anh

Editorialist: Florin Chirica

medium

### PROBLEM:

You’re given m pairs (x, y). We define the cost of a permutation P1, P2, P3, …, PN in the following way:
for each pair (x, y), add to the cost distance between where is placed element x in the permutation and where is placed element y in the permutation. Find the minimal cost, for every permutation of length n.

### QUICK EXPLANATION:

Let’s keep a bitmask DP. The state is servers that are already placed, from left to right. The mask determines uniquely the wires that are going right and still have no pair (for a pair (x, y) from the m ones, we can find number of them such as only one of servers x and y has a slot). To extend a mask, find a server which was not added before and place it to the rightmost slot.

### EXPLANATION:

Restriction n <= 20 immediately suggests us an exponential approach. Let’s note slots by positions in permutation and servers by values of permutation. We can keep a bitmask to store already placed values of permutations (we’ll use the standard convention: bit 1 if value was placed or bit 0 otherwise). Suppose current bitmask has cnt 1 bits. This means, permutation was already completed at positions 1, 2, …, cnt with values corresponding to 1 bits from bitmask.

Let’s add a value not used yet. Problem asks us to trace back to all values x, already added, such as x and y must be connected, and add to the solution distance between position of x and position of y (position of y - position of x). We can determine easily values x using the mask, but we can’t determine their positions. Another approach is needed. We need to make a reduction of the problem.

Once again, let’s add a new value to the permutation, called y. Let’s consider all values x, such as x and y must be connected. If x was already in the permutation, we do nothing (let’s assume distance between x and y is already added). Otherwise, x needs to be added. The trick is to add to the cost of permutation 1, until x is also added, then we add nothing more. Let’s suppose we need cost for (5 4 1 3 2 6) and pairs (5, 1) and (2, 4) need to be connected. Let’s add its cost step by step.

The complexity of presented solution is O(n * 2 ^ n), since number of masks is 2^n and for each mask, we try to extend it by one of n elements.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution to be updated soon
Setter’s Solutions

5 Likes

Can someone rephrase the problem statement? I’m still not able to understand what we had to do? That example didn’t help at all…

1 Like

For some reason, all problems except `RRPLAYER` are not visible on pages `http://www.codechef.com/problems/easy`, `http://www.codechef.com/problems/medium` and `http://www.codechef.com/problems/hard`.

instead of “add to the cost distance between where is placed element x in the permutation and where is placed element y in the permutation”, “add to the cost distance between where element x is placed in the permutation and where element y is placed in the permutation”

Can we not break the servers into sets of servers that need to be connected? And then find each set’s minimum spanning tree. I had thought of this during the contest but did not get time to implement. Has anyone tried this approach?

if the mask has lets say 3 bits which are 1’s then that mask represents that servers 1,2,3 are placed at the positions of the toggled bits in the mask in some permutation ? correct me if i am wrong.

@gkcs No a min spanning tree will not work in this case.

Consider a graph G=(V,E)

Minimum spanning tree essentially finds the best way to connect all V where the weight of each E is known beforehand. Now, the question is, how will you assign a weight to an edge E? Its not possible as the weight of an edge depends on its position relative to other vertices in the final solution. GT is not the way to go for this.

1 Like

In tester’s solution,
can anyone please explain the logic of this statement ?

f[s] = min (f[s], f[t] + len * (2*cnt - deg[pos]));

1 Like

Editorialist’s solution ???

Here’s my solution which follows the editorial’s approach :-
http://www.codechef.com/viewsolution/5634846

1 Like

One hell of a problem ! Really hard… I think I could make a solution with complexity O(N^2 * 2^N ) but that is more than what this problem needs!!!

take example:
5 3
2 1
2 3
4 5

so the best way to connect will be 1-2-3 4-5
hence length = 3 (no of ‘-’)

You can actually edit it yourself for stuff like this.

Awesome explanation.