Hello there,
I'm Han-Sheng.
I'm a Software Engineer at Google, and I work on the Google Silicon
Simulation Tools team in Taiwan.
Today, I'm going to introduce the problem "Slide Parade", from the Code Jam
2022 World Finals.
I had experience as a contestant in Code Jam before I joined Google,
and now it feels really different as a contributor.
This year, I contributed
as the problem author of Slide Parade, and I also provided some ideas
on generating part of the extreme test cases.
Now, let's learn and talk through the problem statement.
In this problem, we continued the story of the company, Gooli,
which you may be familiar with from past Code Jam problems.
6 years ago, Gooli built some one-way slides to connect their buildings.
Each slide allows employees
to go from its "origin" building to its "destination" building.
In this example,
we have 3 buildings and 6 slides.
Each pair of buildings has two slides connecting them in both directions.
For example, starting from building 1,
you can go to building 2.
After being given the layout of the Gooli campus
we are asked to design a parade using the slides.
However, there are some constraints on the parade.
- The parade must begin and end at building 1.
- The parade must pass through all the buildings the same number of times,
Visiting building 1 at the beginning and the end of the parade are counted only once.
- The parade must use each slide at least once,
Currently, the parade is not valid.
It doesn't go back to building 1,
and the numbers of visits to the buildings are not equal.
Moreover, 5 of the slides remain unused in the parade.
To make it valid,
we could continue the parade and go through the buildings
counterclockwise and clockwise.
Now the parade begins and ends at building 1,
passes through all buildings twice
and uses all of the slides,
so it is a valid parade.
Now let's look at another layout.
In this example,
it's impossible to design a valid parade, because after leaving building 1,
say, to building 2,
it's impossible to go back to building 1, or go to building 3,
so the two slides on the right can never be used,
and the number of visits between building 2 and building 3
will never be equal.
That's all for the problem statement!
I'm excited to see the creative approaches to this problem from our finalists.
After the round ends,
you can try out this and our other Finals Problems
on the Code Jam website in practice mode.
Stay tuned because there's still more of our livestream to come. Bye!
Hi everyone.
I'm Timothy from the coding competition's team here at Google.
I'm going to explain a solution to Slide Parade.
So we've been tasked with finding a parade route
that goes through every single slide at least once,
but goes through every single building the same number of times.
One way we can approach this is by representing this as a graph.
So the nodes will be our buildings and the edges will be our slides.
If we split each node into two versions of the nodes,
we can have our edges, the slides, going from one side to the other.
Now we can find a matching in this graph.
This matching here
would represent the slides going from 1 to 2, 2 to 3 and 3 to 1.
So what this will be is a bunch of possibly disjoint cycles
where we've gone through every single node exactly one time,
but we might not have used every single slide.
For example, we didn't use the slide from 2 to 1.
So we can actually find another matching.
We can this time force the edge from 2 to 1
and then we just remove the edges
that we used from 3 to 1 and from 2 to 3 and find another matching.
And now this matching will be a bunch of potentially disjoint cycles
where we again have went through every single node exactly one time.
Now, we might not be able to find that matching
or we have to keep going for every single edge that we haven't used yet
and we might not be able to find one of them.
If we don't find one of them, that just means that the parade route doesn't exist
so we can just return impossible as our answer.
But if we do find them all, we now have a bunch of sets of cycles that cover a graph,
and every single one of these sets of cycles
goes through every single node exactly one time.
And together all of these sets use every single slide.
As long as our graph was connected and we found all of these matchings,
we can actually use that to build in our Eulerian circuit.
One thing we need to be careful with to make sure this runs fast enough
is when we find the secondary matchings, we can reuse some of the work
we already did from our earlier matching, so we only really have to match
one more additional node instead of rebuilding the entire matching.
But that's all for now.