Largest square from 1x1 and 2x2 tiles

A square of side s can be built when its area s² splits into some number b of 2×2 tiles and a of 1×1 tiles with 4b + a = s², b ≤ N, a ≤ M. We do not have to use every tile.

Area alone is not enough. A 2×2 tile cannot stick out of the square, so geometry caps how many big tiles fit:

• At most ⌊s/2⌋² big tiles fit in an s × s square. Tile the top-left 2⌊s/2⌋ × 2⌊s/2⌋ block on the even grid; that is the most possible, because every big tile covers exactly one cell whose row and column are both even (1-indexed: 2, 4, …), and there are only ⌊s/2⌋² such cells.
• Any b up to that cap can be placed (use a subset of those grid positions). The rest of the area is filled with 1×1 tiles.

So with b = min(N, ⌊s/2⌋²) big tiles (using more big tiles always saves small ones), the square is buildable exactly when

need(s) = s² − 4·min(N, ⌊s/2⌋²)  ≤  M

Brute force. Try every s from ⌊√(M + 4N)⌋ down to 1 and return the first feasible one. That is O(√(M + 4N)), about 7·10⁴ steps for the maximum input. Fine in practice, and a good first answer.

Trap: feasibility is not monotone in s. With M = 0, N = 1, side 2 works but side 1 does not (it needs one small tile). With M = 4, N = 1, side 2 works but side 3 needs 5 small tiles. So a single binary search over s is wrong.

Fix: split by parity. Write s = 2k or s = 2k + 1.

• Even, s = 2k: need = 4k² − 4·min(N, k²) = 4·max(0, k² − N). Non-decreasing in k.
• Odd, s = 2k + 1: need = (2k+1)² − 4·min(N, k²). When k² ≤ N it is 4k + 1; otherwise it is (2k+1)² − 4N. Both strictly increase in k.

Within each parity, feasibility is monotone (true, then false forever). Binary search the largest feasible k for each parity and return the bigger side. Return 0 when neither parity has a feasible k ≥ 1 (s = 0 is "no square").

Invariants used in the search: lo is always feasible (or the sentinel "none"), hi + 1 is always infeasible. The upper bound k ≤ √(M + 4N) holds because area can never exceed M + 4N.

Python integers do not overflow, but in Java/C++ use 64-bit: s² reaches about 5·10⁹.

from math import isqrt


def small_tiles_needed(side: int, big: int) -> int:
    """1x1 tiles needed to fill a side x side square when up to `big`
    2x2 tiles are available. Uses as many 2x2 tiles as geometry allows."""
    half = side // 2
    used_big = min(big, half * half)
    return side * side - 4 * used_big


def largest_feasible_k(m: int, n: int, parity: int, k_max: int) -> int:
    """Largest k >= 0 such that side = 2k + parity is buildable, or -1.
    Feasibility is monotone in k for a fixed parity."""
    def ok(k: int) -> bool:
        side = 2 * k + parity
        return side > 0 and small_tiles_needed(side, n) <= m

    lo, hi = -1, k_max  # ok(lo) treated as true; answer in [lo, hi]
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if ok(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo


def max_square_side(m: int, n: int) -> int:
    """Side length of the largest square fully tiled by at most m 1x1 tiles
    and at most n 2x2 tiles, or 0 if no square can be formed."""
    if m < 0 or n < 0:
        raise ValueError("tile counts must be non-negative")
    max_side = isqrt(m + 4 * n)          # area bound
    k_max = max_side // 2 + 1
    best = 0
    for parity in (0, 1):
        k = largest_feasible_k(m, n, parity, k_max)
        if k >= 0:
            side = 2 * k + parity
            if side > 0:
                best = max(best, side)
    return best


def brute_force(m: int, n: int) -> int:
    for side in range(isqrt(m + 4 * n), 0, -1):
        if small_tiles_needed(side, n) <= m:
            return side
    return 0


if __name__ == "__main__":
    assert max_square_side(0, 0) == 0
    assert max_square_side(1, 0) == 1
    assert max_square_side(0, 1) == 2
    assert max_square_side(4, 1) == 2
    assert max_square_side(5, 1) == 3
    assert max_square_side(0, 3) == 2
    assert max_square_side(0, 4) == 4
    assert max_square_side(8, 0) == 2
    assert max_square_side(9, 0) == 3
    assert max_square_side(0, 10**9) == 63244
    assert max_square_side(10**9, 10**9) == 70710
    for m in range(60):
        for n in range(30):
            assert max_square_side(m, n) == brute_force(m, n), (m, n)
    print("ok")

• Time: O(log(M + N)), two binary searches over k ≤ √(M + 4N)/2 + 1, each check O(1).
• Space: O(1).
• The brute force scan is O(√(M + 4N)) time, O(1) space.

• M = 0, N = 0 → 0 (no tiles).
• M = 1, N = 0 → 1.
• M = 0, N = 1 → 2 (side 1 is impossible, side 2 works: non-monotone case).
• M = 4, N = 1 → 2 (side 3 would need 5 small tiles).
• M = 5, N = 1 → 3 (one 2×2 in a corner, five 1×1 around it).
• M = 0, N = 3 → 2 (three big tiles cannot make a 4×4).
• M = 0, N = 4 → 4.
• M = 8, N = 0 → 2; M = 9, N = 0 → 3.
• M = 0, N = 10⁹ → 63244 (largest even 2k with k² ≤ 10⁹).
• M = 10⁹, N = 10⁹ → 70710 (70710² = 4 999 904 100 ≤ 5·10⁹, and the area bound is ⌊√(5·10⁹)⌋ = 70710).
• Randomized check against brute_force for all M < 60, N < 30.

1. Return the counts used. Return (side, big_used, small_used) with big_used = min(N, ⌊s/2⌋²) and small_used = s² − 4·big_used. Same search.
2. Must use all tiles. Then M + 4N must be a perfect square s², and N ≤ ⌊s/2⌋². One isqrt and one comparison, O(1).
3. Rectangle instead of square (largest area w × h, or fixed width w). The cap becomes ⌊w/2⌋·⌊h/2⌋; for fixed w the same parity-split binary search over h works. For max area over all shapes, iterate w and binary search h.
4. Add 3×3 tiles (or general k×k). Geometry is no longer a simple cap: mixing 2×2 and 3×3 tiles inside a square has packing constraints. Discuss a greedy (largest tiles on their own grid first, then fill), why it can fail, and fall back to a search or DP over small sides.
5. Many queries (M, N). Each query is already O(log). Mention a closed form: even side 2·⌊√(N + ⌊M/4⌋)⌋, odd side solved per branch with isqrt, giving O(1) per query.

Mid-level (L4)

• States the area equation and notices that 2×2 tiles cannot be placed freely.
• Produces a correct scan from the area bound downward, with 64-bit care.
• Tests the small edge cases (0,0, 0,1, 1,0).

Senior (L5)

• Derives the ⌊s/2⌋² cap and argues both directions (cannot exceed it, any smaller count fits).
• Spots that feasibility is not monotone in s and splits by parity before binary searching.
• Validates against a brute force and handles the 10⁹ bounds.

Staff (L6+)

• Gives the coloring proof of the cap crisply and explains why "use as many big tiles as possible" is optimal.
• Offers the O(1) closed form and discusses when it is worth the readability cost.
• Reasons about the 3×3 / general tile extension and where the simple cap argument breaks.