HDU Multi-University Training 2019, Contest 4/5

Brute Force?/ Case Analysis: Contest 4, Problem M
First we can brute-forcely check factorize $n$ with the primes under $x = \sqrt[^5]{n}$. Then if $n$ is still larger than 1, other primes left to check is greater than $x$, which means there can only be at most 4 such primes. Analyzing the cases, we can see the answer will be 1 unless $n = p^2, p^3 \text{ or } p^4$ for some $p$.

XOR Operation/ Greedy?: Contest 5, Problem B
For each $a[i]$, define the favorite number as the best $b$ that $a[i]$ can choose (i.e. $a[i] \oplus b$ is smallest). For each $b[i]$ we define it similarly.
Without loss of generality, we assume there is no duplicate number in $A$ nor $B$. (The solution can be easily extended to the general case.)

Lemma 1: If for some number $a[i]$ and $b[j]$, they are each other’s favorite number, then $a[i] \oplus b[j]$ must be in the optimal solution. (If not, we can repair them together and the answer becomes better.)

Then we see this problem from a graph perspective: See each number as a vertex in a directed graph, and if $b$ is $a$’s favorite number, there is an directed edge from $a$ to $b$.

Lemma 2: There will be not cycle of length $>$ 2.
Proof (by contradiction): Suppose there is some cycle $x_1, x_2, x_3, …, x_n$. Then we have $x_1 \oplus x_2 < x_2 \oplus x_3 …. < x_n \oplus x_1 < x_1 \oplus x_2$. Contradiction.

Therefore, the idea to solve this problem is to effectively finding the cycle of length 2, putting the pair into the answer, and solve the problem again.

Leave a Reply

Your email address will not be published. Required fields are marked *