RRSERVER - Editorial

Practice

Contest

PROBLEM LINK:

Author: Roman Rubanenko

Tester: Tuan Anh

Editorialist: Florin Chirica

DIFFICULTY:

medium

PREREQUISITES:

bitmask DP

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.

From empty permutation we add {5}. Now, we have to add 1 to the cost, as long as value 1 is not added. Next element is 4, and permutation is {5 4}. Since 1 is still not added, we increase cost by 1. Let’s add 1. This step, cost increases by 2 (once for 5 element and once for 4 element). Now, permutation is {5 4 1}. Pairs (5, 1) are now connected, and more its cost is added correctly (it is 2 and it was added in 2 steps: when 4 was added to permutation and when 1 was added to permutation). By now, we no longer have to worry about cost of element 5. We still need to worry about cost of element 4, since element 2 is still not added. We add 3, we increase cost by 1 and we add 2, we increase cost by 1. Now, once again (4, 2) is connected, so we don’t have to add extra cost for element 4. We add element 6 and zero additional cost needs to be added. We get 1+2+1+1 = 5, exactly the cost of the permutation.

From this example we can get a working algorithm. Suppose we have a mask and we add value x. Suppose dp[mask] is the minimal “partial cost” (as seen above) to fill first cnt positions (cnt = number of bits of mask) with elements with bit one in the mask and we extend mask with x (x has a zero bit in the mask). How does the “partial cost” modify? Before adding x, we add 1 for each two elements (a, b) that need to be connected, such as exactly one of a and b has a one bit in the mask (if none of them is, none was added yet - so no point to add to cost; if both are - then they are paired and again there is no point in adding extra cost). So, if we have another dp2[mask] = number of elements (a, b) that need to be paired such as exactly one of a and b are in the mask, then we can do dp[mask | (1 << x)] = min(dp[mask | (1 << x)], dp[mask] + dp2[mask]).

We reduced the problem to calculating dp2 array. An observation, which in fact allows this array to exist, is that in any order we place elements from mask corresponding to 1 bits, dp2[mask] remains the same. That being said, given the mask, let’s extend it with a value x. Let’s calculate dp2[mask | (1 << x)]. Some elements that must be paired can appear now two times in the mask. Other may appear now only one time. How to tell. Initially, dp2[mask | (1 << x)] = dp2[mask]. Let’s take each element y such as x and y need to be paired. If y appears in the mask, now we need to decrease dp2[mask | (1 << x)] by 1 (it’s the case when two paired elements appear both in a mask now). Otherwise, we need to increase dp2[mask | (1 << x)] by 1 (it’s the case when, from two elements, only one appears; now x appears and we need to increase, until y also appears).

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

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 ‘-’)

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”

You can actually edit it yourself for stuff like this.

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

Awesome explanation.

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

//