[THEME MUSIC]
[MOUSE CLICK]
MAIRIN CHESNEY: Hi, everyone.
My name is Mairin, and I'm a software engineer
on Google Maps.
Thanks for joining us for our Kick Start problem
walk-through.
Not familiar with Kick Start?
Head to our website after the video
to learn more about our online coding competition.
I'm here today with my colleague Karim.
KARIM FATEHI: Thanks, Mairin.
Hi there.
My name is Karim, and I am a software engineer
on Google photos.
Incidentally, Maps and Photos are my favorite Google
products.
And I'm really excited to be here today
to talk to you about Kick Start.
MAIRIN CHESNEY: Great to have you here, Karim.
Today we're going to walk through our platform
and how to solve an algorithmic problem during a Kick Start
round.
Whether you've tuned in today to prep for an upcoming Kick Start
round, learn more about competitive programming,
get ready for an interview, or simply have fun,
there is something here for everyone.
Let's get started.
How do you sign up for Kick Start?
The first step is to create a coding competitions
profile with a Gmail account.
Once you've created your profile, you aren't done yet.
Make sure you then register for Kick Start.
You will need to do this in order
to participate in any online or onsite round.
Pause the video here if you need to create your profile,
and register at g.co/kickstart.
And hit play once you're ready to go.
Now that you're registered and logged in,
you're all set to participate in any upcoming Kick Start
challenge.
But what does competing in a round actually entail?
To participate, you'll click on the Compete Now button
on the homepage to take you to the problem set.
This is the Problem Overview page,
where you can access the problems in the round,
take a look at your rank on the scoreboard,
ask clarifying questions to Google moderators,
check the time remaining, and refer to round statistics.
In a normal Kick Start round, you
will usually see four problems that you can attempt to solve.
Each problem varies in difficulty level.
These colored bars under each problem name
provides you with statistics about how many users
have attempted the problem and how many have been successful.
In order to read each problem statement and submit solutions,
you'll need to click on the Open Problem button.
This blank space above the scoreboard is where you'll be
able to view your points and penalties--
which means a wrong attempt--
from your submission.
It's blank right now, since we haven't submitted anything yet.
Below that is the scoreboard that will
be up during and post-round.
Here you'll be able to find where you ranked
compared to other participants.
Throughout this video, we will refer
to our FAQ, which is our Frequently Asked Question page,
linked in the top menu bar.
The FAQ is filled with information
about how to prepare and compete in Kick Start.
During a round, we encourage you to have
the FAQ open in a separate tab to quickly refer back and forth
if you have a question.
KARIM FATEHI: Now that we understand key dashboard
features, let's see how to attempt
a problem on the platform.
We are going to solve Yogurt, a past Kick Start
problem from 2018.
To the left is the problem statement,
which explains the task you're asked to solve.
It is very important you read the entire problem
statement carefully.
Let's look at the problem statement for Yogurt.
Yogurt can be a nutritious part of an appetizer, main course,
or dessert, but it must be consumed before it expires,
and it might expire quickly.
Moreover, different cups of yogurt
might expire on different days.
Lucy loves yogurt, and she has bought n cups of yogurt.
But she is worried that she might not
be able to consume all of them before they expire.
The i-th cup of yogurt will expire a of i days from today.
And a cup of yogurt cannot be consumed on the day it expires
or any day after that.
As much as Lucy loves yogurt, she
can still only consume, at most, k cups of yogurt each day.
What is the largest number of cups of yogurt that she can
consume starting from today?
Then there is the Input and Output section,
which explains the format of how your solution should
read and write.
Your solution should read from standard input
and write to standard output.
For yogurt, the first line of the input
gives the number of test cases, t.
t test cases follow.
Each test case starts with one line containing two integers, n
and k, as described previously.
Then there is one more line with n integers a of i.
Further, there is the Limits section,
which specifies the general constraints of the input
variables and any other special constraints.
Usually limits for test set 1 are set in such a way
that an inefficient or easier solution can pass the test
set, whereas test set 2 might need more efficient algorithms
or data structures.
In either case, the test sets we used
to validate your code are much larger,
and may contain corner cases that you
don't see in the samples.
On the right-hand side, we have the built-in editor,
where you can write your code in a variety of languages,
and also tested on our servers by toggling the Show Test input
button on the bottom right.
An easy way to get a test case is
to copy one of the example inputs and paste them in.
Or you can write your own test samples for edge cases.
You can write code and run tests until you
feel confident that you have the right solution.
You will likely make some mistakes.
But that is what the editor is for.
Just keep at it.
In Kick Start, we run the test cases right away,
so you get to see the results immediately
on the product screen.
If you get it wrong, don't worry.
You can edit your code and try again, up until the round ends.
We support a variety of languages, like Python, Java,
C++, et cetera.
But I recommend mastering one language,
as it will help you code faster and avoid obvious bugs.
Check out our FAQ page for all supported languages, libraries,
and code snippets for all Kick Start problems.
When you are ready, hit Submit Attempt.
Let's get back to Yogurt.
Mairin, do you have any thoughts on how to solve it?
MAIRIN CHESNEY: Thanks, Karim.
The first approach I see is looking
through the list of yogurt expiration dates
and finding the k yogurts closest to expiring,
and then have Lucy consume them by removing them from the list.
Programmatically, I can do that by finding the smallest
expiration date in the list, and remove it
from the list a total of k times.
To move to the next day, I just need
to subtract 1 from the expiration
date of all remaining yogurts.
Then I'll continue this process until I run out
of yogurts or all the remaining yogurts are expired.
If you're familiar with big O notation,
you might realize that's an o of n-squared approach.
That's a good start, but it's too slow for the larger test
case.
As I look at the problem more, I think
I could improve the efficiency of the approach
by first sorting the yogurts by days until they expire.
That way I can start at the beginning
of the list of yogurts and walk through it one time,
consuming along the way.
I'm most comfortable with Python.
So that's the language I'm going to use.
I'm going to make a helper class with a few methods
to help me simulate consuming yogurt.
Notice that I make use of Python's sorted method,
as well as list comprehensions.
Feel free to use whatever constructs you
can in the language you choose.
Oh no, I'm seeing a runtime error
when I try to submit my code.
If I head over to the FAQ, I can see what that means.
Ah, there's the issue.
I forgot to use the self keyword in my consume method.
Fixed.
Shoot, now I've got a wrong answer.
Hmm, ah, there it is.
I forgot to reset my consumed_today variable to 0.
And submit it.
[APPLAUSE]
To view your score for the round,
check back on the dashboard.
Don't worry if you click out of the problem.
All of your work will be saved.
A score for around consists of a point total and penalty time.
As soon as you get the correct answer for a test set,
you get those points.
The number of points a test set is worth
is always shown on the scoreboard
directly below the problem title on the dashboard.
If you have the same number of points as someone else,
Kick Start will use the penalty time as the tiebreaker.
Your penalty time is the number of minutes
from the start of the round until
your last correct submission, plus a few extra minutes
added for each incorrect attempt.
Take a look at the rules and FAQ for exactly
how the scoring works.
In short, it's most important that you
focus on getting as many points as possible.
But if you can do it quickly and without mistakes,
that's even better.
For the most part, Kick Start problems
focus on algorithms and data structures.
In the problem, Yogurt, I noticed
that I could use sorting to improve my algorithm.
Understanding and being able to use
common algorithms such as graphed reversals,
dynamic programming, binary search, as well as
data structures like stacks, queues, and binary trees,
will help you succeed in a Kick Start
or other competitive programming contest.
This code should be efficient enough
to run through both test sets, but we
want to show you an optimization that is even faster.
Karim, take it away.
KARIM FATEHI: Thanks, Mairin.
In the previous example, we went forward in time
and ate yogurts that were expiring the soonest.
Is there a different way we could visualize the problem?
Since daily capacity, k, is greater than or equal to 1,
we have yogurt for at most n days.
Let's think about what yogurts we could eat on the n-th day.
That would be yogurt that would expire at n or more days.
So we can replace any of a of i that is greater than n with n.
Remember, we can always eat yogurt
any time before it expires.
Then, on the n minus 1-th day, we
can eat any excess from day n, as well as yogurts
that expire on day n minus 1.
This way, we could work backwards,
moving any excess yogurts until day 1, when the remainder must
be discarded.
In Java, you should always name your class "solution,"
with the main method that reads from standard n
using the scanner, as shown here.
For each test case, we read in n and k.
Then we read in the expiration dates, a of i, for all cups,
and bucket the yogurts by their expiration dates.
We start from the n-th day, eat up to k yogurts,
and move the rest to the previous day.
We make one forward path through the data to bucket the yogurts,
and one reverse pass to count the consumption.
Be sure to hit the Submit Attempt button.
[APPLAUSE]
And that is how you would solve Yogurt in a Kick Start round
in linear time.
After you solve what you can and the round ends,
head to the dashboard to view the results.
You can check out the Round Overview by the toggle
here, and also learn about how to solve
each problem by viewing the problem analyses posted
after every round.
You can view your rank on the scoreboard.
Curious how your friends solved the problem?
You can also see other contestants' code
from completed rounds by clicking on their nickname
in the scoreboard to see all their in-contest attempts.
Remember, practice makes progress.
We recommend taking a look at past Kick Start rounds
on the Archive page, and trying your hand
at some of the problems in Practice mode
in a three-hour window, mirroring what
an official round will be like.
So that is the Kick Start platform.
If it feels like a lot of information,
don't worry about remembering everything.
Review the detailed FAQ page.
Also check out our YouTube playlist.
Both have a ton of information on how
to prepare for an upcoming round.
We also encourage you to join our Facebook group
to connect with the community, ask questions, and get
helpful tips from fellow coders.
MAIRIN CHESNEY: Hope to see you in our next online round.
Our schedule page can be found on our website and here.
And remember to keep practicing.
Thank you for joining us.
And we hope you learned a thing or two,
and this video will kickstart your competitive programming
journey.
[MUSIC PLAYING]
[MOUSE CLICK]