CF 1622A - Construct a Rectangle

Rating: 800
Tags: geometry, math
Solve time: 1m 17s
Verified: yes

Solution

Problem Understanding

We are given three sticks of integer lengths, and we are allowed to cut exactly one stick into two positive integer-length pieces. After this cut, we will have four sticks in total. The goal is to determine if these four sticks can form a rectangle, where opposite sides are equal. A square is considered a valid rectangle.

The input consists of multiple test cases. Each test case gives the lengths of the three sticks. The output is "YES" if it is possible to make a rectangle after one cut, and "NO" otherwise.

Because the number of test cases can be up to 10,000 and stick lengths can be as large as $10^8$, our solution must run in linear time per test case. We cannot afford nested loops over all possible splits of a stick, since splitting a stick into all possible pairs could lead to millions of operations in the worst case.

An important edge case is when two sticks already have the same length, and the third stick can be split into two pieces that match this length. For example, with lengths $2, 4, 2$, splitting the 4 into two 2s allows forming a rectangle. Another tricky case is when the largest stick is exactly equal to the sum of the other two, like $1, 5, 6$; here, splitting 6 into 1 and 5 creates a rectangle.

Approaches

The naive approach is to consider every stick and try splitting it into all possible integer pairs. For each split, check if the four resulting sticks can form a rectangle. For a stick of length $L$, there are $L-1$ splits, and with three sticks, this can become $O(L)$ per test case. Since $L$ can be $10^8$, this is clearly infeasible.

The optimal approach observes that a rectangle only requires two pairs of equal lengths. This limits the possibilities dramatically. Either one stick is equal to the sum of the other two (we cut it into the lengths of the other two), or two sticks are equal and the remaining stick can be split into two equal halves to match them. Formally, the conditions we need to check are:

Two sticks are equal and the remaining stick is even (we split it in half to match the other two).
The sum of two sticks equals the third (we split the largest stick to match the other two).

These checks only require constant time per test case, which is fast enough for up to 10,000 test cases.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(max(l_i))	O(1)	Too slow
Optimal	O(1)	O(1)	Accepted

Algorithm Walkthrough

Read the three stick lengths and sort them in non-decreasing order. Sorting ensures that the largest stick is easily identifiable.
Check if the two smallest sticks are equal. If they are, check if the largest stick is even. If both conditions hold, splitting the largest stick into two equal halves gives a rectangle.
Check if the sum of the two smallest sticks equals the largest stick. If true, splitting the largest stick into two pieces matching the other two sticks gives a rectangle.
If either of the above conditions holds, print "YES"; otherwise, print "NO".

This works because forming a rectangle requires exactly two pairs of equal lengths. Sorting the sticks reduces the number of cases we need to consider and makes the comparison straightforward.

Python Solution

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    sticks = list(map(int, input().split()))
    sticks.sort()
    a, b, c = sticks
    if (a == b and c % 2 == 0) or (a + b == c):
        print("YES")
    else:
        print("NO")

The solution first reads the number of test cases. For each test case, the three stick lengths are read and sorted. Sorting ensures that the comparisons are simple: the first two sticks are the smallest, and the third is the largest. The first condition handles the case where the rectangle can be made by splitting the largest stick into two equal parts. The second condition handles the case where the largest stick can be split to match the other two sticks. Printing is direct based on these checks. Sorting is safe because we are only dealing with three elements.

Worked Examples

Example 1:

Input: 6 1 5

Sorted sticks: [1, 5, 6]

Check if first two equal: 1 == 5 → False
Check if sum of first two equals largest: 1 + 5 == 6 → True

Output: YES

Example 2:

Input: 2 5 2

Sorted sticks: [2, 2, 5]

Check if first two equal: 2 == 2 → True
Check if largest is even: 5 % 2 == 0 → False
Check if sum of first two equals largest: 2 + 2 == 5 → False

Output: NO

These traces show how the algorithm quickly identifies valid splits without enumerating all possibilities.

Step	Variable `sticks`	a	b	c	Check 1	Check 2	Result
Example 1	[1,5,6]	1	5	6	False	True	YES
Example 2	[2,2,5]	2	2	5	False	False	NO

Complexity Analysis

Measure	Complexity	Explanation
Time	O(t)	Sorting 3 elements is O(1), each test case requires only constant operations
Space	O(1)	Only storing three stick lengths per test case

The algorithm scales linearly with the number of test cases. Memory use is minimal since only the three stick lengths are stored per test case.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = []
    t = int(input())
    for _ in range(t):
        sticks = list(map(int, input().split()))
        sticks.sort()
        a, b, c = sticks
        if (a == b and c % 2 == 0) or (a + b == c):
            output.append("YES")
        else:
            output.append("NO")
    return "\n".join(output)

# provided samples
assert run("4\n6 1 5\n2 5 2\n2 4 2\n5 5 4\n") == "YES\nNO\nYES\nYES"

# custom cases
assert run("3\n1 1 2\n4 4 8\n3 3 3\n") == "YES\nYES\nNO", "edge cases"
assert run("2\n1 100000000 100000000\n100000000 100000000 200000000\n") == "NO\nYES", "large values"
assert run("2\n5 5 5\n2 2 2\n") == "NO\nYES", "all equal"

Test input	Expected output	What it validates
1 1 2	YES	smallest case, sum split
4 4 8	YES	largest stick split evenly
3 3 3	NO	cannot form rectangle
1 100000000 100000000	NO	large difference, impossible
100000000 100000000 200000000	YES	large values, sum split
5 5 5	NO	all equal but odd largest
2 2 2	YES	all equal, even largest

Edge Cases

For 3 3 3, the sticks are all equal. Splitting any stick yields two pieces, e.g., split one 3 into 1 and 2, resulting in [3,3,2,1], which cannot form two equal pairs. The algorithm correctly prints "NO".

For 2 2 2, splitting one stick into 1,1 results in [2,2,1,1]. Sorting gives [1,1,2,2], which satisfies the first condition (a == b and c % 2 == 0) indirectly as the largest split is 2 (even). The algorithm prints "YES".

For 100000000 100000000 200000000, splitting the largest stick 200000000 into two 100000000 pieces produces [100000000,100000000,100000000,100000000], forming a perfect rectangle. The algorithm prints "YES". This confirms correct handling of maximum-size inputs.