Visual explanation of a Google Codejam 2017 question

This is the last question from the Google Codejam 2017 qualification round.


How can we place models

Models. +: 1 point, x: 1 point, o: 2 points

on the square stage

The stage is a grid

to get as many points as possible? The rules are


Some models are already placed.

Pre-placed models

We can only change a + or X to an O or place new models on the stage.


From the rules, all rows look like this

One row

where at most one model is not a +. Let's just record where the non-+s are

A non-+

The rule is now: at most one non-+ per row and column.

So we can convert a grid (stage) into one grid of non-+ and one grid of non-x.


using these rules

Translation table

and the points match up if each non-+ and non-x is worth 1 style point.

New style points

The already placed models translate to already placed non-+ and non-x.

This lets us place non-+s and non-xs separately.


non-+ is the easier of the two. A preplaced non-+ means we can't put more non-+ in that row or column

Removed squares from pre-placed non-+

so we might as well remove them and get a smaller square. How can we place as many non-+ as possible?

Best placement of non-+

Along the diagonal is one way. This places as many non-+ as we have rows (or columns) so we can't do better.


non-x placement is

Non-x transformation

non-+ placement rotated by 45 degrees. But now the stage isn't a square anymore. How can be place a maximum number of non-+ here?

This looks like some kind of set packing where the squares are the elements and the rows and columns are the subsets. Since each square appears in exactly two subsets,

Grid to bipartite graph

set packing here is actually maximum bipartite matching and we can use any of the existing algorithm for that.

Maximum matching in the bipartite graph

Blog index