CF 1249C2 - Good Numbers (hard version)

Rating: 1500
Tags: binary search, greedy, math, meet-in-the-middle
Solve time: 1m 37s
Verified: no

Solution

Problem Understanding

We are given several independent queries. Each query provides a large integer $n$, and we must output the smallest integer $m \ge n$ such that $m$ can be expressed as a sum of distinct powers of 3. In other words, every valid number corresponds to choosing a subset of numbers from $1, 3, 9, 27, \dots$ and summing them, with each power allowed at most once.

This structure means every good number is essentially a base-3 representation where digits are restricted to 0 or 1 only. If any digit 2 appears in the ternary representation, that value is not directly valid, and we must “round it up” to the next representable number.

The input constraint $n \le 10^{18}$ implies we can safely consider powers of 3 only up to about $3^{38}$, since $3^{39}$ already exceeds $10^{18}$. That bounds the state space of all relevant constructions to fewer than 40 positions. With up to 500 queries, any solution that is linear in this bit-length per query is easily fast enough.

A naive idea is to generate all valid sums of distinct powers of 3 and then search for the smallest one not less than $n$. However, the number of such sums is $2^{40}$, which is far too large (about one trillion possibilities). Even generating or sorting them is impossible.

A more subtle failure mode arises if we try to greedily interpret $n$ in base 3 and simply replace every digit 2 with a carry. A careless implementation might adjust digits locally without properly propagating carries to higher positions, producing values that are still invalid or even smaller than $n$. For example, if we see a digit pattern like $1,2,0$, fixing only the 2 without considering the interaction with lower digits can break monotonicity guarantees.

Approaches

The brute-force approach enumerates all subsets of powers of 3 up to $3^{38}$, computes their sums, and then answers each query by binary searching this list. This is correct because it directly constructs the entire set of valid numbers. The problem is that the subset space grows exponentially with the number of powers. With about 39 usable powers, we already reach $2^{39}$, which is computationally infeasible.

The key observation is that validity depends only on ternary digits being in ${0,1}$. This means we never need to reason about subsets directly. Instead, we work in base 3 and treat the problem as a constrained digit system: we want the next number whose ternary representation contains no digit 2.

This transforms the task into a digit-correction problem similar to finding the next number with a restricted alphabet. We can fix invalid digits by scanning from least significant to most significant position, and whenever we encounter a 2, we increment the next position and zero out everything below. This is analogous to binary “next number with no consecutive ones,” but adapted to base 3 with a forbidden digit.

Once we enforce all digits are 0 or 1, we may still end up below $n$, so we ensure minimality by constructing the smallest valid configuration strictly greater or equal to the original number through controlled propagation of carries.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	$O(2^{40})$ per query	$O(2^{40})$	Too slow
Optimal	$O(\log n)$ per query	$O(\log n)$	Accepted

Algorithm Walkthrough

We process each query independently.

Convert $n$ into its base-3 representation stored in a mutable array of digits.

This gives direct a