Hello, everyone.
My name is Salma.
I'm going to walk you through the Wonderland Chase problem statement.
I am a site reliability engineer in Google Cloud. On the side,
I like contributing to Code Jam problem development.
I reviewed the statement of this problem as a non-native English
speaker and I also developed its solution analysis.
Now, let's get started!
Our problem is about Alice in Wonderland being chased by the Queen of Hearts.
Our goal is to identify when Alice will get caught.
Or maybe she won't... Alice is trapped in Wonderland's labyrinth,
which looks something like this.
The labyrinth consists of a number of junctions.
The junctions are connected to one another by bidirectional corridors.
The starting position of both Alice and the Queen are known.
The Queen starts by picking her first move.
Her goal is to catch Alice in the smallest number of moves.
The Queen tells the Herald her move and the Herald announces it.
Alice gets to make her move before the Queen does.
She now knows the Queen's next move, so she can choose the optimal move
to escape it, or at least maximize the number of moves until she's caught.
After that the Queen moves to the announced junction.
They both keep taking turns to move,
they can choose either to stay at the same junction
or move through a corridor to another one,
until Alice gets caught, or the Queen gives up.
She will do so after one billion moves.
The goal is to know how many moves it takes
before the Queen catches Alice.
If they both select moves optimally.
Or maybe the Queen will give up and Alice will be safe.
I can't wait to see some of the creative approaches
our finalists take to tackle this problem.
Remember, there will be a live walkthrough of the solution on the livestream
after the round ends.
And don't forget to check out the analysis page for the problem after the round.
Goodbye!
My name is Melisa Halsband
I work as a software engineer in the Google office in Dublin, Ireland.
We're going to be going over the Wonderland Chase problem.
So let's get into it.
So this problem can be represented quite easily as a graph
where the junctions are representative nodes
and the corridors are represented at the edges.
The first thing to observe quite trivially is that the only way that the Queen has
any hope of catching Alice is that they are both in the same connected component.
If they are not, then Alice can just sit comfortably
and watch YouTube and then she will never be caught.
So for the rest of the problem, we're going to consider that...
We're going to assume the Queen and Alice are in the same connected component.
and we're only going to look at this component...
for the rest of the problem.
So, an important observation to make now is
that Alice will be always safe
if she can get into a cycle within the graph.
This is because even if the Queen is in the same cycle
and just next to her, Alice can always go the opposite way...
Sorry,
and sort of run in circles Tom and Jerry style.
And at the end of the chase, Alice will be tired,
but certainly safe.
So we're going to be using this later on.
How are we going to solve the problem now?
So, something we can do is we're going to partition this graph
into two subgraphs
A node is going to be considered to be in Alice's subgraph
if Alice can get there first, meaning that she has a shorter distance
from wherever she is.
And if a node is at the same distance from Alice and the Queen, or the Queen is closer,
then this node is to be considered in the Queen’s subgraph.
We can find this out by performing a better search
and just tagging the nodes with the distance from
each of these ladies.
Like this, and so on, and so forth.
We actually can use the same traversal to find the connected components if we’re interested in.
Okay.
Once we have done this, we can look at Alice's subgraph.
So obviously for each node
We compare the distances and whatever is smaller we assign,
and then we can look at Alice's subgraph on its own and we can ask,
‘Are there any cycles in it?’
We can check this by performing, now--
Depth-first search in Alice's subgraph, or just by counting the notes on edges.
If there are as many edges as there are nodes or more
it means that there is at least one cycle because this is a simple graph.
OK. If this is the case,
then again, Alice is safe because as we have seen,
if she can get into a cycle,
she can stay there and be safe.
So the second thing to observe is we need to check how many edges are there
that have one end on the Queen and one
end on Alice's subgraphs.
So something like this
So if there are at least two nodes
that have this, that connect to the two subgraphs,
what we can observe is that there will be then at least one cycle that contains
both the Queen’s and Alice's nodes, because Alice's subgraph is connected,
it connects the two ends, and the same happens for the Queen.
And therefore, we have now a cycle.
If this happens, Alice is again safe
because she can reach any of the points in her subgraph
Before the Queen can, so she can go to any part of her subgraph
and therefore she can get to any node.
in this loop, in the cycle that we found
Okay, so the last case to consider is
if there are no cycles in Alice's subtree
and if there are no more than one
edge that connect the two graphs.
In this case, actually the things
get a bit spicier for Alice because the Queen has this strategy
of getting into her end of this
bridge node that connects the two graphs.
And while Alice can get into any node into her graph
and her subgraph by definition because she has a shorter distance,
then she will not be able to get into any of the Queen’s
Because if that was the case, she would cross paths with the Queen.
And now Alice is effectively trapped in her own tree
because the Queen is sitting at the root of a graph that has no cycle.
So this is a tree.
At each step, the Queen will be closing in into Alice,
going to whatever branch
where Alice is.
And eventually Alice will be caught.
So what can Alice do in order to maximize the chase?
And in the hope that the Queen tires and gives up the chase,
she will have to go to the farthest away leaf in her subtree.
And which is this leaf?
We have calculated this already when we calculated the distance
from the Queen to each of the nodes in the graph.
So we know
which will be the farthest that the Queen would have to traverse
in order to corner Alice into a leaf.
So this is what Alice would have to do in order to to maximize the chase
And this number would have to be multiplied by two because
both Alice and the Queen take turns and
that's the result of the problem.
I hope you have enjoyed it as much as I did.