Home » 国际竞赛 » Details

USACO 2022 January Contest, Silver Problem 1. Searching for Soulmates

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午3:31

USACO 2022 January Contest, Silver Problem 1. Searching for Soulmates

Farmer John's cows each want to find their soulmate -- another cow with similar characteristics with whom they are maximally compatible. Each cow's personality is described by an integer $p_{i}$ ( $1 \leq p_{i} \leq 10^{18}$ ). Two cows with the same personality are soulmates. A cow can change her personality via a "change operation" by multiplying by $2$ , dividing by $2$ (if $p_{i}$ is even), or adding $1$ .

Farmer John initially pairs his cows up in an arbitrary way. He is curious how many change operations would be needed to make each pair of cows into soulmates. For each pairing, decide the minimum number of change operations the first cow in the pair must make to become soulmates with the second cow.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$ ( $1 \leq N \leq 10$ ), the number of pairs of cows. Each of the remaining $N$ lines describes a pair of cows in terms of two integers giving their personalities. The first number indicates the personality of the cow that must be changed to match the second.

OUTPUT FORMAT (print output to the terminal / stdout):

Please write $N$ lines of output. For each pair, print the minimum number of operations required for the first cow to make her personality match that of the second.

SAMPLE INPUT:

SAMPLE OUTPUT:

For the first test case, an optimal sequence of changes is $31 ⟹ 32 ⟹ 16 ⟹ 8 ⟹ 9 ⟹ 10 ⟹ 11 ⟹ 12 ⟹ 13$ .

For the second test case, an optimal sequence of changes is $12 ⟹ 6 ⟹ 7 ⟹ 8$ .

SCORING:

Test cases 1-4 satisfy $p_{i} \leq 10^{5}$ .
Test cases 5-12 satisfy no additional constraints.

Problem credits: Quanquan Liu

USACO 2022 January Contest, Silver Problem 1. Searching for Soulmates 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Richard Qi)

Denote $A$ as the number we start with and $B$ as the number we want to turn $A$ into.

Observation 1: The answer is always $O (\log max (A, B))$ .

To see why this is the case, we first prove that we can turn $A$ into $1$ using $O (\log A)$ operations.

Observe the binary representation (base 2) of $A$ . If $A$ is a power of two, then clearly we can just do dividing operations and reduce it to $1$ quickly. Otherwise, if the last bit is $0$ , do a dividing operation; if the last bit is a $1$ , do a plus followed by a dividing operation. This reduces the number of bits in the binary representation of $A$ by $1$ . Thus, either $A$ is a power of two and we do $O (\log A)$ dividing operations, or we do a maximum of $2$ operations to reduce the number of bits in the binary representation of $A$ by $1$ . Since there are only $O (\log A)$ total bits in $A$ , this takes $O (\log A)$ operations in total.

For the case of turning $1$ into $B$ , note that if we take the inverse of all operations, this is equivalent to turning $B$ into $1$ using "subtract 1" and dividing operations. By a similar argument as above, if the last bit of $B$ is a $0$ , we can divide by $2$ , otherwise we can subtract one and then divide by $2$ . This takes $O (\log B)$ operations to turn $B$ into $1$ , so it takes $O (\log B)$ operations to turn $1$ into $B$ using addition and multiplication operations.

Thus, it takes $O (\log A + \log B)$ operations to turn $A$ into $1$ , and then turn $1$ into $B$ , so the answer is always $O (\log max (A, B))$ .

Observation 2: There is never a division that takes place after a multiplication operation. Intuitively, any $1$ s that we add in between a multiplication and division operation would be more efficiently moved after the division operation.

We will prove this via proof by contradiction: suppose there is a division operation that takes place after a multiplication operation. Then, in the middle of the sequence of operations, we have $\dots *, +^{k}, / \dots$ , where $*$ denotes a multiplication operation, $+^{k}$ denotes $k \geq 0$ addition operations, $/$ denotes a division operation, and the $\dots$ indicate operations occurring before and after this subsequence of operations.

Now, because a division operation was used, and the number after the $*$ operation was even, the number of $+$ operations in between is even. Suppose we replaced this subsequence of operations with $\dots +^{k / 2} \dots$ . Let the number starting the subsequence be $x$ ; in the first version of the sequence of operations, we have $x ⟹ 2 x ⟹ 2 x + k ⟹ x + k / 2$ , while in the second version of the sequence of operations, we have $x ⟹ x + k / 2$ .

Since $+^{k / 2}$ is always less operations than $*, +^{k}, /$ and both subsequences correspond to the same function, the second subsequence never appears in an optimal solution.

Thus, we have proven that there is never a division that takes place after a multiplication operation, so the multiplication/division operations are of the form $/, /, /, \dots *, *, *$ , with some number of addition operations added in between every two division/multiplication operations. We can divide the operations into $3$ phases: the subsequence consisting of the last division operation and everything before it, the subsequence consisting of the addition operations after the last division and before the first multiplication, and the subsequence consisting of the first multiplication operation and everything after it. We label these subsequences $S_{1}, S_{2}, S_{3}$ .

These observations are good enough for partial credit. Suppose that we have found all numbers $x$ such that we need exactly $k$ operations to turn $A$ into $x$ , and suppose we have already done this for all $k^{'} \leq k$ . Then, we can find all numbers $y$ such that we need exactly $k + 1$ operations to reach $y$ from $A$ , as each of these $y$ must be a previous $x$ value after a division/multiplication/addition operation is applied. Additionally, each of these $y$ should be numbers that could not have been reached using $k$ or less operations.

It turns out that for the subtask, if we only consider small values of $x$ and $y$ in the above algorithm, we arrive at the correct answer. In other words, when turning $A$ into $B$ , the intermediate numbers do not get larger than $10^{5} + O (\log A + \log B)$ . The first and second observations mentioned above imply this, because during $S_{1}$ , the only way we can increase is through $+$ operations (but there are only a small number of total operations), and during $S_{2}$ and $S_{3}$ , the number only increases, until it arrives at $B \leq 10^{5}$ . Additionally, from the first observation, we only need to consider values of $k \leq O (\log max (A, B))$ , which allows us to calculate the values of $y$ from the values of $x$ in linear time for each value of $k$ .

Depending on implementation, this approach can be either $O (max (A, B) \log max (A, B))$ or $O (max (A, B))$ .

Observation 3: Just before a division operation, and just after a multiplication operation, there is at most one addition operation. "Just before" a division operation means before the division operation but after the previous division operation (if such a division operation exists); "just after" is defined similarly for multiplication.

We prove this for division (the proof for multiplication is similar). Suppose that we have a subsequence $\dots +^{2}, /, \dots$ . Then, we can replace this with $\dots /, +, \dots$ , as both subsequences represent the function $x ⟹ x / 2 + 1$ .

(Although not needed for this problem, this observation actually implies that when turning $A$ into $B$ , the intermediate numbers do not get larger than $10^{5}$ , which means in the brute force solution mentioned above, we could have only considered numbers $\leq 10^{5}$ . The reason for this is that during $S_{1}$ , the sequence consists of $/$ or $+ /$ subsequences concatenated together. In $/$ and $+ /$ , the original number cannot increase. Thus, the only way that an intermediate number is larger than $A$ is immediately after the first $+$ operation, which only happens if $A$ is odd. So, all intermediate numbers are $\leq 10^{5}$ .)

Observation 4: If we fix the total number of divisions as $D$ , then the sequence $S_{1}$ is fixed, and if we fix the total number of multiplications as $M$ , then the sequence $S_{3}$ is fixed.

We prove the first part of the statement (the second part is very similar). Suppose we make $D$ divisions in $S_{1}$ . Consider the first division; if $A$ is odd, then we must have added one before dividing (we could not have added more by the result of our third observation). If $A$ is even, then we could not have added anything before dividing, as we cannot add more than $1$ by the third observation, and if we add exactly one, we cannot divide by $2$ . Now, let the value of the number after the first division be $A_{2}$ . We now know that we need to transform $A_{2}$ into $B$ using exactly $D - 1$ divisions, so we can repeat the argument we just made. Repeating this down to $D = 0$ , we arrive at a forced sequence of operations in $S_{1}$ given the value of $D$ .

Similarly, given $M$ , we can arrive at a forced sequence of operations in $S_{3}$ .

Since the total number of operations is $O (\log max (A, B))$ , we can iterate over all pairs of values for $D$ and $M$ and generate the forced sequences $S_{1}$ and $S_{3}$ , which then force the number of addition operations that need to be in $S_{2}$ . Thus, given $D$ and $M$ , we can generate the entire sequence, count the number of operations used, and record the minimum such number of operations.

Depending on implementation, this is $O (\log^{3} max (A, B))$ or $O (\log^{2} max (A, B))$ , both of which fit comfortably in the time limit.

In the below implementation, the outer loop "removed" represents the number of multiplications $M$ in $S_{3}$ , which fixes the number $B^{'}$ that should be reached before applying the sequence of operations in $S_{3}$ . The inner while loop represents increasing the value of $D$ until the value of $A$ after applying the operations in $S_{1}$ becomes less than or equal to $B^{'}$ .

Instead of directly simulating the process of generating the operations in $S_{3}$ , the number of such operations can immediately be determined by looking at the binary representation of $B$ and counting the number of bits in the last $M$ bits of the binary representation $B$ . In particular, the number of additions in $S_{3}$ is equal to the number of $1$ bits in the number $B & (2^{M} - 1)$ , where $&$ denotes bitwise AND.

Danny's Implementation:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class SearchingForSoulmates {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        for (int t = Integer.parseInt(in.readLine()); t > 0; t--) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            long cow1 = Long.parseLong(tokenizer.nextToken());
            long cow2 = Long.parseLong(tokenizer.nextToken());
            long answer = Long.MAX_VALUE;
            for (int removed = 0; cow2 >> removed > 0; removed++) {
                long here = 0;
                long prefix = cow2 >> removed;
                long cow = cow1;
                while (cow > prefix) {
                    if (cow % 2L == 1L) {
                        cow++;
                        here++;
                    }
                    cow /= 2L;
                    here++;
                }
                here += prefix - cow;
                here += removed;
                here += Long.bitCount(cow2 & ((1L << removed) - 1L));
                answer = Math.min(answer, here);
            }
            out.append(answer).append('\n');
        }
        System.out.print(out);
    }
}

Bonus: Solve this problem in $O (\log max (A, B))$ time.

[/hide]