Codejam 2014 - Round 3 - Crime House

8 Dec 2015

A problem that must be solved with a greedy algorithm is usually a very difficult one.

For this problem, it turns out that we can devise a greedy algorithm to solve it. However, a greedy algorithm only solves a specific situation, where we know the number of criminals in the house at the beginning.

However, we can use a binary search to find the minimum number of criminals in the house at the beginning.

There are many axioms to prove:

Axiom: If the starting number of criminals is X yields a valid result, then Y > X always yields a valid result.

Because adding more people can't possibly make the situation invalid. It's just more people in the house at the end.

Axiom: If we have E0, then we will assign the criminal X who will exit the earliest (with no EX in between).

We can prove that by proving it is always worse to exit later. For example:

E0 … L1 … L2 — we can choose either L1 or L2. it doesn't matter E0 … E0 … L1 … L2 — we can choose either L1 or L2. It doesn't matter. Because we can always swap the 2 E0. E0 … L1 … E0 … L2 — we have to choose L1

The best thing to do is choosing L1.

Axiom: If we have E0, and every leave has an enter, then we assign a new person to E0.

We can prove that it doesn't matter…

E0 … E2 … L2 — we have to assign a new person E0 … L0 … E2 … L2 — we can either assign a new person or assign 2.

We do the same thing for L0. It might be a bit tricky.

And that's it.

Give it a kudos