Hi everyone, I'm Max.
One of the things I work on is preparing and test-solving problems for Google Code Jam.
I'm going to describe the problem "Triangles" from the Code Jam 2022
World Finals.
When writing most Code Jam problems, we come up with an interesting
programing problem and then invent a fun story around the problem itself.
This time we didn't write a story, and just stuck with a geometry problem,
because geometry is fun enough as it is,
So here it is!
The program must read from its input a set of points in two dimensions.
Then, the program needs to figure out a way to join up as many of those points
as possible into triangles, while satisfying certain rules.
The triangles cannot cross each other
-- any two triangles
must be either outside of each other, or one must be wholly inside the other
-- except that the vertices of a triangle can touch the edge of another triangle.
For example, these configurations are ok
but these are not.
The input set of points could be very large.
So a program would be too slow if it tried every possible way
to divide up the points into sets of three to make triangles.
So we need another method which can solve this quickly,
even for a large number of points.
If you want to try this problem on your own, head to g.co/codejam
after the round ends, where you can read all of our previous competition problems
and submit solutions to get feedback from our judging system.
And make sure to stay tuned
because once the round ends someone from the Code Jam team will walk
through the solution on the livestream. Good luck to everyone competing!
Hi, everybody.
I'm Pablo. I'm an engineer on the Code Jam team
and I wrote the Triangles problem
and I'm going to talk through some details about this solution.
So in this problem, we have a bunch of points
that we want to join to triangles,
and we want those triangles to fulfill some definition given in this statement.
So in order to solve the problem, what I'm going to do is
I'm going to construct and improve a theorem, that's important,
and then that construction, then we're going to make it efficient enough
so that our algorithim can actually perform it in time.
So here's the theorem.
The idea is that in a sense of 3T points, we can make exactly T triangles,
so basically use up every point, if at most 2T of them are collinear.
So the direction from top to bottom is kind of immediate
because if we have more than 2T collinear points
by the Pigeonhole Principle, at least three of them
are going to end up in the same triangle and then not make a valid triangle,
my direction on the other side is not.
So let's let's look at it.
So first, let's start with the case where there's the set of collinear
points that aren't really saturated It's kind of far from the from the maximum.
So let's say there's at most 2T - 2 collinear points.
So in this case, our strategy is going to be find any triangle
that doesn't interfere with anything else, because since these points are all collinear,
we cannot grab more than two of them for a valid triangle.
So any triangle is going to be okay because it's going to keep
the number of collinear points small enough.
So the way to do this is, let's say we have
lots of points, right?
We're going to find two extreme points.
There's multiple ways of doing this so this can be solved
but the easiest way is just to sort by X and then by Y,
and take the two most extreme points.
So in this case, this would be these two points.
RIght, so we pick these two points and now we want to find ourselves a third point.
And we're going to keep the triangle we pick in a different plane than everything else.
So that way we ensure it doesn't interfere with anything that happens later.
So because these are the two extreme points in this order,
we know that it's not going to be anything on this side of the line.
There could be some things on the line, but that doesn't really matter too much.
So the way to do is like we find, we rotate from here like this
and we find the first point by angle, right?
Because we already know that there's nothing on this side.
So as we move like this,
there's going to be nothing, nothing, nothing until the first point, right.
So we're guaranteed that above this line there's going to be nothing there.
So we could try this triangle.
Of course this in particular doesn't work, because there could be a point here.
But in this case, we can try from the other side.
So we rotate this, this, this, and then we find this point.
And then this triangle will work because this line also has nothing towards this side
The reason the second one worked
is because all the points on the first one didn't
is because all the points are
below the line that joins our first two chosen points.
So we need the other direction.
We don't need to check which is the right direction.
Ideally, we can just like go towards both sides and just keep the one that works.
If both of them work that's fine, we pick either one. Okay.
In this way, we get rid of one triangle,
we maintain the hypothesis so we just have a smaller set to solve.
Now for the other case.
So let's say we have at least 2T + 1.
Sorry, -1, collinears.
So in this case, if it's 2T collinears, we want like, every triangle's going
to have two points from the collinear set and one point from something else.
If it's 2T - 1, there's going to be two points
from the collinear set and one point from the other points
in all but the last triangle, or all but one triangle.
Okay, so let's do that.
So let's say we have this big set of collinear points,
Right, we have three, six, nine here, let's say ten.
And then we have five other points, three here and two here.
Right. So this is exactly 2T.
So what we're going to do is we're going to split the two sides of the line.
And since we have three six, we want to pair them with six collinear points
and we want to pick like the top six.
So one, two, three, four, five, six.
So we're going to pair this up and then pair this up.
And then again, because these two planes are separated by a line, triangles here and triangles here,
are not going to interfere with each other so we can just solve that separately.
If there's less, if there's 2T - 1, one of these is going to have one fewer point.
So let's see how to solve one of these where all points are on one side of the line.
So we can do something very similar as we did in the first stage
if we have all the points on one line,
and some more points all here,
because we picked the first two points in the collinear set,
so the highest two in this case.
And because we know there's nothing here, we can start rotating our imaginary line
until we find the first point and then we're guaranteed there's nothing above.
So this triangle here is in this plane, everything else in this plane
so this triangle doesn't interfere with any other triangle.
And we can keep doing that.
So we do that, we remove this, then we pick these two, we rotate again.
Let's say we find this triangle.
Notice that if there's many points that are tied by angle,
we want to pick the closest one, right.
Because we can slightly skew the line
so that there's still a separation line between the two planes.
Okay, so we can be going going until we have very few points.
So let's say we get to four points,
which is going to be the case if we have exactly 2T to start with.
So if you have four, then we have two out here it's going to be fine
because we are going to just find this triangle and this triangle and it's going to be okay.
However,
if we have only three,
we can run into a problem because that means we also have three non points not on the line.
And if we just find any triangle using two from the line,
it's possible that the other three end up being collinear.
So for this particular case in which we end up with three,
we need to do something else.
Since we only have six points, we can brute force it.
Just try every possible combination and see what works.
It's not hard to convince oneself by cases which I'm not going to do now
that every case with six points in which not more than three of them are collinear,
it's possible to build into two triangles.
The hardest one is when you have three sets of three collinear points like this,
and we can solve this case
with like one big triangle and another smaller triangle inside.
The other cases are somewhat similar
and this solves the problem and proves the theorem.
However we also need to implement this somewhat efficiently.
Taking triangles out in the first phase or in the phase where we are processing the collinears,
it takes linear times, which is quadratic overall, which is okay.
But the first phase can be slow if we keep re-computing
the largest collinear set because as we take triangles
in a greedy way, the largest collinear set might change
So there's a couple of ways of dealing with that.
One is to compute all the collinear sets
at the same time and keep them updated in a sort of priority queue.
But it can be very slow, even though it complexity wise seems efficient.
Another way is to only re compute the largest collinear set when we know it might have changed,
which only means recomputing a logarithmic number of times
but again, both of these approaches
have some logarithmic factors and some large concerns and are going to be too slow.
So the easiest way to deal with it
is to just ignore the largest collinear set at the beginning
and keep doing the greedy step in which we just find triangles.
So we find one triangle, then we find another triangle,
then we find another triangle.
And at some point if we can do it,
so if we take both directions and neither works,
that means that every remaining point is collinear.
So at this point, we can just undo some of the latest triangles
that we built until this is saturated case and we go straight to phase two.
So with this improvement, which is also simpler than the others I mentioned to implement,
it's a little bit more clever.
You can do quadratic time over all and it's very fast
and the implementation is not that tricky.
So that's it for the solution.
Thank you for watching.