Judging the Southeast Region

Lawrence was one of the three “World Finals” level problems in the set. Only two teams managed to solve it. It’s a shining example of a Dynamic Programming problem, with a little bit extra.

Here’s the Judge Input, the Judge Output, the main solving program, another Java program, and a C++ program.

Jump into the spoiler for an outline of a solution.
[spoiler]
This is a simple 2D dynamic programming problem, with the number of attacks being one dimension, and the depots being the other. The trick is to precompute the costs of leaving the rail line intact between every pair of depots BEFORE you get into the DP loops (or recursion). If you try to compute these on the fly, you’ll end up going over the same territory too much, looping and looping, and running out of time.

Here’s how you can compute the costs. sum[a][b] (a<=b) is the sum of strategic values of depots a through b, and cost[a][b] (a<=b) is the cost of leaving the railroad connected from depot a through depot b. stations[i] is the strategic value of station i.

            for( int j=0; j<n; j++ )
            {
                sum[j][j] = stations[j];
                cost[j][j] = 0;
                for( int i=0; i<j; i++ )
                {
                    sum[i][j] = sum[i][j-1] + stations[j];
                    cost[i][j] = cost[i][j-1] + stations[j]*sum[i][j-1];
                }
            }

To do the DP, it’s easiest to write a recursive function and memoize it. Check out the main judge program for details – it uses a method called place( attacks, start ) which returns the best score Lawrence can obtain by starting at start if he has attacks attacks remaining. The limits that the problem places on these makes it feasible to use a big memoizing array.
[/spoiler]