Notes on Up and Down

If  the solution up.java is called from the command line with the up.in as parameter, both the efficient algorithm and the more obvious approach are both tried if W <= 520.  All data is checked for consistency.

The last two large cases are directly derived from smaller ones, with related answers.  The last, like an earlier small one, has a number of complete blockades, separating regions that can only be bridged by chutes and ladders.  The further separation of the regions in the last problem does not change the number of chute and ladders used, and in all but the last region, the spacings within regions are the same as before.  The last region just adds a number of extra full steps, based on the difference in the length of the region.

Time is of the essence here.  A hybrid algorithgm is also possible, making nodes of all spaces within S of the start of a chute or ladder.  With the limits on the data, it should lead to a table of size no bigger than 522, and the Java solution handling tables of that size does even the slower Warshall's algorithm very quickly.