Feel free to send your feedback or ask some help here!
1 Like
Can anyone provide some hint about how to start?
Doing binary search for each coordinate individally works most of the time (75%). If you want 100% you will have to work on both ranges at once AFAIK.
Also - first jump I’m making is just a mirror of a starting postion. That way I’m cutting possible area in most efficient way.
2 Likes
I first thought that it was inneficient to search each coordinate individually, but I changed my mind. Cuting the zone in half is as good if the cut is horizontal, vertical or diagonal. Most importantly, its way easier to keep track of the remaining zone if the cuts are horizontal and vertical. So you should concentrate on the one dimensional problem (“Tower” test) and then just repeat for the second dimension. The though part is to determine where to jump to minimize the area remaining (in the worst case) after a few jumps , you can’t always cut in half, and you shouldn’t each time you can…
I really enjoyed this puzzle !
6 Likes
UVA 10084 is a puzzle on the same idea but from a different perspective. Somehow reading that puzzle helped me to progress in this puzzle 
The following review provides additional hints:
1 Like
Umpff, no matter what I try, I don’t manage to past the last test!
I always am like 5 rounds away of success: what am I missing?
I basically move from centroid to centroid, and I update the zone to explore each time depending on the result of the detector… Is there some trick to improve the algo?
I tried to move to the furthest remaining point instead of to the centroid, to search x y individually… nothing work.
Thanks by advance!
My code uses a hodgepodge of approaches. I start out with mirroring my position around the centroid, with special code to handle OOB condition. If that returns a ratio of WARM:COLD areas that is beyond some threshold, then I move to the farthest point on the polygon from my current point and then switch back to centroid again. If I get below a certain threshold of rooms, then I shove them all in a collection and search for a point that gets me closest to 50% split. That last one is just me being lazy with floating point errors, though. It shouldn’t be necessary.
- danBhentschel
Ok thanks! I managed this by mirroring the centroids by 50% (sorry if this is not clear), good idea!
How can I check my code?
Everytime I try a test case it shows I’m sending nothing but doesn’t show any error code, I supouse I have any mistake in my code but as long as I can’t check it step by step I’m not sure where is it crashing
Most people managed to get 100% by searching y and x separately.
Then maybe the pick order - which side to cut first is important in this case. Idono, wasn’t able to make it with binary search on x and y separately.
OK, as someone who is way better in maths than in programming I found this one pretty interesting: once you’ve found the algorithm it should not be very hard to code it. In order to help those who might not be comfortable with the maths, the key here is to understand that the area of research (“AR”) is a CONVEX POLYGON (polygon where the angles on the inside are below 180°). One of its very useful property here is that each line crossing a convex polygon by its centroid splits it in two equal areas. So my solution process the centroid and then calculate the next position so that: dist{current batman pos, centroid} = dist{next batman pos, centroid}. That means that the next batman pos is not necessarily the “mirror” position; but it is on a circle… (be careful thought, if the whole AR is on the bisection of the previous and the next Batman pos, it won’t be very useful… 
)
Finally do not forget that the convex polygon means that for each floor, there are only one left bound and one right bound that delimitate the AR on this floor (except if the whole floor is not in the AR) . So use the bounds and dichotomy to process each floor if you want to pass the last test.
With this solution (optimal mathematically I guess (?), as the AR is always split in 2) I managed to have 5 turns left on the final test. The most difficult part for me was the “tower”, as there cannot be any circle: you’ll have to use the best approximation… (the area is not split in 2, but you’ll have to find the optimal split).
Good luck, i hope you’ll have as much fun as me on this one 
20 Likes
why for test 7 when i gave 498 498 after (x0,y0)=(501,501) the game will respond with COLDER not WARMER (is there a problem in calculating the distance between) ?/
can anyone help by giving some hints on how to start? thank you so much
Basically, its an implementation of binary search.
however, to get the centre, you need to mirror the current coordinate on the centre for the next coordinate
it is possible to do one coordinate first, and then the next
1 Like
Okay I just completed this one (my very first very hard puzzle!!).
Thanks a lot codingame, for this wonderful puzzle
3 Likes
I started this puzzle just after completion medium-level Episode 1. As this task is harder, I expected it in the hard category, havn’t checked it in advance. When I finished Episode 2, I was surprised this puzzle is in very hard category. I do not believe it! IMHO it would be “very” if there were a test, that cannot be passed by solving each coordinate individually. Working with centroids is much harder (I can’t), than keeping track of min and max for an axis. Cutting the zone in half horizontally etc is OK while jumps are not limited, but with OOB problems there should be more effective way if jumps are not limited to rectangles. I have no example right now, but I do believe it can be found.
As more mathematician than programmer I used kinda similar but different approach. I store all possible bomb positions in horizontal intervals for each y. In big loop I Monte-Carlo next move and check areas corresponding to all three possible results. Lets call them n0, n1, n2. I minimaze “max(n0, n1, n2) - min(n0, n1, n2)” to choose the best next move. A bit tricky part was to abort MC. I could break cycle with timecheck but due to laziness I placed counter until C / (down_y - up_y + 1) since complexy of calculation of n0, n1, n2 is O(down_y - up_y + 1), where down_y is y coordinate of the lowest possible bomb position and up_y stands for the highest. And one exception was when you have no possible move with more than one nonzero n0, n1, n2 (in Tower it happens for example). In that case I output a random possible bomb position.
Amazingly, but this worked (Monte-Carlo for this puzzle)!
As mentioned above, mirroring the bisector of the search space will implement a binary search, and will get you about a 50% score. The problems you have will be when you can’t perform this mirror move because it would take you off the grid.
Finding a simple, greedy alternative move in these situations allowed me to solve all but the last puzzle. Finding a more optimized alternative move is what got me 100%. This involved pencil + paper and math scribbling more than programming.
My advice would be to realize that bombs near the edge of the grid are much harder to triangulate than bombs near the centre, and you will need to account for this somehow to improve your worst-case outcome. Good luck!
2 Likes
Got the 100% but it’s frustrating to see that a dirty horizontal then vertical search works better than an elegant solution just because of the 150ms mandatory response.
2 Likes