CF - Magic Ship

Official Editorial (C++)

Explanation

We start by calculating how the wind shifts us over a given number of days, and then we check whether we can cover the remaining distance with our own daily movement in that same amount of time. Specifically, we figure out the net change of one full cycle of wind, then multiply that by how many full cycles fit into our candidate number of days, and finally account for any leftover days by finding the partial cycle change. Note that the partial cycle change will take more days, which is fine as we can always reach our destination and continue counteracting the wind.

If we know the candidate number of days we are traveling for, we can measure the total change from the wind by calculating how many full cycles of wind fit within our number of days. We apply that shift to our initial position and then measure the distance to the destination. If the Manhattan distance to the destination is no greater than the number of days, it means we could have used some of those days to make up the distance with our own movements, so reaching the destination is possible by that day.

We perform a binary search on the number of days to find the smallest time for which this reachability check is true. If we know a candidate number of days lets us reach our destination in time, we can cut our search space as we then look for a smaller candidate number of days. Otherwise, we look for a larger candidate number of days. Finally, we output the smallest valid day or conclude that it is impossible, in which case we output $-1$.

Implementation

Copy
#include <cmath>
#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

bool reachable(std::pair<long long, long long> start,

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

public class MagicShip {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		long[] atPos = Arrays.stream(read.readLine().split(" "))
		                   .mapToLong(Long::parseLong)
		                   .toArray();

Copy
from typing import List


def reachable(start: List[int], end: List[int], wind: str, time: int) -> bool:
	start = start.copy()
	# count the net changes after one wind cycle
	wind_x = wind.count("R") - wind.count("L")
	wind_y = wind.count("U") - wind.count("D")
	cycle_num = time // len(wind)
	# speed this up by multiplying by the amount of complete cycles in the time