Analysis: Message Relay by Brian Dean


This problem is solved in a relatively straightforward manner by simply tracing the message pattern forward starting from each cow, noting if we get stuck in a loop or not. To check if we are stuck in a loop, we can either mark cows that we have visited, stopping when we reach a cow that is marked, or we can maintain a counter of our total steps, stopping when we reach more than N steps. Both approaches will run in O(N^2) time in the worst case, which is amply fast given that N is at most 1000.

An alternative approach, which may be slightly easier to code, is to do the following: we first mark all cows forwarding to zero as non-loopy. Then we scan the cows again, marking any cows forwarding to a non-loopy cow as non-loopy. We repeat this process for N total scans, in effect propagating the "non-loopy" designation backwards across all non-loopy chains of cows. All cows remaining at the end must be loopy.

If we want to solve the problem faster (say, if N was at most 1 million), then we could use almost the same approach as above: scan forward from each cow, simulating the path taken by a message, marking cows we have seen so we can stop when we go around a loop. However, the key is that we stop our scan not only if we find ourselves in a loop, but also if we find ourselves visiting a cow that we have already "resolved". That is, suppose we start scanning from cow i and realize that eventually we get stuck in a loop. We then scan from i forward a second time and mark each cow we see as "loopy" (again stopping after we have gone around the loop once). Afterwards, if we ever see any of these cows during a future scan, we stop immediately and conclude that our path will end in a loop. This approach guarantees that we never re-visit the same cows multiple times, adding a significant boost in speed.

There is one more nice "trick" that is worth mentioning in the context of this problem. In order to detect whether we have entered a loop, the most obvious thing to do is to mark cows we've visited, stopping once we reach a marked cow. However, an alternative method for doing this is to walk down the list twice at the same time, once at normal speed and the second time at twice our normal speed. Think of this as sending one message at normal speed and another at twice normal speed, both moving at the same time. If the fast message catches the slow message, we know we are in a loop!

Here is my solution following the approach described in the second paragraph above, written in C:

#include <stdio.h>>
#define MAX_N 1000

int next[MAX_N+1];
int non_loopy[MAX_N+1];  

int main(void)
{
  int count, i, j, N;

  freopen ("relay.in", "r", stdin);
  freopen ("relay.out", "w", stdout);

  scanf ("%d", &N);
  for (i=1; i<=N; i++) {
    scanf ("%d", &next[i]);
    if (next[i] == 0) 
      non_loopy[i] = 1;
  }

  for (i=1; i<=N; i++)
    for (j=1; j<=N; j++)
      if (non_loopy[next[j]]) 
	non_loopy[j] = 1;
  
  for (i=1; i<=N; i++)
    count += non_loopy[i];

  printf ("%d\n", count);
  return 0;
}