Hi everyone, my name is Sadia and I'm a Site Reliability Engineer at Google.
My job is to make sure Google runs reliably.
I work on Codejam and I help out with Coding Competitions as my side project.
We hope you enjoyed all of the problems from our 2021 contest.
Today, I and my friend and co-worker, Satish, are going to talk you through problem Slides Circuit from our Final Round.
Over to you, Satish.
Thanks Sadia. Hi all, my name is Satish and I’m an Engineering Manager at Google.
I work on software to improve candidates' experience when applying to Google and make assessing candidates easier and equitable.
I also manage the engineering team working on Code Jam.
As Sadia mentioned, we'll be talking through the Slide Circuits problem 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.co/CodeJam.
Now, let's get started!
The problem involves a huge company called Gooli, that has B buildings in its campus.
Gooli built S unidirectional slides numbered from 1 to 8 between the buildings to facilitate transportation of employees.
That sounds like a fun way to move between buildings.
Yeah, but all these slides make transportation more complicated.
Now Melek, Gooli's Head of Transportation, wants to disable some slides, such that only circuits remain.
Now what is a circuit? A circuit is a set of two or more buildings b1,b2,...,bk
such that there is exactly one slide enabled from building bi to the next building bi+1,
and exactly one slide enabled from building bk to building b1.
No other slides from or to any of those buildings should be enabled, to prevent misdirections.
A state of the slides is then called fun if each building belongs to exactly one circuit.
There is a control console that can enable or disable a set of slides at once.
A single operation on the console takes 3 arguments,
the first slide L and the last slide R and an integer M.
Then it will act on all slides that are multiple of M between L and R.
Also that action is valid only if all the slides to be acted on have the same state.
For example if the action is to enable a set of slides, all of these slides must be disabled already.
In a campus of 5 buildings and 8 slides, initially all slides are disabled.
An enable operation with L=1, R=6 and M=2 will enable slides 2, 4 and 6
After that, a Disable operation with L=5, R=8, M=3 will disable slide 6.
Now there's a cat in the picture!
Melek's cat jumped over the console and started making random operations.
It is guaranteed that the operations are in the order that they are always possible.
But not all is bad though.
After each console operation performed by the cat, Melek can trigger a manual override that would enable exactly one disabled slide.
Melek will use this manual override to make sure that the slides are fun, if that is possible.
When the cat performs another console operation, if a manual override occurred, it is undone before the console operation happens.
Now that is interesting.
Since Melek wants to make the slides fun, our goal is to determine, after each of the cat's operations, if Melek can make the slides fun.
One important observation is that slides are fun, only when there are exactly B slides enabled,
and each building has exactly one slide going to it, and coming out of it.
So after each operation, we need to check if there's only one slide missing from the fun state,
and that slide exists in the original campus. We need to figure out how to do that.
We can consider this as a graph, with buildings as nodes and slides as edges.
For each operation, can we just enable/disable the edges involved, and then count degrees of the buildings?
That is exactly what we can do.
We can maintain the indegree and outdegree count of each of the nodes, and with each operation update them.
But that would mean for each operation, it would take O(S) time to process.
That works for the small test case, but not for the large.
We need a faster way to enable/disable edges, and find the answer. How can we optimize?
Let's first consider how we can do the updates.
One way can be to consider a hashing function.
There can be multiple choices, one of them can be using xor function.
For each node, we can assign two random integers to it,
one denoting it's indegree's presence, another outdegree's presence.
With hashing, we can maintain a set of edges, denoted by the hash value.
Every time we get an enabled operation, we can "insert" those edges into our set
by xor-ing the integers assigned to those nodes of those edges to the hash value.
For example, for inserting edge(u,v), we have to xor u's outdegree and v's indegree integers.
For disabling, we can take the negative of those numbers, and xor.
But won't it still take O(S) times to update for each operation, in the worst case?
We can pre-compute the prefix sum of xor, for the assigned integers on the edges.
We can also compute this separately for every possible multiple "m".
Then we can do the updates in constant time, for each operation.
Then how do we find if we can turn the slides to a fun state enabling exactly one slide?
Well, for a "fun" scenario, the set of edges we are maintaining should have all the random integers assigned to all the nodes exactly once.
We can calculate the xor value of all the numbers at the beginning.
Let's call it final_sum.
Then after every operation, we need to find if there exists an edge (u,v)
where if we xor the u's outdegree value and v's indegree value to the current hash value, it matches the final_sum.
This can be also done by another pre-computation.
Brilliant idea, Sadia. This indeed solves Melek's problem.
Hope you enjoyed the problem and make sure you check out the full analysis on g.co/CodeJam.
Also don't forget to check our other videos from our colleagues who've walked through the other problems from the Code Jam 2021 Virtual World Finals.
Thanks for watching! Bye!
Bye!