Grid L — Deon Nicholas

Problem

You are given $p$ unit-length segments and $q$ L-shaped pieces, where an L-shaped piece is two unit-length segments joined at a $90°$ angle. You want to use ALL of the pieces — all $p$ segments and all $q$ L's, rotating them however you need — to form the grid lines of an $n \times m$ grid. The segments make up the edges of the grid, and the grid ends up with $n \times m$ cells inside. For example, four unit segments can make a square, which is a $1 \times 1$ grid:

+-+
| |      four unit segments -> a 1 x 1 grid
+-+

Given $p$ and $q$ , output any valid $n$ and $m$ , or $-1$ if it's not possible. ( $1 \leq p, q \leq 10^8$ , up to $100$ test cases.)

Initial Observations

Construction — this is a constructive algorithm, so I have to come up with an idea.
Look at the diagonals — a staircase of L's from the top-left to the bottom-right?
There's probably a unique recursion.
Come up with a conjecture.
[Examine Examples] — including varied examples and extremes. [Work Backward]. [Write It Out].
Eventually: matching, flows, edge cover.

IdeaWorking backward: how many edges does a grid even have?

To get started I tried some small examples — small values of $p$ and $q$ , and small grids — to get a feel for what the pieces can make.

Key Observation

If we have to use all the pieces, the total number of unit edges is fixed: each L contributes two edges and each segment contributes one, so the grid must have exactly

e = p + 2q

edges.

Work Backward

Instead of building up from the pieces, suppose we already had a finished grid. What would $p$ and $q$ have to be? For the sake of argument, let's say the grid has $r$ rows and $c$ columns of cells (rather than $n \times m$ , just for my simplicity), and count its edges — say on a $2 \times 3$ :

+-+-+-+
| | | |      r = 2, c = 3
+-+-+-+      horizontal unit edges: 3 lines of length 3 -> c(r+1) = 9
| | | |      vertical unit edges:   4 lines of length 2 -> r(c+1) = 8
+-+-+-+

Key Observation

After drawing a few of these, it's pretty quick to see that an $r \times c$ grid has $H = c(r+1)$ horizontal unit edges and $V = r(c+1)$ vertical unit edges, for a total of

H + V = 2rc + r + c .

So for a valid construction we at least need $2rc + r + c = e = p + 2q$ .

Write It Out

Expand and solve for $c$ : from $2rc + r + c = e$ we get

c = \frac{e - r}{2r + 1},

which must be a positive integer. So $2r+1$ has to be a factor of $e - r$ , and $c \geq 1$ gives the bound $r \leq (e-1)/3$ .

So one easy solution, maybe: try all possible $r$ , compute the associated $c$ , and check that it's an integer. The problem is these numbers are really, really big — $e$ can be up to $300$ million, and there are $100$ test cases, so trying all $r$ up to $e/3$ is way too slow. Okay. Now what?

IdeaPeeling off the L's looks like a matching

Before worrying about speed, I wrote up the Idea 1 loop — try all $r$ , take the first integer $c$ :

e = p + 2q
for r = 1 .. (e-1)/3:
    if (e - r) mod (2r + 1) == 0:
        c = (e - r) / (2r + 1)
        output r, c; done
output -1

— and ran it on the samples.

Generate and Test

I think it was the third-to-last sample, $p = 2$ , $q = 10$ , where my code came out with an incorrect answer. It picks $r = 1$ , $c = 7$ : the number of edges is correct ( $e = 22 = 2 \cdot 7 + 1 + 7$ ), but my answer differed from the Sample Output.

Key Question

Is $1 \times 7$ a correct alternative answer for $p = 2$ , $q = 10$ — or is it actually wrong? And if it's wrong, why?

So let's play with the $1 \times 7$ grid:

+-+-+-+-+-+-+-+
| | | | | | | |      r = 1, c = 7:   H = 14 horizontal edges
+-+-+-+-+-+-+-+                     V = 8 vertical edges

There are only $8$ vertical edges here. And if you look at how an L-piece has to sit, it occupies one horizontal and one vertical unit edge that physically touch at a point:

+-+
|        an L: one horizontal edge + one vertical edge, sharing an endpoint

So no matter how you arrange things, this grid can never host more than $8$ L's — and this test case has $q = 10$ . My answer really was wrong: the number of edges can be correct while the L's still don't fit.

Key Observation

Peeling the L-pieces off a finished grid is choosing a matching in a bipartite graph: the horizontal edges are one group of nodes, the vertical edges are the other group, and there's an edge between them if they physically touch at a point (so they could form an L together). Using $q$ L-pieces means finding a matching of size $q$ .

That's helpful, except for the fact that matching is an even harder problem than the original problem. But it does help us think about it: we're trying to match horizontal edges with vertical edges. So when is a big matching possible?

Ask for Help

This reminded me of Hall's matching theorem, which is a thing I learned in graph theory somewhere in school — I had to look it up. It says a perfect matching exists if and only if every subset of nodes on one side has a neighborhood at least as large as itself. The "only $8$ vertical edges" argument above is one subset of that: take ALL the horizontal edges — their neighborhood can't be bigger than the $8$ verticals that exist. Applying the theorem for real would mean checking every subset, so I didn't try to apply it exactly.

I also did a squarer example ( $8 \times 2$ ), started drawing L's on the corners, and got a lot more matched. So the shape matters: long and elongated is bad, square-ish is good — and at the very least, you're blocked by whichever orientation you have less of: every L uses one horizontal and one vertical edge, so no matching can be bigger than $\min(H, V)$ .

Key Question

For a fixed $r$ and $c$ , under what conditions can we place a matching of size $q$ in the grid? (In other words: what is the Hall-type matching condition for this particular graph?)

IdeaTry all r, with the matching conditionAC

So, the new algorithm: for each candidate $r$ and its $c$ , also compute $H = c(r+1)$ and $V = r(c+1)$ , and require

\min(H, V) \geq q .

Key Observation

This condition is definitely necessary, because of the matching bound: every L uses one horizontal and one vertical edge. Whether it's sufficient I did not prove in contest. But the regularity of these grids felt pretty good — there are always lots of horizontals next to verticals, and there's not really a way to create a pathological case as long as the grid is square enough. I tried for a few minutes to prove it, didn't, and just took it as a conjecture.

The next question I had for myself: how do I search all these $r$ and $c$ fast enough? There are still way too many candidate $r$ 's.

Key Observation

By symmetry we only need to try $r \leq c$ — transposing the grid swaps $r$ with $c$ (and $H$ with $V$ ), so if any grid works, one with $r \leq c$ works. And once $r \leq c$ ,

e = 2rc + r + c > 2r^2 ,

so $r < \sqrt{e/2}$ . That's about $12{,}000$ candidates even at $e = 3 \cdot 10^8$ — very fast over $100$ test cases.

Algorithm

e = p + 2q
for r = 1, 2, 3, ...:
    if e - r < 2r + 1: break              # c would be < 1
    if e - r < r * (2r + 1): break        # c would be < r  (only need r <= c)
    if (e - r) mod (2r + 1) != 0: continue
    c = (e - r) / (2r + 1)
    H = c * (r + 1);  V = r * (c + 1)
    if min(H, V) < q: continue
    output r, c; done
output -1

Once I felt confident in that, I submitted, and it was accepted. (Far too late — it took me way too long. But accepted.)

IdeaPost-contest: why is min(H, V) enough?

We're left with the final question: why is it that as long as both edge counts are at least $q$ , we can always use exactly $q$ L-pieces? That's what was left unproven in my analysis, and proving it is part of why I wanted to write this one up. So let's figure it out.

Lemma.

In an $r \times c$ grid, the maximum number of L's that can be placed simultaneously (the maximum matching between horizontal and vertical edges) is exactly

\min(H, V) = rc + \min(r, c) .

Proof.

The upper bound we already know: each L uses one edge of each orientation, so no matching can be bigger than $\min(H, V)$ .

For the construction, take $r \leq c$ without loss of generality, so the vertical edges are the rarer kind ( $V = rc + r \leq rc + c = H$ ), and let's match every vertical edge. Group the horizontal edges by column: column $j$ has $r + 1$ of them (one per horizontal line), and each one can form an L with a vertical edge on the line to its left (line $j$ ) or to its right (line $j+1$ ).

Now hand them out column by column. Vertical line $1$ can only be served by column $1$ : pair its $r$ verticals there, and column $1$ still has one horizontal left over — hand it to line $2$ . Column $2$ then owes line $2$ only $r - 1$ , and can hand two horizontals to line $3$ . The handoff grows by one each column — a little triangle — until some column is handing off all $r$ ; from then on, each column serves its right-hand line entirely and has one horizontal to spare. Let's watch it happen on $r = 2$ , $c = 4$ , peeling each matched L-piece out of the picture as we go. The full grid:

+-+-+-+-+
| | | | |
+-+-+-+-+
| | | | |
+-+-+-+-+

Column 1: pair line 1's two verticals with two of column 1's horizontals, and the leftover horizontal sticks out — it takes line 2's upper vertical with it:

+ +-+-+-+
    | | |      three L's peeled: line 1 is gone,
+ +-+-+-+      and so is one vertical of line 2
  | | | |
+ +-+-+-+

Line 2 still owes one vertical; column 2 pays it, and now TWO of its horizontals stick out — they take all of line 3:

+ + +-+-+
      | |      three more L's: line 2 finished,
+ + +-+-+      line 3 gone entirely
      | |
+ + +-+-+

And now the handoff has saturated at $r = 2$ : column 3 takes all of line 4, column 4 takes all of line 5, each with one horizontal to spare:

+ + + + +
 
+ + + + +      every vertical is matched; the two spare
               horizontals are all that's left
+ + +-+-+

No edge is used twice — once it's matched, it's out of the picture. Every vertical line gets its $r$ matches, and the spare horizontals number exactly $H - V = c - r$ (here: $2$ ). So all $V = rc + r$ verticals are matched, which meets the bound.

∎

So take any $r$ and $c$ that my loop outputs. The number of edges is correct, and $q \leq \min(H, V)$ , so by the lemma there's a way to place $q$ L-pieces on the grid. Place them, then fill in every remaining edge with a plain unit segment — and the counts guarantee that's exactly the $p$ segments we have. So the conjecture was true, and the solution is fully correct.

Review

To build an $r \times c$ grid out of exactly $p$ unit segments and $q$ L-pieces, let $H = c(r+1)$ and $V = r(c+1)$ be the grid's horizontal and vertical edge counts. You need the right number of edges, $H + V = p + 2q$ , and enough edges of each orientation, $\min(H, V) \geq q$ — and any $(r, c)$ satisfying both works. The path:

Count the edges. Using every piece means the grid has exactly $e = p + 2q$ unit edges. An $r \times c$ grid has $H = c(r+1)$ horizontal edges and $V = r(c+1)$ vertical edges, so we need $2rc + r + c = p + 2q$ . [1][2]
Solve for $c$ . For a candidate $r$ , we get that $c = (e - r)/(2r+1)$ , which must be a positive integer.
See the L's as a matching. An L occupies one horizontal and one vertical edge sharing an endpoint, so placing $q$ L's is a size- $q$ matching between the horizontal and vertical edges. [3]
The matching exists iff $\min(H, V) \geq q$ . Necessary because each L uses one edge of each orientation; sufficient because the column-by-column handout achieves a matching of size $\min(H, V)$ . [KQ] [4] [Lemma 1]
Only try $r \leq c$ . Transposing the grid swaps $r$ and $c$ , so if any grid works, one with $r \leq c$ works — and then $2r^2 \leq 2rc < 2rc + r + c = e$ , so $r < \sqrt{e/2}$ : about $12{,}000$ candidates at worst. Check each candidate for integrality and the min condition; print the first hit, or $-1$ . [5]

(My accepted submission.)

References

Problem-solving techniques used:

Examine Examples

Small examples, varied examples, and extremes all earned their keep here: the long thin grid ( $1 \times 7$ : $14$ horizontal edges, $8$ vertical) against the squarer ones is where the $\min(H, V)$ condition came from. And the most useful example of all was one I didn't pick myself — see Generate and Test below.

Work Backward

The input is $p, q$ and the answer is a grid. By flipping it — starting from a finished $r \times c$ grid and counting what $p$ and $q$ would have to be — we can derive every equation in this problem.

Problem Transformation

Seeing L-placement as a bipartite matching between horizontal and vertical edges. Somewhat of a red herring — matching in and of itself is a harder problem than this one — but it framed the right question, and the $\min(H, V)$ condition dropped out of it.

Ask for Help

Hall's matching theorem, from graph theory somewhere in school; I had to look it up. I never applied it exactly — I used it as intuition for why long thin grids fail.

Generate and Test

Writing out the code to try all $r$ and running it on the samples is what found the $r$ that didn't work ( $p = 2$ , $q = 10$ picking the $1 \times 7$ grid). When you're examining examples and gen-testing, looking for examples that truly falsify a claim — or truly verify it — is also how you find the pattern of when it works and when it doesn't.

Generate and Test

I never proved in contest that $\min(H, V) \geq q$ is enough. The grids felt regular enough that I took it as a conjecture, submitted, and proved it after.

Learning points:

In the end, the solution was really easy. It's a construction problem, which often can feel daunting, and it took me longer than it should have. Ironically I think I had the right path the whole way — I just came to it slowly.
The things I did well: looked at small examples and varied them, made the matching transformation, tried all $r$ , came up with the condition. The thing that would have sped me up: pursuing the extremes deliberately. "Not enough horizontal edges is obviously bad; not enough vertical edges is obviously bad" was available much earlier than I found it.
Test your claims against examples that can actually kill them. The naive loop looked fine until a sample falsified it, and that one failing case (long thin grid) is what surfaced the real condition. A claim that has only seen friendly examples isn't tested yet.
I did this problem at around 11 p.m. Not to make an excuse, but it's probably something to note: I should be taking contests in the morning, well-rested, maybe a shot of coffee right before. I suspect I would have gotten there faster. I don't know.

Topics:

Constructive problems
Bipartite matching / Hall's theorem
Counting / algebra
Enumeration with bounds