CF 1531B1 - Мониторинг

CF 1531B1 - \u041c\u043e\u043d\u0438\u0442\u043e\u0440\u0438\u043d\u0433

Rating: -
Tags: *special
Solve time: 4m 20s
Verified: no

Solution

Problem Understanding

We are given a collection of monitors, each with a width and a height. We want to count how many unordered pairs of distinct monitors can be rotated so that their heights match. Rotating a monitor swaps its width and height. The goal is to find all pairs $(i, j)$ such that after possibly rotating one or both, the monitors have the same vertical height.

The input size $n$ can go up to 1000. That is small enough that an $O(n^2)$ solution is feasible because $n^2 = 10^6$ operations, which comfortably fits within typical 1-2 second limits. The height and width values can be very large ($10^9$), so any approach that tries to create arrays indexed by dimensions is impossible.

A subtle edge case occurs with square monitors where width equals height. For instance, if we have monitors $(2, 2)$ and $(2, 2)$, any rotation leaves the height unchanged. Similarly, if two monitors have dimensions $(2, 3)$ and $(3, 2)$, rotating the first and leaving the second unchanged aligns their heights at 3. A naive implementation that checks only the original orientation would miss this possibility.

Another edge case is multiple identical monitors. If we have three monitors of size $(3, 5)$, the algorithm must count all unordered pairs correctly, not just the first combination it encounters.

Approaches

The brute-force approach iterates over all unordered pairs. For each pair, we check four possibilities: leave both as-is, rotate the first, rotate the second, or rotate both. If any of these combinations results in equal heights, we increment the count. This is correct, because it explicitly examines every valid pairing. The number of checks is $4 \times \frac{n(n-1)}{2}$, which is $O(n^2)$ and works for $n \le 1000$.

The observation that lets us simplify the problem is that we only care about the set of possible heights each monitor can contribute: either its original height or its width if rotated. For each monitor, we can store a sorted tuple $(\min(w, h), \max(w, h))$. Two monitors can form a valid pair if there is any intersection between their possible heights. Checking all pairs with this property is also $O(n^2)$, but slightly cleaner than explicitly enumerating rotations.

We could attempt a frequency-based approach, where we count how many monitors support each height, then sum combinatorially. That works best for problems with very large $n$ or constrained height ranges. For $n \le 1000$, the $O(n^2)$ approach is simple, clear, and fast enough.

Algorithm Walkthrough

1. Read the number of monitors $n$.
2. Read the width and height of each monitor and store them as tuples in a list.
3. Initialize a counter count = 0 for valid pairs.
4. Loop over all pairs $(i, j)$ with $i < j$. For each pair, extract the widths and heights $(w_i, h_i)$ and $(w_j, h_j)$.
5. Check all four combinations of orientations: $(h_i == h_j)$, $(w_i == h_j)$, $(h_i == w_j)$, and $(w_i == w_j)$. If any match, increment count.
6. After checking all pairs, print count.

Why it works: the invariant is that we only count pairs once because $i < j$. For each pair, we consider all rotations, so no valid combination is missed. We never double-count because each unordered pair is considered exactly once.

Python Solution

PythonRun

We use i < j to ensure pairs are unordered and unique. The conditional directly checks all four rotation possibilities without explicitly rotating monitors. This avoids creating new tuples unnecessarily.

Worked Examples

Sample 1

Input: