Shortest path in a custom binary search tree

Question

This a question from a coding competition

The original question can be found here http://www.olympiad.org.za/olympiad/wp-content/uploads/2014/03/2013-PO-Question-Paper.pdf Question 5

SHORTEST PATH THROUGH THE HALL [by Alan Smithee of Hulsbos High]

The hall is packed wall to wall with rows of chairs, but in each row there are exactly two chairs missing. The chairs in each row have numbers from 1 to 100. Write a program that will calculate the length of the shortest path from the front to the back of the hall. Each chair is 1 unit wide and each row is 1 unit deep (from the front of a chair to the front of the chair behind it). It is not possible to move diagonally. You may start in front of any gap in the front row and end behind any gap in the last row. You always walk through the middle of a gap. Illustrated is the shortest path through a hall, with five rows of chairs. In the illustration the hall is only 10 chairs wide instead of 100. The first number in the input will contain the number n – the number of rows. The next n lines will have two numbers, separated by a space, indicating where the gaps are. Example Input: 5 3 6 2 8 4 5 7 8 3 10

I think I have an efficient algorithm that I think will work, but I'm not sure how to implement it into Java.

What I want to do is break up each choice into a search tree so for instance if the user input was:

number of rows: 3

Spaces : 4 7 2 9 8 11

Make 2 search trees:

              4                               7            
       2           9                     2           9
     8   11      8   11             8      11     8      11

And then find the path where the difference between each node is the smallest So in this case the shortest path would be in the second tree 7->9->8 with the total distance being 5 (||7-9|-8|) So my question is then

1. Is this acceptable algorithm given the problem

2. How would I implement either this algorithm or another in java

@JuanLopes Take for instance this example (0s represent a space).

Row6: 0 2 3 4 5 6 0 8 9

Row5: 0 2 3 4 5 6 0 8 9

Row4: 1 2 3 0 5 6 0 8 9

Row3: 1 2 3 0 5 6 0 8 9

Row2: 1 2 3 0 5 6 0 8 9

Row1: 1 2 3 0 5 6 0 8 9

What I understand from your algorithm is that it looks at each row individually. So through rows 1-4 the distance between each space to the next row is equal but when you get to row 5 if you went down the path where all the 4s were missing it would take you longer compared to going down the path with all the 7s missing, does your solution take that into account?

Answer 1

The algorithm you described is not acceptable because there can be at most 100 rows, so if in each row the number of nodes in the tree doubles, you'll end up with 2^101 nodes in your tree in the worst case.

That problem can be solved by a simple dynamic programming, where on each step you have to choose the minimum between the first and the second gap:

T(0, j) = 1
T(i, j) = 1+min(
              abs(pos(i, j)-pos(i-1, 0)) + T(i-1, 0),
              abs(pos(i, j)-pos(i-1, 1)) + T(i-1, 1))

Where i is the ith row and j is either 0 or 1, denoting which gap we chose on the last turn. Here is some example Java implementation:

import static java.lang.Math.abs;
import static java.lang.Math.min;

public class Main {
    public static int solve(int[][] P) {
        int a = 1, b = 1;
        for (int i = 1; i < P.length; i++) {
            int na = 1 + min(
                    abs(P[i][0] - P[i - 1][0]) + a,
                    abs(P[i][0] - P[i - 1][1]) + b);

            int nb = 1 + min(
                    abs(P[i][1] - P[i - 1][0]) + a,
                    abs(P[i][1] - P[i - 1][1]) + b);

            a = na;
            b = nb;
        }
        return min(a, b);
    }

    public static void main(String... args) {
        System.out.println(solve(new int[][]{
                {3, 6},
                {2, 8},
                {4, 5},
                {7, 8},
                {3, 10},
        }));


        System.out.println(solve(new int[][]{
                {4, 7},
                {2, 9},
                {8, 11}
        }));
    }
}