We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

# Hackerland Radio Transmitters

# Hackerland Radio Transmitters

antipyrrhus + 0 comments Key is to use greedy algorithm to always place the transmitter at the house furthest to the right possible to cover the range. O(n log n) solution due to the sorting at the beginning.

Arrays.sort(x); int numOfTransmitters = 0; int i = 0; while (i < n) { numOfTransmitters++; int loc = x[i] + k; while (i < n && x[i] <= loc) i++; loc = x[--i] + k; while (i < n && x[i] <= loc) i++; } System.out.println(numOfTransmitters);

techniker + 0 comments This is definitely not an easy problem. Incorrect difficulty marked.

abhishek021093 + 0 comments #!/bin/python3 import sys n,k = input().strip().split(' ') n,k = [int(n),int(k)] x = [int(x_temp) for x_temp in input().strip().split(' ')] x = sorted(x) #logic # 2 4 5 6 7 9 12 # Go as right as possible for first iteration # Again go as right as possible for second iteration # what does this mean that place transmitter in a such way that it will handle houses on left and right sides comfortably # So first you are at left most position.. iterate over and find middle position where (middle-left==k) and then find right most position where (right-middle<=k) count_trans = 0 last = x[0] i = 0 while(i < n): count_trans = count_trans + 1 next_point = x[i] + k while(i < n and x[i] <= next_point): i = i + 1 next_point = x[i-1] + k while(i < n and x[i] <= next_point): i = i + 1 print(count_trans)

Paul_Denton + 0 comments Why are ppl allowed to post solutions here? The solution discussion should only be accessible to people who already solved a problem!

jason_dam + 0 comments That was a hard-earned 15 points...

Sort the houses, then loop through and look for placement of transmitters. Keep track of where the transmitter was last placed each time.

If the last house is not in range of any transmitter, place one more on it.

Load more conversations

Sort 323 Discussions, By:

Please Login in order to post a comment