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