In topcoder Arena, I find a pretty interesting solution to the problem, SRM 567 div1 medium "TheJediTest".
The solution is given by ftiasch
Most of the solutions are bases on a greedy algorithm, but this one seems like based on some graph theory. Could someone tell me how this solution works? Thanks!
public class TheJediTest {
final static long INF = (long)1e18;
public int minimumSupervisors(int[] students, int m) {
int n = students.length;
long[][] graph = new long[n+1][n+1];
for(int i=0; i<=n; ++i) {
for(int j=0; j<=n; ++j)
graph[i][j] = INF;
}
for(int i=0; i<n; ++i)
graph[i][i+1] = 0;
for(int i=0; i<n; ++i) {
long sum = 0;
for(int j=i; j<n; ++j) {
sum += students[j];
int l = Math.min(i-1, 0);
int r = Math.max(j+1, n-1) + 1;
graph[l][r] = Math.min(graph[l][r], (sum + m - 1)/m * -1);
}
}
for(int k=0; k<=n; ++k)
for(int i=0; i<=n; ++i)
for(int j=0; j<=n; ++j)
graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
return -(int)graph[0][n];
}
}
First of all, note that the amount of supervisors is minimal if all children are at the same room. This gives us a lower bound on the number of supervisors — the total number of children divided by m (rounded up). This is the same as (sum + m - 1) / m. In general, define the cost of a segment as (sum + m - 1) / m where sum is the total number of children on the segment.
We can find other lower bounds by selecting a number of subsegments that have at least 2 rooms between each other. Then children from these subsegments can't appear in the same room in the final solution; so the number of supervisors must be at least the sum of costs of the subsegments.
Now we try to find the tightest lower bound by maximising the sum of subsegments defined in the previous paragraph. We can use a simple DP, but let's instead find a graph-theoretical solution.
Imagine that we already processed i floors. We can either skip the next floor (then we go to floor i + 1 and don't add anything to our sum of costs) or add a subsegment (then we go to corresponding floor and add the cost of subsegment to our sum of costs). Now build a graph with n + 1 vertices (meaning that we processed 0, 1, ... or n floors). Directed edge from i to i + 1 having a zero length will mean that we skip the floor. Other directed edges will mean we choose a subsegment, and their lengths will be the costs of these subsegments. We need to find a path of largest length from 0 to n.
Instead let's change a sign of all edge lengths. Now we need to find the shortest path from 0 to n. The graph has edges of negative length but no negative cycles (in fact it has no cycles at all). So we can use Bellman-Ford algorithm. Moreover, if we add all missing edges with positive infinite length (to make sure we never choose them) we can simply use Floyd algorithm.
So this solution searches for the tightest lower bound. As for why this bound is reachable, I can't prove this right now. But it seems reasonable. One can show, for example, that in the optimal solution neighbour segments must have exactly 2 floors between them and there can't be many students in these floors, so it seems that we can use supervisors from closest segments for these 2 rooms without increasing the total number of supervisors.
(Also note that the code above contains a mistake: in the following lines min and max should be swapped.)