Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @java_coffee_cup,validated by @pluieciel,@Rafarafa and @Timinator.
If you have any issues, feel free to ping them.
An interesting puzzle (as always from @java_coffee_cup…), well done!
Currently I fail some tests and I am a bit confused how to move on…
I converted the puzzle to the well-known set-cover problem, which is NP-hard. So, instead of an exhaustive search, I used a polynomial time greedy method. But, of course, this algorithm is not optimal in every case, so out of the 90 IDE test cases I pass only 60+ but fail in over 20, by overshooting the expected solution by 1 or 2.
I am not sure whether:
- my original reasoning was wrong and this is not an NP-hard problem at all
- the test cases are so small that we were expected to use an exponential brute force algo that is 100% correct
- indeed a greedy approximation solution was the expected approach, just a bit better than what I came up with.
I’ll add a few comments to your question that probably won’t help. I don’t understand how “greedy” fits into this problem. I kind of understand that a greedy approach can be used to determine an approximation, but I didn’t solve the problem until after I quit trying to figure out how to be greedy.
There are two other published Python solutions in addition to mine. All three algorithms revolve around the same formula. None of them feel greedy to me, but my knowledge of computer science theory is not vast.
1 Like
As my solution is not correct, maybe it is not a spoiler and allowed to describe it here:
- First I generate the list of candidate positions for the sensors: For each islet, a circle of radius
rintersects the coastline at at most 2 points. If a sensor is between these 2 points, then the sensor can cover this islet. These 2p (or less) points are the candidates. It is easy to see that no other candidate points along the coastline need to be considered, as any other sensor position can be replaced with the neighbouring points from this 2p list without any decrease in the coverage. - I filter out any duplications from the list of candidate sensor positions.
- For each candidate points we calculate which islets it can cover (by checking for all islets if the candidate point is within the range of that islet).
- The greedy part is in the process of selecting the sensor locations. In a loop I select the candidate that covers the highest number of remaining uncovered islets. After selecting a sensor location I update the coverage data for all other candidates (so that already covered islets are no longer taken into account). I stop when no islets to cover remained.
Note: I know this greedy method is incorrect, it is easy to construct a counter-example. E.g. imagine 5 islets that middle 3 can be covered with a single sensor, so the algo might select it first but then it needs 2 more sensors to cover the remaining 2 islets on the side. That is a total of 3 sensors. But maybe the 5 islets could have been covered by just 2 sensors, e.g one for 2 islets on the left, another for the 3 on the right.
Glad that you like taking this challenge.
Yes I think you are correct to treat it as a greedy problem.
My algorithm has some difference from yours. I did not try to find which circle can cover the most points. I tried to find the Leftmost or Rightmost circle that can cover (or touch, with a greedy mindset) something. Each circle will eliminate some islets from the map.
2 Likes
@Timinator and @java_coffee_cup: Thanks for the help!
I get it now, the solution is indeed very simple, I just completely missed this idea.
PS: while it is a set-cover cover problem, but not the general one. Because of the geometric meaning, the sets to cover have specific constrains. So of course the puzzle is not NP-hard, e.g. my solution is just O(n^2).
Correct me if I’m wrong, but once the points are sorted, the number of transmitters can be determined in one pass through the data, so (if you’re interested), I believe the best time complexity is O(nlogn).
3 Likes