CF 353A - Domino

CF 353A - Domino

Rating: 1200
Tags: implementation, math
Solve time: 4m 19s
Verified: yes

Solution

Problem Understanding

We have a row of domino tiles. Each tile has a number on its upper half and a number on its lower half.

For every tile, we may either leave it as it is or rotate it by 180 degrees. Rotating a tile simply swaps its upper and lower values. Each rotation costs one second.

Our goal is to make both of these sums even:

1. The sum of all numbers currently on the upper halves.
2. The sum of all numbers currently on the lower halves.

We must find the minimum number of rotations needed. If no sequence of rotations can make both sums even, we output -1.

The number of tiles is at most 100, which is very small. Even an $O(n^2)$ solution would be trivial here. The challenge is not performance but discovering the parity observation that makes the answer immediate.

The key detail is that only parity matters. Whether a number is 2 or 6 is irrelevant, since both are even. Likewise, 1, 3, and 5 all behave identically because they are odd.

Several edge cases are easy to mishandle if we focus on actual values instead of parity.

Consider:

1
1 2

The upper sum is odd and the lower sum is even. Rotating gives upper = 2 and lower = 1, so the parities simply swap. One sum remains odd forever. The correct answer is -1.

A careless solution might think that because one tile contains both an odd and an even number, a rotation can always fix things.

Another important case is:

2
1 2
2 1

Initially, both sums are odd:

Upper = 3, Lower = 3.

Rotating either tile changes both sums by an odd amount, making both sums even. The correct answer is 1.

A solution that only checks whether the current sums are even would incorrectly return -1.

One more subtle case:

2
1 1
3 3

Upper and lower sums are both even:

Upper = 4, Lower = 4.

The answer is 0 even though every tile consists of two odd numbers. We do not need to rotate anything once the target parity is already achieved.

Approaches

A brute-force solution would try every subset of dominoes to rotate. For each subset, we would compute the resulting upper and lower sums and check whether both are even. Since every domino has two states, there are $2^n$ possible configurations.

This works conceptually because every valid arrangement corresponds to one subset of rotated tiles. Unfortunately, even for $n = 100$, $2^{100}$ configurations are astronomically large and completely impossible to enumerate.

The reason we can do much better is that parity is the only thing that matters.

Suppose a domino contains values $(x, y)$. Rotating it changes the upper sum by $y - x$ and the lower sum by $x - y$.

If $x$ and $y$ have the same parity, then $y - x$ is even. Rotating that domino does not change the parity of either total sum.

If $x$ and $y$ have different parity, then $y - x$ is odd. Rotating that domino flips the parity of both total sums simultaneously.

This observation completely characterizes the problem.

Let:

• $S_u$ be the current upper sum.
• $S_d$ be the current lower sum.

If both sums are already even, the answer is 0.

If one sum is even and the other is odd, the answer is immediately -1. Every useful rotation flips both parities together, so they always remain equal. We can never turn (even, odd) into (even, even).

If both sums are odd, we need exactly one parity-flipping domino, meaning a domino whose two numbers have different parity. Rotating that single domino makes both totals even. If no such domino exists, the answer is -1.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	$O(2^n \cdot n)$	$O(1)$	Too slow
Optimal	$O(n)$	$O(1)$	Accepted

Algorithm Walkthrough

1. Read all dominoes and compute the total upper sum and total lower sum.
2. While reading, check whether there exists a domino whose two values have different parity.

Such a domino is special because rotating it flips the parity of both total sums. 3. If both sums are even, output 0.

No rotations are required because the goal is already satisfied. 4. If both sums are odd, check whether a parity-flipping domino exists.

If it exists, output 1 because rotating exactly one such domino makes both sums even. 5. If both sums are odd but no parity-flipping domino exists, output -1.

Every rotation preserves parity, so the odd totals can never become even. 6. If one sum is even and the other is odd, output -1.

Any rotation changes both parities together, so the mismatch can never disappear.

Why it works

The crucial invariant is that rotating a domino with equal-parity ends changes nothing about the parity of either total sum, while rotating a domino with different-parity ends flips the parity of both totals simultaneously.

Because both totals always change together, it is impossible to move from (even, odd) or (odd, even) to (even, even). Those states are unreachable.

When both sums are odd, a single parity-flipping domino immediately converts (odd, odd) into (even, even), and one rotation is obviously minimal because at least one change is required. This exhausts all possible parity states, so the algorithm is correct.

Python Solution

import sys
input = sys.stdin.readline

n = int(input())

upper_sum = 0
lower_sum = 0
has_mixed_parity = False

for _ in range(n):
    x, y = map(int, input().split())
    upper_sum += x
    lower_sum += y

    if (x % 2) != (y % 2):
        has_mixed_parity = True

if upper_sum % 2 == 0 and lower_sum % 2 == 0:
    print(0)
elif upper_sum % 2 == 1 and lower_sum % 2 == 1:
    print(1 if has_mixed_parity else -1)
else:
    print(-1)

The first part accumulates the two total sums. At the same time, it records whether any domino has different parity on its two halves.

After all input is processed, the solution only needs to examine the parity of the two totals.

The order of the checks matters slightly for clarity. The already-valid case is handled first because it immediately gives answer 0. The (odd, odd) case comes next because it is the only situation where a single rotation may help. Everything else falls into the impossible category.

No overflow concerns exist because the maximum possible sum is only $100 \times 6 = 600$.

Worked Examples

Sample 1

Input:

2
4 2
6 4

Tile	Upper Sum	Lower Sum	Mixed-Parity Domino Exists
Start	0	0	No
(4,2)	4	2	No
(6,4)	10	6	No

Final parities:

Upper Sum	Lower Sum
Even	Even

Answer: 0

Both totals are already even, so no rotation is necessary.

Sample 2

Input:

1
1 2

Tile	Upper Sum	Lower Sum	Mixed-Parity Domino Exists
Start	0	0	No
(1,2)	1	2	Yes

Final parities:

Upper Sum	Lower Sum
Odd	Even

Answer: -1

The totals have different parity. Any useful rotation flips both parities together, so one total will always remain odd.

Additional Example

Input:

2
1 2
2 1

Tile	Upper Sum	Lower Sum	Mixed-Parity Domino Exists
Start	0	0	No
(1,2)	1	2	Yes
(2,1)	3	3	Yes

Final parities:

Upper Sum	Lower Sum
Odd	Odd

Answer: 1

Rotating either domino flips both sums from odd to even.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(n)$	One pass through all dominoes
Space	$O(1)$	Only a few variables are stored

With at most 100 dominoes, the linear scan is far below the time limit. Memory usage is constant and negligible compared to the available 256 MB.

Test Cases

# helper: run solution on input string, return output string
import sys, io

def solve():
    input = sys.stdin.readline

    n = int(input())

    upper_sum = 0
    lower_sum = 0
    has_mixed = False

    for _ in range(n):
        x, y = map(int, input().split())
        upper_sum += x
        lower_sum += y

        if (x & 1) != (y & 1):
            has_mixed = True

    if upper_sum % 2 == 0 and lower_sum % 2 == 0:
        print(0)
    elif upper_sum % 2 == 1 and lower_sum % 2 == 1:
        print(1 if has_mixed else -1)
    else:
        print(-1)

def run(inp: str) -> str:
    backup_stdin = sys.stdin
    backup_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    solve()

    out = sys.stdout.getvalue()

    sys.stdin = backup_stdin
    sys.stdout = backup_stdout

    return out.strip()

# provided sample
assert run("2\n4 2\n6 4\n") == "0", "sample"

# minimum size, impossible
assert run("1\n1 2\n") == "-1", "single tile"

# one rotation solves it
assert run("2\n1 2\n2 1\n") == "1", "odd odd with mixed parity tile"

# odd odd but no mixed parity domino
assert run("2\n1 1\n3 3\n") == "-1", "cannot change parity"

# larger all-equal case
assert run("5\n2 2\n2 2\n2 2\n2 2\n2 2\n") == "0", "already valid"

# maximum-style repeated pattern
inp = "100\n" + "\n".join(["1 2"] * 100) + "\n"
assert run(inp) == "0", "large input"

Test input	Expected output	What it validates
1 / 1 2	-1	Minimum-size impossible case
2 / 1 2 / 2 1	1	Single rotation fixes both sums
2 / 1 1 / 3 3	-1	No parity-changing domino exists
Five copies of (2,2)	0	Already-valid configuration
100 copies of (1,2)	0	Large input handling

Edge Cases

Consider:

1
1 2

The algorithm computes:

• Upper sum = 1 (odd)
• Lower sum = 2 (even)
• Mixed-parity domino exists

The sums have different parity, so the algorithm immediately returns -1.

Rotating the tile changes the state from (odd, even) to (even, odd). The mismatch remains. The output is correct.

Consider:

2
1 2
2 1

The algorithm computes:

• Upper sum = 3 (odd)
• Lower sum = 3 (odd)
• Mixed-parity domino exists

Since both totals are odd and a parity-changing domino exists, the algorithm returns 1.

Rotating either tile flips both totals to even. One move is sufficient and minimal.

Consider:

2
1 1
3 3

The algorithm computes:

• Upper sum = 4 (even)
• Lower sum = 4 (even)
• No mixed-parity domino exists

The first condition triggers and returns 0.

Although every domino has odd values, the target is already satisfied. The algorithm correctly avoids unnecessary rotations.

Consider:

2
1 1
1 1

The algorithm computes:

• Upper sum = 2 (even)
• Lower sum = 2 (even)

The answer is 0.

Rotations do nothing because every tile has identical values on both halves. The parity-based reasoning still handles this case correctly.