Overview

Given \(N\) cards, the problem asks to select 2 or more cards such that the “product of integers on the front sides” equals the “product of integers on the back sides,” and find the minimum number of cards selected among all valid selections.

Analysis

Since each card can either be “selected” or “not selected,” a brute-force enumeration of all selections would yield \(2^N\) possibilities. With the constraint \(N \le 22\), this becomes at most \(2^{22} \approx 4.2 \times 10^6\) possibilities, which may exceed the time limit (TLE) in languages like Python.

To dramatically reduce the computational complexity, we use Meet-in-the-Middle.

The condition “the product of front sides equals the product of back sides” can be expressed as a ratio: $\( \frac{\prod P_i}{\prod Q_i} = 1 \)$

We split the selected cards into a first-half group \(A\) and a second-half group \(B\). Let the ratio of products for each group be \(\frac{p_A}{q_A}\) and \(\frac{p_B}{q_B}\). Then the condition can be transformed as follows: $\( \frac{p_A}{q_A} \times \frac{p_B}{q_B} = 1 \iff \frac{p_A}{q_A} = \frac{q_B}{p_B} \)$

In other words, we try all selections for both the first half and second half, computing the “ratio of front product to back product (as a reduced fraction).” Then, if the first half has ratio \(p : q\), and the second half has a selection with ratio \(q : p\), combining them satisfies the condition.

Algorithm

1. Preprocessing Divide each card’s \(P_i, Q_i\) by their greatest common divisor (GCD) in advance to make them coprime (reduced fraction). This prevents intermediate values from becoming too large.
2. Group Splitting Split the \(N\) cards into two groups: the first half (\(\lfloor N/2 \rfloor\) cards) and the second half (remaining cards).
3. Enumerate All Subsets of the First Half For every subset of the first-half group (excluding the empty set), compute the product of front values \(p\) and the product of back values \(q\) of the selected cards, then divide by GCD to obtain the ratio \((p, q)\).
   • If the ratio is \((1, 1)\) and the number of selected cards is 2 or more, update the answer candidate (minimum count).
   • Record in a dictionary (hash map) the “minimum number of cards” needed to produce each ratio \((p, q)\) as the key.
4. Enumerate All Subsets of the Second Half Similarly enumerate all subsets of the second-half group, build a dictionary, and update the answer candidate when the condition is met.
5. Combining First and Second Halves For each ratio \((p, q)\) recorded in the first-half dictionary, check whether the reverse ratio \((q, p)\) exists in the second-half dictionary. If it does, combining them makes the overall ratio \(1:1\). The total number of selected cards is “first-half count + second-half count,” so update the answer if this is smaller than the current minimum. (Since at least one card is selected from each half, the total is always 2 or more.)
6. Output the Result If the final minimum has been updated from its initial value, output that value; otherwise, output -1.

Complexity

• Time Complexity: \(O(2^{N/2} \log(\text{maximum product}))\) By halving \(N \le 22\), the number of states to explore is at most \(2^{11} = 2048\) for each half. Including GCD computations and dictionary lookups for each state, it runs very efficiently and easily fits within the time limit.
• Space Complexity: \(O(2^{N/2})\) The dictionaries storing results for the first and second halves have at most around \(2^{11}\) entries, so memory usage is minimal.

Implementation Notes

• Handling the “2 or more cards” condition A case where only 1 card is selected with \(P_i = Q_i\) violates the problem’s condition of “selecting 2 or more cards.” Therefore, when checking whether the ratio becomes \(1:1\) within the first half only or the second half only, you must verify that c >= 2 (the number of selected cards is 2 or more).

• Managing as reduced fractions Managing ratios as floating-point numbers (float) may introduce errors, so it is safe to always use integer pairs (p // g, q // g) as dictionary keys.

  Source Code

import sys
from math import gcd

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    A = []
    B = []
    idx = 1
    for i in range(N):
        p = int(input_data[idx])
        q = int(input_data[idx+1])
        idx += 2
        g = gcd(p, q)
        if i < N // 2:
            A.append((p // g, q // g))
        else:
            B.append((p // g, q // g))
            
    ans = float('inf')
    
    half1 = {}
    for i in range(1, 1 << len(A)):
        p, q = 1, 1
        c = 0
        for j in range(len(A)):
            if (i >> j) & 1:
                p *= A[j][0]
                q *= A[j][1]
                c += 1
        g = gcd(p, q)
        p //= g
        q //= g
        if p == 1 and q == 1 and c >= 2:
            if c < ans:
                ans = c
        if (p, q) not in half1 or c < half1[(p, q)]:
            half1[(p, q)] = c

    half2 = {}
    for i in range(1, 1 << len(B)):
        p, q = 1, 1
        c = 0
        for j in range(len(B)):
            if (i >> j) & 1:
                p *= B[j][0]
                q *= B[j][1]
                c += 1
        g = gcd(p, q)
        p //= g
        q //= g
        if p == 1 and q == 1 and c >= 2:
            if c < ans:
                ans = c
        if (p, q) not in half2 or c < half2[(p, q)]:
            half2[(p, q)] = c

    for (p, q), c1 in half1.items():
        if (q, p) in half2:
            c2 = half2[(q, p)]
            if c1 + c2 < ans:
                ans = c1 + c2
                
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.