CODEWITHSUNDEEP
javaalgorithmmath
rommel
rommel

Reputation: 47

Java USACO how to solve/understand the solution to Marathon (bronze december 2014)?

Here's the problem.

Here's the solution.

I already solved that problem but my code is too slow to pass all the testcases until 100, 000 points, so I read the official solution, but I could not understand the solution, the math part that says:

int largestSkip = 0;
    for(int i = 1; i < n-1; i++) {
      int noSkipDistance = Math.abs(x[i+1] - x[i]) + Math.abs(x[i] - x[i-1]) + Math.abs(y[i+1] - y[i]) + Math.abs(y[i] - y[i-1]);
      int skipDistance = Math.abs(x[i+1] - x[i-1]) + Math.abs(y[i+1] - y[i-1]);
      largestSkip = Math.max(largestSkip, noSkipDistance - skipDistance);
    }

How do they get those formulas?, if I understood well the variable skipDistance goes from 0 - skip 1- 2, 1- skip 2 -3, and so on, the other variables noskipDistance goes from 0 -2, 1 -3 (no skipping) and so on, are there other similar problems? or please if anyone could help me to understand I will be really grateful

The best solution that comes to my mind is, but It is too slow 

import java.io.*;
import java.util.*;
public class marathon {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("marathon.in"));
        PrintWriter pw = new PrintWriter(new File("marathon.out"));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][2];
        boolean[] flag = new boolean[n];

        for(int i = 0; i < n; i++){
            String s = br.readLine();
            int n1 = Integer.parseInt(s.substring(0 , s.indexOf(" ")));
            int n2 = Integer.parseInt(s.substring(s.indexOf(" ") +1, s.length()));
            arr[i][0] = n1;
            arr[i][1] = n2;
        }
        Arrays.fill(flag, true);
        long min = Long.MAX_VALUE;

        for(int i = 1; i < (n -1); i++){
            flag[i] = false;
            min = Math.min(min, solve(arr, flag, n));
            flag[i] = true;
        }
        pw.println(min);
        pw.close();
    }

    public static long solve(int[][]arr, boolean[] flag, int n){
        long min = Long.MAX_VALUE;
        long sum = 0;
        List<Integer> listX = new ArrayList<>();
        List<Integer> listY = new ArrayList<>();
        listX.add(arr[0][0]);
        listY.add(arr[0][1]);
        for(int i = 1; i < n -1; i++){
            if(flag[i]){
                listX.add(arr[i][0]);   
                listY.add(arr[i][1]);
            }
        }
        listX.add(arr[n-1][0]); 
        listY.add(arr[n-1][1]);

        for(int i = 1; i < listX.size(); i++){
            sum = Math.abs(listX.get(i -1) - listX.get(i)) +   Math.abs(listY.get(i -1) - listY.get(i)) + sum;
        }
        return sum;
    }
}

Upvotes: 0

Views: 920

Answers (1)

user801154
user801154

Reputation:

What happening in this solution is what is written in their editorial. At each point it is calculating the effective length it would go if it chose that point as skipping point.
For eq:
If there are four points (a, b, c, d) and you are at point 'a'. You can either go to 'b' or skip 'b'.

  • If you go to 'b', distance traveled is: Manhattan distance a -> b + b -> c; (Lets call it X)

  • If you skip 'b', distance traveled is: Manhattan distance a ->c; (Call it Y)

Gain in distance by choosing this choice = X - Y.

You objective is to find the maximum gain and choose the point which gives it.
In the end, ans is: sum of all Manhattan distances - the maximum gain.

Upvotes: 4

Related Questions