CareerCup

We can treat this as a shortest path problem.
Going from chest to clue A, then to clue B and returning to chest, does not affect the result of picking all clues except A and B.
So we can use dynamic programming with bitmasks (handy that N <= 24). We can process the bitmasks in ascending order from 1 to 2^N - 1. A bitmask will have bit i set to 1 if we need to pick clue i. The minimum cost of selecting a set of clues is given by:
- the cost of picking one of the clues with bit set to 1 + the cost of picking all the other clues
- or the cost of picking 2 of the clues with bit set to 1 + the cost of picking all the other clues

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX = 24;
int dp[1<<MAX], N, sx, sy, x[MAX], y[MAX], dist[MAX][MAX], chest_dist[MAX];

int main() {
	int nt, t, i, j, all_mask, mask, cost;
	scanf("%d", &nt);
	for (t = 1; t <= nt; t++) {
		scanf("%d %d %d", &sx, &sy, &N);
		for (i = 0 ; i < N ; i++) {
			scanf("%d %d", &x[i], &y[i]);
			chest_dist[i] = (x[i]-sx)*(x[i]-sx)+(y[i]-sy)*(y[i]-sy);
		}
		for (i = 0 ; i < N ; i++)
			for (j = i+1; j < N ; j++)
				dist[i][j] = (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);

		dp[0] = 0;
		all_mask = (1 << N) - 1;
		for (mask = 1; mask <= all_mask; mask++) {
			// mask with bit i set to 1 if we need to pick clue i
			dp[mask] = INT_MAX;
			for (i = 0 ; i < N; i++)
				if (mask & (1 << i)) {
					// pick clue i and come back to chest
					dp[mask] = min(dp[mask], 
                                  chest_dist[i]*2 + dp[mask ^ (1<<i)]);
					for (j = i+1; j < N; j++)
						if (mask & (1 << j)) {
							// pick clues i and j, come back to chest
							cost = chest_dist[i]+chest_dist[j]+dist[i][j] + 
                                     dp[mask ^ (1<<i) ^ (1<<j)];
							dp[mask] = min(dp[mask], cost);
						}
				}
		}
		printf("%d\n", dp[all_mask]);
	}
	return 0;
}

NP complete my son said

I Got the Solution...it can be done using bit masking DP

please answer soon someone :(

My approach is as follows:
Step 1: Make the "Clue Box" to origin and make all points relative to that
Step 2: For all the pairs (all combination of two) of clues find the angle between them. If the angle between them is less than or equal to 90 degree then it is considered as acceptable. (If there are two nodes whose angle difference between them is greater than 90 then it is better to visit them separately)
Step 3: For all pairs of acceptable nodes sort them in the order of distance between them. Note: The distance metric is as per given in the problem statment
Step 4: Take each edge (sorted order) and compute the distance needed to get those two clues. (Remove both the nodes from a HashMap)
NOTE: We track all nodes using a HashMap (python Dict)
Step 5: Once all the edges are over, iterate through the HashMap and add the cost to visit those independent nodes.
Return the result

import math
import pdb 
import itertools

#arr = [(1,1),(4,3),(3,4),(0,0)] #containing all points
#arr = [(-3,4), (2,2) ]
#arr = [(0,0), (1,1), (-1,1), (1,-1), (-1,-1)]
#arr = [(0,0), (0,1), (0,2)]
arr = [(0,0),(0,5),(1,5),(5,1),(5,0),(-5,-5)]

nodeDict = {} #dictionary containing all nodes
distanceArr = []
totalDistanceTravelled = 0 

def myComparator(x, y): 
  if y[2] < x[2] and y[2] < x[2]:
    return 1
  if x[2] == y[2] and x[2] == y[2]:
    return 0
  return -1


def angleDiffAndDistance(index):
  index1, index2 = index
  degs1 = math.degrees(math.atan2(*arr[index1]))
  degs2 = math.degrees(math.atan2(*arr[index2]))
  diff =  abs(degs1-degs2)
  if diff >= 270 or diff <= 90: #acceptable angle difference
    distance  = (arr[index1][0] - arr[index2][0])**2 + (arr[index1][1] - arr[index2][1])**2 
    distanceArr.append((index1, index2, distance))

def getDistance(index1, index2): 
    distance = 0 
    distance  = (arr[index1][0] - arr[index2][0])**2 + (arr[index1][1] - arr[index2][1])**2 
    distance += (arr[index1][0])**2 + (arr[index1][1])**2  
    distance += (arr[index2][0])**2 + (arr[index2][1])**2  
    return distance

def getSingleDistance(index1): 
    distance = 0 
    distance += (arr[index1][0])**2 + (arr[index1][1])**2  
    return 2*distance

if __name__ == "__main__":
  #Making relative to Origin
  originX, originY = arr[0][0], arr[0][1]
  for i in range(1, len(arr)):
    arr[i] = (arr[i][0]-originX, arr[i][1]-originY)
  arr = arr[1:]    
  indexes = [i for i in range(0, len(arr))]  
  for i in indexes:
    nodeDict[i] = 0   
  combinations = itertools.combinations( indexes, 2)

  for i in combinations:
    angleDiffAndDistance(i)
  distanceArr.sort(myComparator)
  print arr
  print distanceArr
  for i in distanceArr:
    if i[0] in nodeDict and i[1] in nodeDict:
      del nodeDict[i[0]]
      del nodeDict[i[1]]
      totalDistanceTravelled += getDistance(i[0], i[1])
  for node in nodeDict:
    totalDistanceTravelled += getSingleDistance(node)
  print totalDistanceTravelled