LAZY01-EDITORIAL

PROBLEM LINK

Practice http://www.codechef.com/INLO2015/problems/LAZY01

Contest http://www.codechef.com/INLO2015

Editorialist: Bhawna Jain http://www.codechef.com/users/bhawnamait

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Permutation,Adhoc

PROBLEM

The 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 EXPLANATION

Start 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.

EXPLANATION

Given 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!).

http://www.codechef.com/viewsolution/6809254

//