Editorialist: Bhawna Jain http://www.codechef.com/users/bhawnamait
PROBLEMThe aim is to visit all control points once in some order and directly return to the first one such that the total distance is exactly L if it is possible so print POSSIBLE else print IMPOSSIBLE.
QUICK EXPLANATIONStart from 0,select a point which is the midpoint of your cycle find the subset contains (N-2)/2 points excluding midpoint and 0, find the perfect permutation (0,points inside the subset,midpoint,outside the subset) which gives you exact length L. If input not contains any such cycle print IMPOSSIBLE.
EXPLANATIONGiven a weighted graph ,determine whether there exist a cycle of exact length L when we visit all the points at once. Make all permutations of points and check if there exist any permutation for which the length is exactly equals to L.
However, the above logic will get TLE. The reason being,Time complexity for the above approach is o(N!) in worst it’s goes 14! = 89*10^9. we cannot pass the time limit with the above solution.
A good approach is to break the problem in half ,first select 0 as a starting point and loop over each point in O(N) for selecting midpoint . Find a subset containing X= (N-2)/2 (not containing 0 and midpoint )where X are number of the points we are visited before reached midpoint .takes time complexity o(2^N).
for midpoint = 1 to N // make each point as a midpoint
// Loop over every set of (N-2)/2 nodes half = (N - 2)/2;
for mask = 0 to(1<<N)
if mask&1 continue; // Contains start if mask & (1<<midpoint)) continue; // Contains midpoint if __builtin_popcount(mask) != half continue; // Number of nodes not correct //select the subset for k = 0 to 2 // Find all current nodes (those in mask for k = 0, // or those not in mask for k = 1) push(0); for i = 1 to N if i = midpoint continue if (k == 0) == ((mask & (1<<i)) > 0 push(i) push(midpoint)
After that problem is divided into two halfs, now we have to take permutation of (N-2)/2 points which are present in our subset and for half others which are not present in it,complexity reduce to o(N-2/2!) or o(N/2!), 7!=5040 which is in under complexity limits.
For every half cycle of length k,check whether there exist half cycle of length L-k. If we found any Permutation like that ,print POSSIBLE else IMPOSSIBLE. The worst case time complexity of this algorithm is O(N2^NN/2!).