Triangulation puzzle

Puzzles
#1

Hey there.

I’m having a real hard time for solving this one.
The really obvious solution is too slow to compute the result.
I implemented some kind of a dichotomic search, but it does not seems to validate in time. I pass every “simple test” (up until the 6th test) with no problems, but then, I don’t have enough moves to solve the two last tests.

I’d love to explain my current algorithm, but I’m afraid of giving too much information and spoiling the fun for the others :slight_smile:

Any advice on this one ?

2 Likes
#2

Hi.

Have you taken a look at the batman challenge review blog article ? It might contain just what you need to pass those elusive tests.
http://www.codingame.com/blog/en/2014/07/shadows-of-the-knight-top-codingamers-code-reviews.html

1 Like
#3

Hey !

I didn’t know there were review on the challenges ont he blog !
It actually gives a solution really close to mine, my way of dividing space was not exactly the same though. I think this is where the problem lies !

Thanks a lot !

1 Like
#4

in the task description the euclidean distance formula is given:
http://code.codingame.com/fileservlet?id=1459932446290

however, you don’t need to extract square root to compare the distances
for example:

// VectorDistance2 (hmg)
//
function VectorDistance2(const v1, v2 : TVector) : Single;
// EAX contains address of v1
// EDX contains highest of v2
// Result is passed on the stack
{$ifndef GEOMETRY_NO_ASM}
asm
      FLD  DWORD PTR [EAX]
      FSUB DWORD PTR [EDX]
      FMUL ST, ST
      FLD  DWORD PTR [EAX+4]
      FSUB DWORD PTR [EDX+4]
      FMUL ST, ST
      FADD
      FLD  DWORD PTR [EAX+8]
      FSUB DWORD PTR [EDX+8]
      FMUL ST, ST
      FADD
{$else}
begin
   Result:=Sqr(v2.V[0]-v1.V[0])+Sqr(v2.V[1]-v1.V[1])+Sqr(v2.V[2]-v1.V[2]);
{$endif}
end;
#5

Why in the world would you show an Assembly Level Code

2 Likes
#6

Btw I need help on this. I can pass everything except the last one.
Ive used a board to store the area that is to be searched .Something like : char board[10000][10000];
But the problem is that I cant iterate a 8000 X 8000 board under 100 ms. :stuck_out_tongue:

So I put a condition :smile:

if( w>=5000)
    w/=4;
if( h>=5000)
    h/=4;

And :smile: luckily for me the bomb was in the top corner :stuck_out_tongue: So I kinda temporarily solved it.
But I still want to learn how to really solve it. I read the blog and they dont really explain their approach properly and I dint understand that also.

#7

I find the title and topic very misleading. What does the problem have to do with triangulation ?

#8

My approach is quite difficult to implement, but it’s easy to understand:

Quick Observation:
Our blue/active area (where the bomb can be installed) is always convex polygon

So what we’re gonna do?

  • Let’s select point randomly where we want to go
  • Divide active polygon into two polygons along the perpendicular line to move vector (one of them will be next active polygon) and compute area each of them. (area1 and area2)
  • Remember value of min(area1, area2) and store the point with the largest one.
  • Repeat all until end of time (for me it was about ~25k iterations)

So, in a nutshell, we’re looking for a point that will slice active area into two equal halves.

Some improvements:

  • We can improve process of drawing new points - we can randomly choose point from ACTIVE AREA and compute reflection of current point from chosen one (chosen point will be on the line that slices polygon), but we have to care for cases when reflection point is outside of allowed rectangle).
  • We can add some heuristics to process of picking points - for example: distance to centroid of polygon.

Good luck!