CF 1024808 - Плакаты

CF 1024808 - \u041f\u043b\u0430\u043a\u0430\u0442\u044b

Rating: -
Tags: -
Solve time: 4m 13s
Verified: yes

Solution

Problem Understanding

We have a rectangular bulletin board and two fixed-orientation rectangular posters. Alex always places his poster first. The question is not simply whether both posters fit, because Alex has two different goals depending on Bob's poster.

For the first plan, Alex wants to place his poster in a way that leaves some position where Bob can place his poster without overlap. For the second plan, Alex wants to place his poster so that every possible position for Bob overlaps it, making Bob unable to place his poster.

The input gives the height and width of the board, followed by the dimensions of Alex's poster and Bob's poster. The output contains two answers, one for each plan.

The dimensions are at most 150, which looks small, but the geometry is continuous, so a direct simulation of every possible position is unnecessary. The important part is finding the structural properties of two axis-aligned rectangles. A solution that tries every placement pair would perform roughly 20,000 × 20,000 checks in the worst case, which is unnecessary. We need a constant-time geometric observation.

A few cases are easy to mishandle. If Alex's poster itself does not fit, neither plan can work. For example:

20 30
21 10
20 30

The output is:

No
No

Even though Bob's poster fits, Alex cannot start the process.

Another trap is assuming that two posters fitting individually means they can coexist. For example:

50 100
30 20
30 20

The first answer is Yes because the two posters can be placed side by side vertically or horizontally. The second answer is No because Alex cannot block Bob completely when the board has enough remaining space around his poster.

Touching edges also matter. Rectangles are allowed to share borders, so a gap of exactly zero is not an obstacle.

Approaches

A brute-force approach would enumerate every possible position of Alex's poster and then check every possible position of Bob's poster. Since the largest number of positions is about 20,000 for each poster, this creates around 400 million comparisons. The approach is correct because it directly models the problem, but it ignores the rectangle structure.

For Plan A, the key observation is that two non-overlapping axis-aligned rectangles always have a separating horizontal or vertical line between them. If the separation is horizontal, the two posters consume their heights independently and their widths must fit together. If the separation is vertical, the opposite happens. This reduces the problem to two simple checks.

For Plan B, Alex wants to minimize the largest empty regions around his poster. The best position is the center of the board, because moving the poster toward an edge only increases the space available on the opposite side. Once Alex is centered, Bob can only fit either above/below Alex or left/right of Alex. We only need to check whether those remaining strips are large enough.

The brute-force works because it explores every possible placement, but fails because it repeats the same geometric reasoning thousands of times. The observation about separating lines and the optimal centered placement reduces everything to constant-time arithmetic.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O((HW)^2)	O(1)	Too slow
Optimal	O(1)	O(1)	Accepted

Algorithm Walkthrough

1. Check whether Alex's poster fits inside the bulletin board. If either its height or width exceeds the corresponding board dimension, both answers are No, because Alex cannot place his poster.
2. For Plan A, test whether the posters can be separated horizontally. This requires both posters to fit vertically and their widths to fit when placed next to each other:

ha <= H, hb <= H, and wa + wb <= W.

Also test the vertical separation case:

wa <= W, wb <= W, and ha + hb <= H.

If either case works, Bob can have a place. 3. For Plan B, imagine Alex places his poster in the middle of the board. The remaining height is H - ha, and the remaining width is W - wa. The largest possible top or bottom gap is half of the remaining height, and the largest left or right gap is half of the remaining width. 4. Check whether Bob can fit into one of these remaining strips. Bob can succeed if either:

hb <= (H - ha) / 2 and wb <= W

or:

wb <= (W - wa) / 2 and hb <= H.

If neither is possible, Alex successfully blocks Bob.

The reason this works is that any rectangle avoiding Alex's rectangle must be completely on one side of it. It cannot pass through Alex horizontally and vertically at the same time. Centering Alex minimizes all four side gaps simultaneously, so if Bob cannot fit there, no other placement can make the gaps smaller.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    H, W = map(int, input().split())
    ha, wa = map(int, input().split())
    hb, wb = map(int, input().split())

    if ha > H or wa > W:
        print("No")
        print("No")
        return

    plan_a = False

    if ha <= H and hb <= H and wa + wb <= W:
        plan_a = True

    if wa <= W and wb <= W and ha + hb <= H:
        plan_a = True

    plan_b = True

    if hb <= (H - ha) / 2 and wb <= W:
        plan_b = False

    if wb <= (W - wa) / 2 and hb <= H:
        plan_b = False

    print("Yes" if plan_a else "No")
    print("Yes" if plan_b else "No")

if __name__ == "__main__":
    solve()

The first part rejects impossible cases immediately because both plans require Alex to place his own poster. The Plan A calculation follows the separating-line argument directly. The two orientations cover every possible arrangement of two rectangles that do not overlap.

For Plan B, floating-point division is used intentionally. Using integer division would incorrectly round values such as (H - ha) / 2 downward. The comparison is only against integer poster sizes, so ordinary Python floating point precision is more than enough for these small values.

Worked Examples

For the first sample:

20 30
15 10
10 20

Plan A:

Check	Value
Horizontal separation	15 <= 20, 10 <= 20, 10 + 20 <= 30
Result	Possible

Plan B:

Check	Value
Remaining height	20 - 15 = 5
Remaining width	30 - 10 = 20
Top/bottom gap	2.5
Left/right gap	10
Bob fits in any gap	No

The first trace shows that the posters can coexist, but Alex can still block Bob by choosing the central position.

For the third sample:

50 100
30 20
30 20

Plan A:

Check	Value
Horizontal separation	20 + 20 <= 100
Result	Possible

Plan B:

Check	Value
Remaining height	20
Remaining width	80
Maximum vertical gap	10
Maximum horizontal gap	40
Bob fits	Yes

The second trace demonstrates why Plan A and Plan B are different questions. The posters fit together, but Alex cannot prevent Bob from using the large free areas.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a fixed number of arithmetic comparisons are performed
Space	O(1)	No data structures are stored

The constraints allow much slower solutions, but the constant-time solution avoids unnecessary geometric enumeration and easily fits the limits.

Test Cases

import sys
import io

def run(inp: str) -> str:
    old = sys.stdin
    sys.stdin = io.StringIO(inp)
    data = sys.stdin.readline
    H, W = map(int, data().split())
    ha, wa = map(int, data().split())
    hb, wb = map(int, data().split())

    if ha > H or wa > W:
        ans = "No\nNo"
    else:
        a = (ha <= H and hb <= H and wa + wb <= W) or \
            (wa <= W and wb <= W and ha + hb <= H)

        b = not ((hb <= (H - ha) / 2 and wb <= W) or
                 (wb <= (W - wa) / 2 and hb <= H))

        ans = ("Yes" if a else "No") + "\n" + ("Yes" if b else "No")

    sys.stdin = old
    return ans

assert run("""20 30
15 10
10 20
""") == "Yes\nYes"

assert run("""20 30
21 10
20 30
""") == "No\nNo"

assert run("""50 100
30 20
30 20
""") == "Yes\nNo"

assert run("""10 10
10 10
10 10
""") == "Yes\nNo"

assert run("""100 100
10 10
90 90
""") == "No\nYes"

Test input	Expected output	What it validates
20 30 / 15 10 / 10 20	Yes Yes	Basic coexistence and blocking
20 30 / 21 10 / 20 30	No No	Alex cannot fit
50 100 / 30 20 / 30 20	Yes No	Plan A and Plan B differ
10 10 / 10 10 / 10 10	Yes No	Exact board boundaries
100 100 / 10 10 / 90 90	No Yes	Large poster blocked by centered placement

Edge Cases

When Alex's poster exactly matches the board, the remaining space is zero. For:

10 10
10 10
10 10

the Plan A condition succeeds because the two posters can touch only if there is another arrangement, but here there is no room for Bob, so the second answer is No. The algorithm handles this because both remaining gaps are zero.

When Bob's poster exactly fits into one of the remaining strips, Alex fails Plan B. For example, if the remaining vertical gap is exactly large enough, the comparison uses <=, because touching Alex's poster is allowed.

When the board has plenty of space but the posters cannot be arranged side by side in the required orientation, Plan A must still return No. The separating-line checks cover both possible orientations, so no invalid diagonal arrangement is accidentally accepted.