[Music]
hi everyone
my name is 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 bazzelli 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 dot co
code jam 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 taste 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 the enjoyment you get is
proportional to the area you ate
you get to cut the cake in 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 so let's hope you don't get a
stomachache
interesting so the enjoyment you receive
is equal to the sum of a i's for the
icing patches on the left piece
and the enjoyment your twin receives is
equal to the sum of bis for the icing
patch on the right piece
of course accounting for when our line
goes through the icing patches
exactly you want to cut the cake such
that the absolute value of the
difference between your enjoyment
and your twins enjoyment is as small as
possible
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 and we 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 times height divided by
two
if we cut the cake so that the base of
the portion to the left of the line
is one half of the total width of the
triangle
we know that the height is one half of
the vertical segment of the triangle as
well
so the area of the portion to the left
of our cut is one half times one-half
which equals one-fourth of the full
triangle's area
in general for a triangle with a
vertical edge on the right
and a given 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 triangle
don't matter
plus we can see that as long as our cup
point is within a patch
the function of our enjoyment from each
icing patch is a quadratic or a
polynomial of degree two
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 oh
so the overall function for the
enjoyment values
is a piecewise 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 this
range
if we do similar math for our twin we
can also get a piecewise polynomial
representing their enjoyment
we can then get the difference between
our and our twins 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 the
sweep wow
who knew that cutting cake could be so
tricky be sure you check out the full
analysis on g dot co
code jam 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