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.
3 Likes
Thank you so much!!! I finally could be able to solve this puzzle by reading your comment! First time trying, I could only got all the test but the last one (which is really frustrating anyway 
) . Then after reading your statement, I could finally understanding what to do.
Guys (or girls), if you guys keep trying to mirror the coordinate through the bisector, it would make you jump back-and-forth around the edge if the the bomb is near the edge. And it would be reallyyyyyyyyyyyy time-consuming, considering that you have to visit the same old window multiple times. (And for me, the result is 5 rounds away from the actual number of rounds needed to solve the final case.)
So, my advice for you is that focus on the statement that Geropy has stated:
For anyone who could not wrap their head around this idea, I would give you a little hint:
Try to approach the edge fast, really, (but not too fast 
).
By doing this, I got 3 spare rounds in the last case. And I really hope you could come up with something like this, or even better!!! ^^
And as always,
Happy Coding!!!
3 Likes
coz the bomb is at 999,999
5 ≤ W constraint is not true in 3rd test, the tower one, since W = 1
1 Like
Fixed, thanks.
I also did the binary search separately for both coordinates with one optimization:
Because you cannot jump off of the grid, sometimes your next jump will not give you any information at all, just adjusts the position of the bat for future jumps. It makes sense to make these zero information jumps for both coordinates with a single two dimensional jump. Which means you have to work on both coordinates “in parallel”.
3 Likes
Hi, I’m stuck on this problem for a while.
I’m searching for the X and Y coordinates separately and everything’s fine since I pass every test.
But here is my problem : when I submit my code, I get 87% cause I pass every test but the FIRST one.
Of course, there is no way to know why I don’t pass this test because of submission mode.
Did any of you have the same problem or any idea of what could be the reason (I know the data in sub mode are slightly different)?
1 Like
Maybe this was the most messy task for me so far. No matter what I’ve tried it didn’t work, I had really tough time understanding why. At the end I got the logic with many many little tweaks and trials and errors and still everything is not clear to me why my solution works
I don’t understand, how could people solve this by searching for the X and Y coordinates separately. With two separate binary searches, IDE test cases 07 and 08 use too much jumps and fail for me, so I’m currently stuck at 75% and don’t know how to progress without hardcoding some jump-orders for specific testcases.
All I could say is searching separately for X and Y allows to reach 100% both during training and validation phase.
The sole tip I could give you is: if you know your next move won’t learn you anything, then change your search axis.
3 Likes
yo i searching it seperately but still don’t have enough run (n)
do u have any advice for me pls?
thanks for reading man
For those who are doing binary search separately for each axis, some tips:
- Try to go the next move that mirrors the current move with respect to the lower and upper bounds for the axis. (this cuts the search area by half)
- If the next such move is out of bounds, then get back to within the lower and upper bounds (I went into the centre for my code)
- When mirroring, there is a tip to reduce the number of runs, by mirroring with an odd distance. Here’s why:
a) When the result is “warmer” or “colder”, the centre row/column can be eliminated instantly
b) When the result is “same”, the centre row/column is the row/column with the bomb.
Hence, an odd distance mirroring can significantly cut down the number of runs, with a potential for a jackpot “same” result, revealing the row/column instantly.
5 Likes
One of the tests (More Windows) only give you 16 rounds to find the bomb, while map is 49x49 and bomb is located in the position on the picture. Is it possible to find it that fast or is the test broken or something? I’d like to know before I spend more time on this puzzle. Thank you.
i confirm that it is possible (we are 1495 to have successed)
moreover i can tell you that it is possible in 15 moves …
1 Like
Done. Nice and clan moving on multiple axes (not both at the same time though). This puzzle was a bit annoying. But it was worth the effort 