1117 C. Magic Ship
13 March 2025
[ algorithms , codeforces , binary-search-value ]

Give this problem a try 1117 C. Magic Ship.


Approach


Example Code

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

public class Solution {
	public static long[] direction(char d) {
		if (d == 'U') return new long[]{0,1};
		if (d == 'D') return new long[]{0,-1}; 
		if (d == 'L') return new long[]{-1,0}; 
		if (d == 'R') return new long[]{1,0}; 
		return new long[]{0,0};
	}

	public static boolean check(long k, long x1, long y1, long x2, long y2, int n, long[][] pref) {
		long cnt = k / n, rem = k % n;
		x1 += cnt * pref[n-1][0] + (rem > 0 ? pref[(int)(rem-1)][0] : 0L);
		y1 += cnt * pref[n-1][1] + (rem > 0 ? pref[(int)(rem-1)][1] : 0L);
		long manhattan = Math.abs(x2-x1) + Math.abs(y2-y1);
		return manhattan <= k;
	}

	public static long search(long x1, long y1, long x2, long y2, int n, long[][] pref) {
		long max = (long) 1e18;
		long days = max;
		for (long m = max; m >= 1; m/=2) {
			while (check(days-m, x1, y1, x2, y2, n, pref)) {
				days -= m;
			}
		}
		return days;
	}

    public static void main(String[] args) throws Exception {
        // FastScanner io = new FastScanner("");
		FastScanner io = new FastScanner();

		long x1 = io.nextLong(), y1 = io.nextLong();
		long x2 = io.nextLong(), y2 = io.nextLong();

		int n = io.nextInt();
		char[] s = io.next().toCharArray();

		// prefix sum on net changes
		long[][] pref = new long[n][2];
		pref[0] = direction(s[0]);
		for (int i = 1; i < n; i++) {
			long[] dir = direction(s[i]);
			pref[i] = new long[]{pref[i-1][0] + dir[0], pref[i-1][1] + dir[1]};
		}

		long answer = search(x1, y1, x2, y2, n, pref);
		if (check(answer, x1, y1, x2, y2, n, pref)) io.println(answer);
		else io.println(-1);

		io.close();
    }

    /**
        RESERVED NUMBERS
    */
    public static int MOD = 1_000_000_007;

    /**
        DATA STRUCTURES
    */
    static class MultiSet {
        static TreeMap<Integer, Integer> multiset = new TreeMap<>();
        static void add(int x) {
            multiset.putIfAbsent(x, 0);
            multiset.put(x, multiset.get(x)+1);
        }
        static void remove(int x) {
            multiset.putIfAbsent(x, 0);
            multiset.put(x, multiset.get(x)-1);
            if (multiset.get(x) <= 0) multiset.remove(x);
        }
    }

    /**
        IO
    */
    static class FastScanner extends PrintWriter {
        private BufferedReader br;
        private StringTokenizer st;
		
		// standard input
        public FastScanner() { this(System.in, System.out); }
		public FastScanner(InputStream i, OutputStream o) {
            super(o);
			st = new StringTokenizer("");
            br = new BufferedReader(new InputStreamReader(i));
        }
		// USACO-style file input
        public FastScanner(String problemName) throws IOException {
            super(problemName + ".out");
			st = new StringTokenizer("");
            br = new BufferedReader(new FileReader(problemName + ".in"));
        }

        // returns null if no more input
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }
        public int nextInt() { return Integer.parseInt(next()); }  
        public double nextDouble() { return Double.parseDouble(next()); }   
        public long nextLong() { return Long.parseLong(next()); }   
    }
}

Complexity Analysis

  • Time Complexity:
  • Space Complexity:

Sign-off

Congratulations on making it this far! Best of luck in your future competitions!