Hi, I’m Onufry, a Software Engineer
at Google, working on Google Cloud. Together with my co-worker Ulises,
we'll walk you through the problem
"Goose, Goose, Ducks".
Hi, everyone,
My name is Ulises.
I'm a Software Engineer working on YouTube;
I enjoy being part of coding competitions, in the past as a competitor
and now as a contributor.
That's cool!
I've also been involved in Code Jam for something like 13 years now
- first as a competitor, then as an organizer,
and now mostly as a problem author - in particular for this problem.
Awesome. So let's get started.
What is “Goose Goose Ducks” about?
In this problem, the Ducks have infiltrated the first international Geese conference.
So we have a group of participants -- the Geese -- wandering about;
and a number of pieces of evidence that we should use
to identify the conspirators -- the Ducks -- among them.
Cool. What type of evidence do we have?
We have two types of evidence.
First, we know the time and the place of every conspirator meeting,
and we know that all the conspirators were present at every single meeting.
Ok. All the bad Ducks meet here at time five. That's simple.
Second, we have pieces of evidence provided by participants.
A participant of a conference can tell us that together with another participant,
they were present a specific time and place.
Are all these pieces of evidence true?
How did Goose 1 get from one corner to another so quickly?
I thought each bird covers only one meter of distance in one second.
Well, the good Geese never lie,
but the evil Ducks can.
However, we know that a duck will never contradict
an earlier piece of testimony given by a Goose.
So, in this case, someone lied about where Goose 1 was.
Can we figure out who it was?
Well, if Goose 2 is really a
good goose, then Goose 3 lied and contradicted it
- but you just said that can’t happen!
So, we know Goose 2 is actually an evil duck!
Yes, exactly.
Note that Goose 3 might also be a Duck,
and we have no idea where Goose 1 was at any specific place in time.
But we do know that Goose 2 is secretly a Duck in disguise.
And so Goose 2 needed to get to the meeting place for time 6
- so Goose 2 couldn’t have been where Goose 1 claims it
saw it at time 5, right?
So Goose 1 is also a duck!
Right!
But what about Goose 3? We don’t know,
it could’ve told the truth
about Goose 1, Goose 3 could be a good Goose or an evil Duck.
What should I do?
Well, the problem asks you to return the smallest possible non-empty set of Ducks.
So in this case, that's two.
Awesome! I look forward to seeing how the finalists solve the problem.
Me too!
Remember to try out this and all the other Finals problems
on the Google Code Jam site
Thank you for watching!
Hey. I'm Samiksha Gupta from Kick Start Team
and I will walk you through the problem. ‘Goose, Goose, Ducks?’
The key in this problem is to carefully
look out for all the rules of consistency and then derive implications from it.
We have two main information which is given to us in the problem statement.
First is set of meeting points for all the ducks
that representing the conference room.
And second,
and also note that all the ducks attended every meeting in this list.
Second, we have a list of statements that were given by birth about both
maybe a goose or maybe a duck?
Of where they were and with whom they were
and all this is in space time point.
So now, let’s take one bird in the conference room.
Let's say, name it as A. now we construct a path for A
And how do we construct it? It’s like we check out
all these statements that involves A
and also we take into consideration all the meeting points.
Now, let's see here we have P1, P2, and P3.
Now we want to check if it was possible for A to go from P1 to P2
because remember that we also have a max speed limit in the problem statement.
Now, an another observation is
that we would only look at the consecutive points for A
And that we can do it in the logarithmic complexity for this particular part of the problem.
Now, let's see now
once we can compute the speed and, let's say, it's not under the limit,
then we have three cases
Yeah.
The first cases then
would be P1 and P2 - the consecutive ones.
They both came from meeting points.
That's not possible, given the constraints in the problem statement.
Second, we have-- we can have one
is coming from a meeting and the another is coming from a statement.
I will explain about it later.
But let's also take out what's the third case.
The third cases when both of them are statements.
Now, if we go back and remember the problem statement, we have certain rules.
One is a goose will never lie, and a duck will always try to be consistent
with what the goose has said before it's recording
Before it has recorded a statement.
So here, based on that, if we have the second case,
then this implies that if A is a duck, then B is also a duck.
And in the second case -- Sorry, and in the third case,
It's the case that we know for sure that it's a fourth duck.
One thing to check out here is like how we will decide
which one is the fourth duck.
So we will look at who claimed Pi or Pi+1
For that, we will check the ordering of the statements of when it was recorded.
Note that this is different from what we were following along
we were following the ordering of time of traveling in the conference room.
So let's say if Pi was recorded first
then the claiming of Pi is a forced duck.
Now, once we get the forced duck, we would have to remove it.
And again, we have to check the new adjacent
So in case of forced ducks, we don't
We already have,
since the problem is to find out the minimum cysec - our work is done.
We would output the number of forced ducks we were able to find.
Otherwise what we would do, we will model our knowledge
into a graph whose vertices are birds,
and the edges are implications and what are these implications
like if I say if there an edge between A and B, then if A is a duck
then B is also a duck.
So we will have these edges and then the problem reduces into finding
the smallest, strongest connected component in this graph.
And note that this
strongest component - a connected component - should be our final one
Yep. And for more details
You can go to the analysis of this problem.
We can do for that. And thank you.