Since there are few barns (and thus few ranks), it may be feasible to just test all possible ranges and find the smallest. So let us first consider the problem of assigning cows to barns given that the barn ranks must come from a given range. This is really a bipartite matching problem - each cow has certain barns that she can be placed in, and we have to see if all the cows can be assigned.
As usual, network flow can be used to solve this problem. Construct a graph with a vertex for each cow, a vertex for each barn and source and sink vertices. Connect the source to the cows, to the cows to the barns they can occupy and the barns to the sink. The weights are all 1, except for the barn-sink edges whose weight is the capacity of the barns. If the network has flow equal to the number of cows, then we have a complete assignment of cows to barns.
Now consider that we want to find the smallest range for which we have this much flow. Firstly, we don't need to consider all O(B2) ranges; we can instead use a sliding window. We can further optimize the solution by reusing information as we slide the window. When the leading edge is advanced (expanding the window) all the current assignments remain valid, and we can just continue the Ford-Fulkerson algorithm incorporating the newly available edges.
When the trailing edge is advanced (contracting the window), some assignments become invalid. These cows are removed from their barns and made available for placement again. Note that at this point we must immediately try to reassign them, before advancing the leading edge again, as it may be possible to place these cows into other barns without expanding the window.
Each run of the shortest-path algorithm is O(NB), and it occurs every time a cow is added or the window is adjusted. In principle, every cow could be removed and re-added every time the lower edge is moved, so the total runtime is O(N2B2). In practice the runtime will be much lower, and it may even be possible to prove a better bound.
Canada's Richard Peng submitted this solution:
#include <stdio.h>
int grid[2000][30], rev[2000][30], low, high, n, b, cap[30], ans;
void
datain () {
FILE *f_in, *f_out;
int i, j;
f_in = fopen ("stead.in", "r");
fscanf (f_in, "%d%d", &n, &b);
for (i = 0; i < n; i++)
for (j = 0; j < b; j++) {
fscanf (f_in, "%d", &grid[i][j]);
grid[i][j]--;
rev[i][grid[i][j]] = j;
}
for (i = 0; i < b; i++)
fscanf (f_in, "%d", &cap[i]);
fclose (f_in);
}
int used[2000], to[2000], tot[30], found;
int path[2000], rec[2000];
void
search (int pos, int len) {
int i, j, id;
if (found)
return;
path[len] = pos;
used[pos] = 1;
for (i = low; i < high; i++)
if (tot[grid[pos][i]] < cap[grid[pos][i]]) {
path[len + 1] = grid[pos][i];
rec[0] = len + 1;
for (j = 1; j <= rec[0]; j++)
rec[j] = path[j];
found = 1;
return;
}
for (i = 0; i < n; i++)
if ((!used[i]) && (to[i] != -1)) {
id = rev[pos][to[i]];
if ((id >= low) && (id < high)) {
path[len + 1] = grid[pos][id];
search (i, len + 2);
}
}
}
int
match () {
int i, j, count;
for (i = 0; i < b; i++)
tot[i] = 0;
count = 0;
for (i = 0; i < n; i++)
to[i] = -1;
for (i = 0; i < n; i++)
for (j = low; (j < high) && (to[i] == -1); j++)
if (tot[grid[i][j]] < cap[grid[i][j]]) {
tot[grid[i][j]]++;
to[i] = grid[i][j];
count++;
}
while (count < n) {
for (i = 0; i < n; i++)
used[i] = 0;
found = 0;
for (i = 0; i < n; i++)
if ((to[i] == -1) && (used[i] == 0) && (found == 0)) {
search (i, 1);
if (!found)
return (0);
}
for (i = 1; i < rec[0]; i += 2)
to[rec[i]] = rec[i + 1];
tot[rec[rec[0]]]++;
count++;
}
return (1);
}
int
try (int range) {
int i;
for (i = 0; i + range <= b; i++) {
low = i;
high = i + range;
if (match ())
return (1);
}
return (0);
}
void
process () {
int delta;
ans = b;
delta = 16;
while (delta > 0) {
if ((ans - delta > 0) && (try (ans - delta)))
ans -= delta;
delta = delta / 2;
}
}
void
dataout () {
FILE *f_out;
f_out = fopen ("stead.out", "w");
printf ("%d\n", ans);
fprintf (f_out, "%d\n", ans);
fclose (f_out);
}
main () {
datain ();
process ();
dataout ();
}