successboy123
BAN USERMy 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
I don't know if the Trie data Structure would work. For example lets assume that the Trie contains "14.01" and "15.01" and we are searching for "14.99". In the Trie we would proceed as follows "1" -> "4" -> "." Then the only subtree is "01" and Hence the result we get is "14.01" while in reality "14.99" is closer to "15.01".
- successboy123 September 25, 2013Using a Binary Search tree can solve this problem. While traversing the BST we can continue to track the "Minumum difference" found till the current Node and return the "Global minumum" found at the end.
Time O(lg n) and constant space.
public float findClosest(float element) throws IllegalArgumentException{
if (head == null){
throw new IllegalArgumentException();
}
Node traversePointer = head;
float min = Math.abs(head.value - element);
float minElement = traversePointer.value;
//Traverse through all the nodes and find out
while (traversePointer != null ) {
if (min > Math.abs(traversePointer.value - element)) {
min = Math.abs(traversePointer.value - element);
minElement = traversePointer.value;
if (min == 0) {
return minElement;
}
}
if (traversePointer.value > element) {
traversePointer = traversePointer.left;
}else {
traversePointer = traversePointer.right;
}
}
return minElement;
}
Solving in java using Dynamic programming approach. At each index 'i' we iterate back to see how many maximum elements can be included in the set ending at i'th index.
Running time is qudratic O(n^2)
public static int maxLen(String input) {
char[] arr = input.toCharArray();
int[] dp = new int[arr.length]; //auxillary array used by DP
Set<String> elements; //Set used to store unique elements
int max = 0;
for (int i=0; i < arr.length;i++) {
//Step: Iterate from i to 0
//Step: Check how many unique element is contained from j to i
//Step: if 4 then dp[i] = i-j
elements = new HashSet<String>();
int j=i;
for (; j >= 0; j--) {
elements.add(Character.toString(arr[j]));
if (elements.size() == 4 ) {
dp[i] = i - j;
break;
}
}
//If reached end of array
//It means there were atmax 3 unique elements from 0 to index 'i'
if (j == -1){
dp[i] = i+1;
}
}
//Just find the maximum element in DP array
for (int i=0; i< dp.length; i++) {
if ( dp[i] > max) {
max = dp[i];
}
}
return max;
}
Approach:
1. First search for the index of the element which is inverted. Example in the example given array {5,6,7,8,9,10,1,2,3,4} the index is '5' (element 10). Running time (lg n) [Modified binary search]
2. Do an ordinary binary search in the appropriate sub-array.
- successboy123 September 29, 2013