The shortest path in a custom binary search tree

Question

This question is from a coding contest

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

SHORT WAY THROUGH HALL [Alan Sithi from Hulsbos High]

The hall is packed on a 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 room. Each chair has a width of 1 unit, and each row is 1 unit deep (from the front of the chair to the front of the chair behind it). Unable to move diagonally. You can start before any space in the front row and end after any gap in the last line. You always go through the middle of a space. Illustrated is the shortest way through the hall, with five rows of chairs. In the illustration, the hall has only 10 chairs, not 100. The first number at the entrance will contain the number n - the number of lines. The next n lines will have two numbers separated by a space, where spaces are indicated. 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 in Java.

What I want to do is split each selection into a search tree, for example, if user input was:

number of rows: 3

Spaces: 4 7 2 9 8 11

Create 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 will be in the second tree 7-> 9-> 8 with a total distance of 5 (|| 7-9 | -8 |) So, my question is then

• Is this acceptable algorithm a given problem

• How to implement this algorithm in java

@JuanLopes Take, for example, 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 line separately. Thus, through lines 1-4, the distance between each space to the next line is equal, but when you get to line 5, if you went along the path where all 4s were absent, you will need more time than going along the path with all 7s missing. Does your decision take this into account?

Answer 1

The algorithm that you described is unacceptable because there can be no more than 100 lines, so if the number of nodes in the tree doubles in each line, you will end up with 2 ^ 101 nodes in your tree in the worst case.

This problem can be solved by simple dynamic programming, where at each step you need to choose a minimum between the first and second spaces:

 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 string i th, and j is either 0 or 1 , indicating which space we chose in the last turn. Here is a Java implementation example:

 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} })); } }