🔗 Problem #1011

As a child, Woohyun believed that a future would come where humanity could live on planets other than Earth. Now, 23 years after he first set foot on this world called Earth, he is the world's youngest ASNA astronaut, waiting for the glorious moment when he'll set foot on a new world.

The spaceship he'll board carries a large-scale life support system to help settle Alpha Centauri, a new home for humanity, and because of its enormous size and mass, it's equipped with a space-jump device developed by mobilizing the latest technology. However, this space-jump device has the drawback of causing serious mechanical faults if the travel distance increases too sharply, so if it moved $k$ light-years the previous time it was activated, it can only move $k - 1$, $k$, or $k + 1$ light-years the next time. For example, the first time this device is activated, it could in theory move -1, 0, or 1 light-years, but since moving a negative or zero distance is meaningless, it can effectively move 1 light-year, and the next time it can move 0, 1, or 2 light-years. (If it then moves 2 light-years again, the time after that it can move 1, 2, or 3 light-years)

Since Woohyun Kim knows well how much energy the space-jump device consumes each time it's activated, he wants to travel from point $x$ to point $y$ using the minimum number of activations. However, for the safety of the space-jump device, he wants the movement distance right before arriving at point $y$ to always be exactly 1 light-year.

Write a program for Woohyun Kim that computes the minimum number of space-jump device activations required to travel exactly from point $x$ to point $y$.

The first line of the input gives the number of test cases $T$. For each test case, the current position $x$ and the target position $y$ are given as integers, with $x$ always smaller than $y$. $(0 ≤ x < y < 2^31)$

For each test case, print the minimum number of space-jump device activations required to travel exactly from point $x$ to point $y$.

• Input

TC
3
0 3
1 5
45 50

• Output

TC
3
3
4

The title seems to be a homage to Frank Sinatra's Fly me to the moon.

I was first introduced to Sinatra through Blue Moon in Fallout: New Vegas, and afterward I found myself listening to him often, since there are so many great tracks like Come Fly With Me and Theme from New York, New York.

Back to the problem — at a glance you might think, "why not just go as fast as possible?" But the following two conditions get in the way.

1. At the very first and very last segments, you must always jump exactly one square.
2. If you moved $k$ distance, you can only move $k - 1$ to $k + 1$ next.
3. You must always land exactly on the target point (passing over it doesn't count).

Because of these conditions, you can't just wander around aimlessly, so to speak.

Since this isn't about counting possibilities but about following a fixed rule, calculating and listing the results in order should help us find a clue.

It may not be obvious at a glance, but when looking for a pattern, the most convenient reference points are perfect squares (1, 4, 9...). The characteristics are as follows.

• The activation count increases by 1 right after a perfect square.
• The activation count increases by 1 at the midpoint between the current perfect square and the next.

That is, there's a visible change right after each perfect square, and the activation count increases by 1 at the midpoint of the interval based around a perfect square.

The activation count for a perfect square follows this pattern. The general formula for the activation count of a perfect square $n$ is as follows.

$$2\sqrt{n} - 1$$

For 9, $2 * 3 - 1 = 5$, so we can confirm the formula holds.

Since the activation count changes at the midpoint between perfect squares, we just need to calculate this midpoint. Suppose we have a general, non-perfect-square number $k$. Since this pattern revolves around perfect squares, we need to derive the relevant perfect square from $k$. We need to find:

• The smallest perfect square greater than $k$
• The midpoint of the perfect-square interval that $k$ falls into

1. Take the square root of $k$ and round it. This gives us the square root $\sqrt{n}$ of the perfect square $n$ that's greater than $k$ and closest to it.
2. Square $\sqrt{n}$ to get the nearest perfect square $n$.
3. Compute the midpoint $t$ of the perfect-square interval containing $k$, using $n - \sqrt{n}$.
4. If $k > t$, apply the formula $2\sqrt{n} - 1$, the same as the activation count for $n$.
5. If $k <= t$, apply the formula $2\sqrt{n} - 2$, which is the activation count for $n$ minus 1.

Let's use this method to compute the activation count for 7.

Since $\sqrt{7} \fallingdotseq 2.646$, rounding this gives 3. That is, the smallest perfect square greater than 7 is $3^2 = 9$.

Since $9 - \sqrt{9} = 9 - 3 = 6$, the midpoint of the perfect-square interval containing $k$ is 6. If the number is greater than 6, its activation count matches that of 9. Since the given number is 7, its activation count matches that of 9.

The activation count of 9 is $2\sqrt{9} - 1 = 6 - 1 = 5$, so the activation count of 7 is also 5.

We just need to translate the above procedure into code. The implementation difficulty is low.

JAVA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Baekjoon problem #1011 algorithm class
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/11/a1011">1011 solution</a>
 * @since 2021.06.11 Fri 09:06:34
 */
public class Main
{
	/**
	 * Main function
	 *
	 * @param args: [String[]] arguments
	 *
	 * @throws IOException data input/output exception
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		// Number of cases
		int T = Integer.parseInt(reader.readLine());
		
		for (int i = 0; i < T; i++)
		{
			String[] temp = reader.readLine().split(" ");
			
			// Current position
			double x = Double.parseDouble(temp[0]);
			
			// Target position
			double y = Double.parseDouble(temp[1]);
			
			// Distance between x and y
			double distance = y - x;
			
			System.out.println(solve(distance));
		}
		
		reader.close();
	}
	
	/**
	 * Function that returns the number of activations
	 *
	 * @param distance: [double] distance
	 *
	 * @return [int] number of activations
	 */
	private static int solve(double distance)
	{
		int result;
		
		double ref = Math.sqrt(distance);
		
		// If it's a perfect square
		if (ref % 1 == 0)
		{
			result = (int) (2 * ref - 1);
		}
		
		// Otherwise
		else
		{
			double next = Math.ceil(ref);
			
			// If it's greater than the midpoint between the previous and next perfect squares
			if (distance > Math.pow(next, 2) - next)
			{
				result = (int) (2 * next - 1);
			}
			
			// Otherwise
			else
			{
				result = (int) (2 * next - 2);
			}
		}
		
		return result;
	}
}

One thing to be careful about: the maximum value of $x$ and $y$ is $2^31$. The maximum value of int is 2,147,483,647, but $2^31$ is 2,147,483,648, so you must not use int when computing the distance between $x$ and $y$. Only the final result should be printed as an int.

I considered applying memoization, but since we'd need to initialize an array of size $2^31$, that would actually cause even worse overhead. Since this isn't a recursive function either, memoization probably wouldn't make much of a difference.

• Math