Telephone USACO 2021 January Contest

Telephone USACO Solution

Farmer John’s NN cows, conveniently numbered 1…N1…N, are standing in a line (1≤N≤5⋅1041≤N≤5⋅104). The iith cow has a breed identifier bibi in the range 1…K1…K, with 1≤K≤501≤K≤50. The cows need your help to figure out how to best transmit a message from cow 11 to cow NN.

See Also: USACO 2021 January Contest

It takes |i−j||i−j| time to transmit a message from cow ii to cow jj. However, not all breeds are willing to communicate with each other, as described by a K×KK×K matrix SS, where Sij=1Sij=1 if a cow of breed ii is willing to transmit a message to a cow of breed jj, and 00 otherwise. It is not necessarily true that Sij=SjiSij=Sji, and it may even be the case that Sii=0Sii=0 if cows of breed ii are unwilling to communicate with each-other.

Please determine the minimum amount of time needed to transmit the message.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains NN and KK.

The next line contains NN space-separated integers b1,b2,…,bNb1,b2,…,bN.

The next KK lines describe the matrix SS. Each consists of a string of KK bits, SijSij being the jjth bit of the iith string from the top.

OUTPUT FORMAT (print output to the terminal / stdout):

Print a single integer giving the minimum amount of time needed. If it is impossible to transmit the message from cow 11 to cow NN, then output −1−1.

SAMPLE INPUT:

5 4
1 4 2 3 4
1010
0001
0110
0100

SAMPLE OUTPUT:

6

The optimal sequence of transmissions is 1→4→3→51→4→3→5. The total amount of time is |1−4|+|4−3|+|3−5|=6|1−4|+|4−3|+|3−5|=6.

SCORING:

  • Test cases 1-5 satisfy N≤1000N≤1000.
  • Test cases 6-13 satisfy no additional constraints.

Problem credits: Dhruv Rohatgi

Solution

There’s a fairly simple quadratic-time solution: let every cow be the vertex of a graph, and say that there is a directed edge of weight |i−j||i−j| from cow ii to cow jj if cow ii is willing to talk to cow jj. Then the cost of the shortest path from cow 11 to cow NN is precisely the answer, and we can find it with e.g. Dijkstra’s algorithm. However, since the graph has O(N2)O(N2) edges, this is too slow.

That approach uses none of the structure of the original problem: that the edge weights are linear, or that the number of types of cows is very small. Let’s try to use this structure to make a different graph with fewer edges that has the same shortest-path costs.

The physical intuition for a cost of |i−j||i−j| to transmit a message from cow ii to jj is that the message travels 11 cow per unit time. Leveraging this intuition, let’s make a graph where each vertex encodes the location of the message. Then in one timestep, the message can either move left by one, or right by one. So we no longer have a quadratic number of edges.

Of course, the location of the message is not quite enough information to determine where it could go next. If we knew the cow who most recently sent the message, that would be enough information: in one unit time, a message sent by cow ii can either move one unit away from cow ii; or it can be “received” by the cow at its current location if cow ii is happy to talk to this cow. The former edge updates the message’s location, and the latter edge updates the message’s sender. Thus, this graph has O(N2)O(N2) vertices (for every location/sender pair) and O(N2)O(N2) edges (22 per vertex).

Despite appearances, that is progress: we used the specifically chosen edge weights to lower the degree of the graph to O(1)O(1). It remains to decrease the number of vertices, using the other symmetry of the problem: the small number of cow breeds. The key is that we don’t need to remember the sender, just the sender’s breed. Now we only have O(NK)O(NK) vertices and O(NK)O(NK) edges. Every edge has weight either 00 or 11 (cost 11 to move left or right; cost 00 to be received by the cow at the current location, if the breed matches the sending breed). The shortest path from (cow 11, breed of cow 11) to (cow NN, breed of cow NN) in this graph is (almost) the answer we need, and can be found by 0-1 BFS or Dijkstra’s algorithm.

There is one more catch: if the first and last cows are the same breed, this graph will always output N−1N−1 as the shortest path, which may be incorrect if this breed doesn’t talk to itself. There are a number of ways to resolve this, e.g. by changing the breed of cow NN to a fake breed 00, and remembering which breeds of cows are willing to talk to cow NN.

Here is Danny Mittal’s code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class TelephoneCorrect {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int k = Integer.parseInt(tokenizer.nextToken());
        int[] breeds = new int[n + 1];
        tokenizer = new StringTokenizer(in.readLine());
        for (int j = 1; j <= n; j++) {
            breeds[j] = Integer.parseInt(tokenizer.nextToken());
        }
        boolean[][] adj = new boolean[k + 1][k + 1];
        for (int b = 1; b <= k; b++) {
            String line = " " + in.readLine();
            for (int c = 1; c <= k; c++) {
                adj[b][c] = line.charAt(c) == '1';
            }
            adj[b][0] = adj[b][breeds[n]];
        }
        breeds[n] = 0;
        int[][] dist = new int[k + 1][n + 1];
        for (int b = 0; b <= k; b++) {
            Arrays.fill(dist[b], -1);
        }
        dist[breeds[1]][1] = 0;
        LinkedList<Integer> q = new LinkedList<>();
        q.add(breeds[1]);
        q.add(1);
        while (!q.isEmpty()) {
            int b = q.remove();
            int j = q.remove();
            if (j > 1 && dist[b][j - 1] == -1) {
                dist[b][j - 1] = dist[b][j] + 1;
                q.add(b);
                q.add(j - 1);
            }
            if (j < n && dist[b][j + 1] == -1) {
                dist[b][j + 1] = dist[b][j] + 1;
                q.add(b);
                q.add(j + 1);
            }
            if (adj[b][breeds[j]] && dist[breeds[j]][j] == -1) {
                dist[breeds[j]][j] = dist[b][j];
                q.addFirst(j);
                q.addFirst(breeds[j]);
            }
        }
        System.out.println(dist[0][n]);
    }
}

Additional note (thanks to Justin Wu for suggesting that this be included): As an alternative means of simplifying the graph, we can note that if the solution includes a transition from a cow at index ii to another cow (say, of breed bb), then without loss of generality we can assume this other cow is one of the two cows of breed bb closest to index ii — either the one closest on the left or closest on the right (the only exception here is the transition to the final cow in the last position).

One can argue this by taking an optimal path and noting that if any of its transitions (except the last) do not fit this pattern, they can be modified without penalty to fit the pattern. E.g., if the optimal solution goes from index 11 to ii to jj to NN and there is another cow of the same breed as the one at position ii between 1 and ii (say at i′i′), we loose nothing by changing the first leg of the path so it moves from 1 to i′i′ (so now we have an optimal solution that moves from 11 to i′i′ to jj to nn); we then adjust the next leg of the path the same way, and so on.

USACO 2021 January Contest Solution

Leave a Comment