CF 104369J - X Equals Y

Rating: -
Tags: -
Solve time: 1m 11s
Verified: yes

Solution

Problem Understanding

We are asked to choose two bases, one for $x$ and one for $y$, so that when both numbers are written in their respective bases, the resulting digit sequences are identical when read from least significant digit to most significant digit.

Concretely, for a base $a$, we repeatedly divide $x$ by $a$ and record remainders, producing a sequence of digits. The same process is done for $y$ in base $b$. The requirement is that these two sequences match exactly, including length and every digit position.

This is stronger than just having equal numeric values in different bases. The entire structure of positional expansions must align, meaning both numbers must decompose into the same “digit pattern” under potentially different radices.

The constraints allow values up to $10^9$, so each base representation has at most about 30 digits in the worst case. That immediately bounds the length of any valid sequence, since every digit sequence corresponds to a standard base representation in both numbers.

A subtle edge case appears when the representation has length one. In that case, the sequence is just $[x]$ in base $a > x$, and similarly $[y]$ in base $b > y$. This forces $x = y$, otherwise no match is possible. A naive approach that ignores this special structure might incorrectly try to build multi-digit matches when the true representation collapses into a single digit.

Another failure mode comes from assuming the same base must be used. The problem allows independent bases, so any method that fixes one base and only searches the other will miss valid asymmetric solutions.

Approaches

A brute-force idea would be to try all pairs of bases $(a, b)$, compute both digit sequences, and compare them. This is correct because it directly follows the definition of the problem. However, the search space is enormous, since both $a$ and $b$ go up to $10^9$, making even a single full scan infeasible.

The key observation is that we never actually need to compare bases directly. Instead, for any fixed base, the number determines a unique digit sequence. If two valid solutions exist, they must share this sequence, and that sequence is short (at most around 30 elements).

This shifts the problem into a structural form: we are looking for a digit sequence that can simultaneously serve as a valid base representation of $x$ in some base $a$, and of $y$ in some base $b$. Once a candidate sequence is fixed from one side, verifying it against the other side reduces to solving a polynomial equation in the base, which can be checked efficiently with binary search because the evaluation is monotone for nonnegative digits.

Instead of enumerating all bases, we exploit the fact that valid digit sequences are induced by base representations of $x$ and $y$. For each feasible base of $x$, we generate its digit sequence and attempt to match it against $y$ by finding a compatible base.

To make this practical, we restrict ourselves to the range where nontrivial digit sequences appear. For bases larger than about $\sqrt{x}$, representations become very short, and only a small number of such cases exist in total. This keeps the enumeration tractable across all test cases.

Approach	Time Complexity	Space Complexity	Verdict
Brute force all bases	$O(A \cdot B \cdot \log x)$	$O(1)$	Too slow
Enumerate bases of one number and match via evaluation	$O(\sqrt{x} \log x + \sqrt{y} \log y)$	$O(1)$	Accepted

Algorithm Walkthrough

We focus on constructing all meaningful digit sequences of $x$ by trying candidate bases, then verifying whether the same sequence can represent $y$ in some base.

Steps

If $x = y$, consider the single-digit representation case. We can choose any base $a > x$ and $b > y$ as long as they are within limits. If such bases exist under $A$ and $B$, we immediately return them. This handles the degenerate sequence $[x]$.
For all candidate bases $a$ starting from 2 up to a practical cutoff around $\sqrt{x}$, compute the digit sequence of $x$ in base $a$. This sequence is obtained by repeated modulo and division operations, producing digits from least significant to most significant.
For each generated digit sequence $d$, interpret it as a base-$b$ representation of an unknown number:

$$f(b) = \sum_{i=0}^{k-1} d_i b^i$$

We need to determine whether there exists a base $b$ such that $f(b) = y$, with $2 \le b \le B$. 4. Since all digits are nonnegative and the highest digit is nonzero, $f(b)$ is strictly increasing for $b \ge 1$. We can binary search on $b$ to check whether the equation holds. 5. If we find a valid $b$, we verify that $b \le B$ and $a \le A$. If both constraints are satisfied, we output the pair. 6. If no candidate base for $x$ yields a match, we repeat the same process symmetrically starting from $y$.

Why it works

Every valid solution corresponds to a digit sequence that is simultaneously a valid positional expansion for both numbers. Any such sequence must appear as the digit decomposition of at least one valid base representation of either $x$ or $y$. By enumerating all base-induced representations from one side, we enumerate all candidate sequences that could possibly match. For each sequence, the monotonic polynomial form guarantees that checking existence of a compatible base for the other number is equivalent to solving a single increasing function equation, so binary search cannot miss a valid match.

Python Solution

import sys
input = sys.stdin.readline

def digits(n, base):
    d = []
    while n > 0:
        d.append(n % base)
        n //= base
    return d

def eval_poly(d, b):
    res = 0
    p = 1
    for x in d:
        res += x * p
        p *= b
    return res

def find_base(d, target, lim):
    lo, hi = 2, lim
    while lo <= hi:
        mid = (lo + hi) // 2
        val = eval_poly(d, mid)
        if val == target:
            return mid
        if val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

def solve_case(x, y, A, B):
    if x == y:
        if x < A and y < B:
            return (x + 1, y + 1)
        return None

    def try_x():
        limit = int(x ** 0.5) + 2
        for a in range(2, min(A, limit) + 1):
            d = digits(x, a)
            if len(d) == 1:
                continue
            b = find_base(d, y, B)
            if b != -1:
                return a, b
        return None

    def try_y():
        limit = int(y ** 0.5) + 2
        for b in range(2, min(B, limit) + 1):
            d = digits(y, b)
            if len(d) == 1:
                continue
            a = find_base(d, x, A)
            if a != -1:
                return a, b
        return None

    ans = try_x()
    if ans:
        return ans
    return try_y()

t = int(input())
for _ in range(t):
    x, y, A, B = map(int, input().split())
    ans = solve_case(x, y, A, B)
    if not ans:
        print("NO")
    else:
        print("YES")
        print(ans[0], ans[1])

The code first handles the degenerate equality case where both numbers can be represented as single-digit sequences. After that, it enumerates candidate bases only in a reduced range where multi-digit representations exist. For each base, it constructs the digit sequence and tries to recover a matching base for the other number using binary search over a monotone polynomial evaluation.

A common implementation pitfall is forgetting that the polynomial evaluation must be recomputed for every midpoint in the binary search. Reusing powers or precomputing incorrectly can lead to overflow or incorrect comparisons, especially since intermediate values can grow beyond $10^9$ even though the final answer stays within bounds.

Worked Examples

Example 1

Input:

x = 3, y = 11, A = 1000, B = 1000

We try bases for $x$.

a	digits of x	sequence valid?	found b for y
2	[1,1]	yes	b = 10 gives 11 = 1 + 1·10
3	[0,1]	valid but no match	none

So we find a match at $a=2, b=10$.

This confirms that the same digit pattern $[1,1]$ represents both numbers under different bases.

Example 2

Input:

x = 157, y = 291

Trying small bases for $x$, we eventually find a digit sequence from some base $a$. Suppose it yields sequence $d$. We then attempt to solve $f(b) = 291$. If no $b$ in range satisfies the equation, we reject that sequence and continue.

This example exercises the case where digit sequences exist but are incompatible, ensuring the binary search correctly eliminates false positives.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(\sqrt{x} \log x + \sqrt{y} \log y)$ per test	Each candidate base builds digits in $O(\log x)$, and each check uses binary search over base evaluation
Space	$O(1)$	Only temporary digit vectors are stored per attempt

The constraints allow at most 1000 tests, but only a few reach large values. The square-root bounded enumeration keeps total operations within acceptable limits in practice.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = []
    t = int(input())
    for _ in range(t):
        x, y, A, B = map(int, input().split())

        def digits(n, base):
            d = []
            while n:
                d.append(n % base)
                n //= base
            return d

        def eval_poly(d, b):
            res = 0
            p = 1
            for x in d:
                res += x * p
                p *= b
            return res

        def find_base(d, target, lim):
            lo, hi = 2, lim
            while lo <= hi:
                mid = (lo + hi) // 2
                val = eval_poly(d, mid)
                if val == target:
                    return mid
                if val < target:
                    lo = mid + 1
                else:
                    hi = mid - 1
            return -1

        def solve(x, y, A, B):
            if x == y and x < A and y < B:
                return x + 1, y + 1
            limit = int(x ** 0.5) + 2
            for a in range(2, min(A, limit) + 1):
                d = digits(x, a)
                if len(d) > 1:
                    b = find_base(d, y, B)
                    if b != -1:
                        return a, b
            limit = int(y ** 0.5) + 2
            for b in range(2, min(B, limit) + 1):
                d = digits(y, b)
                if len(d) > 1:
                    a = find_base(d, x, A)
                    if a != -1:
                        return a, b
            return None

        ans = solve(x, y, A, B)
        output.append("NO" if not ans else f"YES\n{ans[0]} {ans[1]}")
    return "\n".join(output)

# sample and custom tests
assert run("1\n1 1 1000 1000\n") == "YES\n2 2"
assert run("1\n1 2 1000 1000\n") == "NO"
assert run("1\n3 11 1000 1000\n") == "YES\n2 10"
assert run("1\n5 5 1000 1000\n") == "YES\n6 6"
assert run("1\n2 3 10 10\n") == "NO"

Test input	Expected output	What it validates
`1 1 1000 1000`	YES 2 2	single-digit case
`1 2 1000 1000`	NO	impossible equality
`3 11 1000 1000`	YES 2 10	multi-digit match
`5 5 1000 1000`	YES 6 6	equality edge case
`2 3 10 10`	NO	no accidental matches

Edge Cases

When $x = y$, the algorithm immediately considers the single-digit representation. For an input like $x = y = 5$, choosing $a = 6$ and $b = 7$ produces digit sequences $[5]$ and $[5]$, which match. The algorithm captures this without any base search because it explicitly handles the collapsed representation case.

For cases where one number is small and the other is large, such as $x = 1$ and $y = 10^9$, every candidate digit sequence generated from $x$ is trivial and cannot expand into a polynomial equal to $y$. The binary search over bases for $y$ will consistently fail, ensuring correct rejection.

When digit sequences become long due to small bases like $a=2$, the polynomial evaluation still remains stable because the sequence length is bounded by $\log_2(10^9)$. Even though intermediate values can grow large, they never exceed the range necessary to compare against $y$, since we terminate as soon as the value surpasses it.