Hi everyone! My name’s Amanda, and I’m a Software Engineer Intern working on Google Coding Competitions.
We hope you enjoyed all the problems from our 2021 contest.
Today, my friend and co-worker, Timothy
and I are going to talk you through the problem, Cutting Cake, from our final round.
Timothy, why don’t you go ahead and introduce yourself?
Thanks Amanda. Hi, my name is Timothy Buzzelli.
I am a software engineer on Google Coding Competitions.
We will walk you through what Cutting Cake is asking and how you might want to go about solving it.
Remember, you can always try any of our problems
on your own at any time in Practice Mode on g.co/CodeJam.
Now, let's get started!
Thanks, Timothy! Let’s take a look at the problem.
In this problem, you and your twin sibling are splitting a cake for your birthday.
The cake is covered with triangular icing patches of different flavors.
Although you are twins, you both have different tastes in icing. Each icing patch has two values A and B.
These represent the amount of enjoyment you and your twin get from eating this icing, respectively.
If you or your twin eat only part of an icing patch, you get enjoyment proportional to the area you ate.
You get to cut the cake into two pieces by making a single vertical cut. You will get the piece on the left and your twin will get the right piece.
You will each eat all of your respective halves. Let’s hope you don’t get a stomach ache!
Interesting. So the enjoyment you receive is equal to the sum of Ai’s for the icing patches on the left piece
and the enjoyment your twin receives is equal to the sum of Bi’s of the icing on the right piece.
Of course, accounting for when our line goes through icing patches.
Exactly! You want to cut the cake such that the absolute value of the difference between your enjoyment and your twin’s enjoyment is as small as possible.
Hmmm. This seems tricky! Let’s consider a case with just one triangular patch. Here we have a triangle with a vertical edge on the right.
If we cut all the way to the left of the patch, our twin will get all of the icing and will receive Bi enjoyment.
If we cut to the right of the patch, we will get all of the icing from this patch and will receive Ai enjoyment.
But, if our cut is somewhere in the middle of this triangle, we need to calculate what portion of the triangle is to the left of the cut
to see how much enjoyment we and our twin get from this icing patch.
Well, the formula for the area of a triangle is base x height / 2.
If we cut the cake so that the base of the portion to the left of the line
is ½ of the total width of the triangle,
we know that the height is ½ of the vertical segment of the triangle as well.
So, the area of the portion to the left of our cut is
(½ x ½ = ¼) of the full triangle’s area.
In general for a triangle with a vertical edge on the right
and a given vertical cut location, X, we can calculate the enjoyment as seen.
Here, left is the X coordinate of the left point of the triangle
and width is the width of this triangle.
I see! Also, because not all of our icing patches are triangles with a vertical side,
we can split them into two separate triangles so that this is true. The formula for the enjoyments from a triangle pointing the other direction
is a bit more complicated but is only slightly different to account for the triangle pointing the other way.
Absolutely! And if we look at these functions,
we can see that they only care about the X coordinates of the triangles and our cut location.
So, the Y-coordinates of the triangles don’t matter.
Plus, we can see that as long as our cut point is within a patch,
the function of our enjoyment from each icing patch
is a quadratic or a polynomial of degree 2.
So, if we consider cutting the cake somewhere between two adjacent X coordinates
we know that for every possible cut location in that window,
every patch is either entirely to the left, entirely to the right, or always inside our range.
Ohhh. So, the overall function for the enjoyment values
is a piece-wise polynomial. Between every pair of adjacent X-coordinates from all of the patches,
we get all of the enjoyment from the patches to the left
and can simply add up all the polynomials for the patches inside of this range.
If we do similar math for our twin, we can also get a piece-wise polynomial representing their enjoyment.
We can get the difference between our and our twin’s enjoyment by just subtracting their enjoyment polynomial from ours.
So, we can use a sweep-line technique and consider moving the vertical cut line from the left to the right.
As we pass the start and end points of icing patches, we can update our polynomial.
Then, for every pair of adjacent X-coordinates, we can solve for the minimum
absolute value in that range by just doing a little bit of math.
Our final answer is then the minimum we found during our sweep!
Wow! Who knew that cutting cake could be so tricky?
Be sure you check out the full analysis on g.co/CodeJam.
Also, don't forget to check out the other great problem walkthrough videos from the Code Jam 2021 Virtual World Finals.
And if you’re interested in getting started with Coding Competitions,
Check out Google’s Kickstart competitions, a great place to hone your coding skills.
Thanks for watching! Bye! Bye!