Hi there.
I am Anusha.
I am a Software Engineer at Google and I work for the
Google Assistant Communications team
out of the Mountain View office in California in the US.
Hello, my name is Bartosz and I have been a software developer at Google
in beautiful Waterloo, Canada for almost two years.
I currently work with the Display Ads Experiments team and
the Google Kick Start team which is organizing another coding competition run by Google.
Bartosz and I are going to talk about the problem
“Schrödinger and Pavlov” for Code Jam 2022’s World Finals.
We both have experience as contestants in coding competitions
like Code Jam and Kick Start and we are very excited
to be on the other side setting up challenges for all of you.
It is 1935 and a meeting between two Nobel Prize winners
is producing extraordinary results.
Schrödinger, a famous physicist, invites Pavlov,
a famous physiologist, to see his experiments with cats in boxes.
Pavlov brought his dog with him to keep up
with his own research, and the combination proved interesting, to say the least.
Let’s start out with what the problem is asking for.
We are given N boxes in a row.
Schrödinger's cats may be present in some of them.
Each box is only big enough to hold a single cat.
The boxes are connected by a series of one-way tunnels.
Each box is the starting point of exactly one tunnel,
but can be the destination of zero, one or multiple tunnels.
The cats can move in one direction
from one box to another if a tunnel exists between them.
Note here that the cat can only move if the destination box is empty
as boxes are not big enough for more than one cat.
Cats are usually mellow and calm and prefer to rest inside their boxes if nothing alarms them.
Pavlov’s dog walks past the boxes from 1 to N
and barks at each box in turn.
If a cat is present in the box,
it tries to escape through the tunnel leaving that box.
Note that the cat cannot use the tunnel
if the destination is already occupied by some other cat.
Let us take a look at the example.
Here we have 4 boxes, and we have a cat in the first, second, and fourth box.
There are tunnels from the first box to the second one,
from the second box to the third one,
from the third box to the first one,
and from the fourth box to the third one.
Now, let's consider the dog running from left to right.
When the dog approaches the first box, it startles the cat inside
which tries to escape to the second box.
However, as the box is already occupied, it cannot go there.
Then the dog approaches the second box and startles the cat inside this box.
The cat escapes through the second tunnel
and ends up in the third box, which was free.
Now the dog approaches the third box
which is currently occupied by the cat that escaped from the second box.
The cat gets startled again
but is unable to escape, as the first box is already occupied.
Finally the dog reaches the last box.
The cat inside this box is startled as well
and tries to escape, but is not able to, as the third box is already occupied.
The objective of this problem is to predict if the last box contains a cat when the dog finishes
running past all the boxes and reaches the last one.
In this example, we can see that the last box will contain a cat in the end.
But that's not the whole problem.
In pure Schrödinger's cat tradition,
we are not certain whether some boxes contain a cat or not.
If we have k unknown boxes, then we have 2^k
hypothetical situations
and we want to consider for all of these situations,
if a cat would be left in the last box.
The output of the problem should be
the number of ways that would result in a cat being in the last box.
You need to write a program
that can give an answer to all situations up to 5000 boxes.
It is common for Code Jam problems to deal
with large numbers up to thousands or millions of digits long;
that is easier in some programming languages than others,
so to keep things fair, we often only require giving the value modulo
a large prime such as billion plus seven (10^9+7).
There is also an easier version of this problem that you can solve.
In this version, we have at most 100 boxes
and all the tunnels connect to nearby boxes.
The farthest connected one can be 5 boxes away.
We are going to stop here to avoid any spoilers.
We can't wait to see some creative approaches our finalists take
to tackle this problem.
Stay tuned after the contest ends,
to see a full walkthrough of the solution,
and make sure to check out the analysis page for the solution after the round ends.
Goodbye!
Hello, everyone.
This is Mohamed Yosri.
I'm a software engineer in Safe Search Team and Search Ranking.
I'm also part of Code Jam Coding Competition Team
Right now, we will walk through Schrödinger and Pavlov solution.
So if you are.
As a quick recap, for Schrödinger and Pavlov
We have a row of N boxes These boxes contains a cat
The boxes, some boxes contain a cat.
Some boxes don't contain any cat.
And some boxes may or may not contain a cat.
So if boxes with 1 contain a cat, boxes with 0 does not contain a cat.
Boxes with question mark may or may not contain a cat.
And our objective here is to compute
how many configurations lead to a cat in the last box after the whole process
The process goes from left to right, from box number 1 to box number N.
And at each step,
if the box contain a cat
right now, it can move through a tunnel to the next box
Only if the next box is empty.
And of course, we see that depending on uncertain boxes, the boxes that may or may not contain a cat,
It can change the number of final configurations, our solution.
So, for example, if we have the number of empty boxes, there’s uncertain boxes is K
So we have final configurations with a total of 2^K
So for test set one,
we have two special limits
So the first limit is the number of boxes is up to 100.
And also the tunnels has a limit.
So a box, let's say we have box number i, it can only go,
the tunnel can go only goes to any box within a distance of 5.
So i + 5, or
i - 5, any box in this distance.
It can’t go to any box further than this distance
With all of this in mind.
For Test Set 1
We can have a dynamic programing solution.
This solution has this state.
So the current box we are at right now and
the state of the previous five boxes
and also the state of the current boxes
the current box
and the state of the next five boxes
And why is that?
Because we only move at most five steps ahead
or five steps previous
and what we try to compute is
What is the number of configurations
that will end up if we are at this box right now.
And the previous five boxes were at this state, and the current state
is this state, and the next five boxes are currently at this state.
And of course,
the current, this dimension is up to 100
And the second dimension is up to 2^5
and the third dimension is only two states.
The last dimension is also 2^5
So that state is a total of
100 x 2^11
or N x 2^11
So we go simulate the process from box number 1
to box number N
If the box contains a cat, we try to move it.
If the next box is empty.
And of course if the next box is a maybe so it can contain a cat or maybe it’s empty
We branch the condition
We try if it's contain a cat and if we try if it doesn't contain a cat
and also if the current box is a maybe box, then we also branch.
So we try twice.
We try if it's if it does contain a cat and if it doesn't contain a cat
And doing so, at the end
we will count the number of configurations
that end up with a cat at the very last box.
This is fast enough to pass test set 1/
With further analysis
We can get rid of the exponential factor.
For the full details, you can check out the full analysis
on g.co/codejam
That's it for now. Thank you.