It was one of the expected solutions.

We can also solve it in $$$O(nk^3)$$$ by finding the augmenting paths in the graph in a clever way. The core idea is that you first find the flow from the left to the graph in which each augmenting path goes as far as possible, and then cut off the layers of the graph from the left and update the flow. More details in the editorial. It isn't much faster in practice, though.

How could you guess Digimons over Pokemons anyway!

I did everything (including spoons and stack) by myself. Just some time in image editors :P

And yes, I'm very proud because of the shadows in G (also by hand) XD

I hope so. mnbvmar, Radewoosh, I can assist with uploading if help needed.

I can share my solution

Let's denote bounding box as a rectangle with minimum possible area that covers all the points with edges parallel to axis. Now note that each side of a bounding box contains at least one point (otherwise we are able to shrink bounding box to a closest point in that direction). So each side of a bounding box touches at least one of our squares.

So we can only arrange our squares only in such way that each of 4 bounding box edges is touched. What are the different patterns of square intersections and how do the fill into our bounding box?

Other cases are just rotations and reflections of these four. Firstly, second case is completely useless. Secondly, we can see that in third case we can move blue square right just expanding covered area and turning it into a case one.

Now we only need to care about case 1 and case 4.

In case 1 we can always find a horizontal or vertical line that splits two squares. Let's make a scanline over this line: iterate over all meaningful positions of a splitting line and cover all points to the one side with first square and all points to the other side with second square. Square that covers a set of points can be calculated easily by finding min/max x/y. So we can do two scanlines here by sorting points by x coordinate and by y coordinate and revising all case 1 constructions.

In case 4 we can only fit this contruction into bounding box by attaching left-top corner of the red square to left-top corner of bounding box and bottom-right corner of the blue square to bottom-right corner of bounding box. Or a reflection of this case. Two points of our squares are fixed now, let's see how we can iterate over all possible combinations here. For a fixed size of one square we can easily determine set of points that are covered by one square, so we can uniquely determine set of points and size of a second square. So, let's iterate over all meaningful sizes of the red square with another scanline. Suppose, we want to keep increasing size of a red square and determine the order of points in which they will be included into this square. This is a "square distance" also known as Chebyshev distance between a top-left corner of bounding box and a point. So, we need to sort points according to it and make a similar scanline over this order of points — cover some prefix with first square and suffix with second square.

Note that if we make top-left square scanline we are making bottom-right square scanline because of symmetry. So we only need two of scanline of these type: for top-left corner and for bottom-left corner.

So, in general we need to make 4 similar scanlines that only differ in points order:

1. by x coordinate
2. by y coordinate
3. by Chebyshev distance from top-left corner of bounding box
4. by Chebyshev distance from bottom-left corner of bounding box

For each scanline we iterate over all positions and for each position $$$i$$$ we cover first $$$i$$$ points with one square and all other points with other square. One of these coverings is guaranteed to give a best answer.

I'm pretty sure this is correct, but I have not submited it because our div2 contest is finished and I cannot find any upsolving available. Does anyone know where we can upsolve it?

Just use this simple augmenting paths solution in O(nk^3), do not care about this matroid bullshit :P. However if you really want to understand that exponential solution then you can do this proof in a more direct fashion with some max-flow min-cut type argument without using any matroids, but don't ask me more.