java - Shortest path in a custom binary search tree -

this question coding competition

the original question can found here http://www.olympiad.org.za/olympiad/wp-content/uploads/2014/03/2013-po-question-paper.pdf question 5

shortest path through hall [by alan smithee of hulsbos high]

the hall packed wall wall rows of chairs, in each row there 2 chairs missing. chairs in each row have numbers 1 100. write program calculate length of shortest path front of hall. each chair 1 unit wide , each row 1 unit deep (from front of chair front of chair behind it). not possible move diagonally. may start in front of gap in front row , end behind gap in last row. walk through middle of gap. illustrated shortest path through hall, 5 rows of chairs. in illustration hall 10 chairs wide instead of 100. first number in input contain number n – number of rows. next n lines have 2 numbers, separated space, indicating gaps are. example input: 5 3 6 2 8 4 5 7 8 3 10

i think have efficient algorithm think work, i'm not sure how implement java.

what want break each choice search tree instance if 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 find path difference between each node smallest in case shortest path in second tree 7->9->8 total distance being 5 (||7-9|-8|) question

1. is acceptable algorithm given problem

2. how implement either algorithm or in java

@juanlopes take instance example (0s represent 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 understand algorithm looks @ each row individually. through rows 1-4 distance between each space next row equal when row 5 if went down path 4s missing take longer compared going down path 7s missing, solution take account?

the algorithm described not acceptable because there can @ 100 rows, if in each row number of nodes in tree doubles, you'll end 2^101 nodes in tree in worst case.

that problem can solved simple dynamic programming, on each step have choose minimum between first , 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 ith row , j either 0 or 1, denoting gap chose on last turn. here 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 = 1, b = 1;         (int = 1; < 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);              = 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}         }));     } }