Official Analysis (Java)

Explanation

To transform $a$ into $b$, we proceed greedily. If $a > b$, it can be shown that it is never optimal to add more than once consecutively before dividing $a$ by 2. To see this, consider adding two times before the division. While this leads to three operations in sum, we can instead first divide and then just add one, which has the same effect but requires only two operations.

Then, if $a < b$, as the optimality of the strategy above is already shown, let's reuse it and work on $b$ by allowing multiplication, division, and subtraction by one. We therefore either divide $b$ by two (and first subtract by one if $b$ is odd) or subtract $b$ $b - a$ times to directly reach $a$. One can see that these operations applied on $b$ are equivalent to what one does on $a$ in reversed order.

Implementation

Time Complexity: $\mathcal{O}(N \log{\max(A, B)})$

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll solve(ll a, ll b) {
	if (a == b) {
		return 0;
	} else if (a > b) {
		/*

Copy
import java.io.*;
import java.util.*;

public class Soulmates {
	public static long solve(long a, long b) {
		if (a == b) {
			return 0;
		} else if (a > b) {
			/*
			 * Divide a greedily until a <= b, add 1 in case a is odd to enable

Copy
def solve(a, b):
	if a == b:
		return 0
	elif a > b:
		"""
		Divide a greedily until a <= b, add 1 in case a is odd to enable
		division.
		"""
		is_odd = a % 2
		return 1 + is_odd + solve((a + is_odd) // 2, b)