Asakura's Chase

Computer Science Level 5

The following problem is adapted from the LCC Placement Challenge, question 9. Details on output formats and test cases for Brilliant are given at the bottom of the challenge.

Ryoko Asakura has used her space-warping powers to turn a classroom into a battlefield. For some reason, things no longer follow the rules of Euclidean geometry; you can walk between two desks and possibly end up at the other end of the room! Kyon has been caught in this pocket dimension, and needs to stall while he waits for help to arrive. If Asakura is moving to catch Kyon, while Kyon runs away, will he be able to evade her indefinitely?

More formally, you are given a graph $G$ . The starting positions on the graph, $K_{(yon)}$ and $A_{(sakura)}$ will be decided by the players at the start. $A$ chooses her starting desk, followed by $K$ . Starting with $A$ and alternating each round, the active player may choose to move from a desk to any connected desk on $G$ . $G$ is assumed to be reflexive--that is to say, a player may choose to stay at a desk instead of moving. Assuming that $K$ plays optimally, is there a finite series of moves that allows $A$ to catch $K$ ?

Input

The first line will contain two integers, $N$ and $M$ , the number of nodes and edges respectively. $M$ lines will follow.

Each following line will contain two integers, $u, v$ , indicating an edge $uv$ on $G$ .

$1 \le N \le 1000$

$1 \le M \le N(N+1)/2$

$1 \le u, v \le N$

Output

If a finite series of moves exists that allow Asakura to catch up to Kyon ( $A = K$ under optimal play for $K$ ), print

Kyon is doomed!

Otherwise, print

Safe!

Sample Input 1

Sample Input 2

Output for Sample Input 1

Safe!

Output for Sample Input 2

Kyon is doomed!

Explanation for Sample Input 1

Here is what the classroom looks like: img Asakura might choose to start at desk 1. Kyon then chooses any desk other than 6 or 2 (say, 3). On her first turn, Asakura moves to desk 2. Kyon responds by moving to desk 4. In this way, he can continue to move to evade Asakura indefinitely.

Explanation for Sample Input 2

Here is what the classroom looks like: img

Asakura might choose to start at desk 4. Kyon then chooses any desk, say 5. On her first turn, Asakura moves to desk 7. Kyon can choose to stay still or move to desk 6. Either way, Asakura catches him next turn.

For our purposes, we will consider the set of 11 test cases here . Each test case is given consecutively, without any separation from the others, subject to the input format described above. Note that the first two cases are the samples. Your answer will be the number of cases in which Kyon is captured by Asakura.

The answer is 6.

1 solution

Spencer Whitehead
Jan 30, 2016

This is an example of the cop-win problem. Essentially, for all graphs $G$ in the test data, find if $G$ is cop-win or not. An algorithm for the cop-win problem in general exists in polynomial time, using strong products of graphs. This algorithm (discussed in Bonato and Nowakowski's "A Game of Cops and Robbers on Graphs") runs in $O(n^{6})$ , which is far too slow for the limit of 1000 on N.

Instead consider a different algorithm, that uses the cop-win strategy. This theorem states in essence:

1. A "fold" of a graph requires the same number of cops to police it as the base graph
2. A fold may be formed by choosing a vertex u covered by another vertex v and removing it (Where covering means that the neighbours of u are a subset of the neighbours of v unison v)
3. By recursively folding G, you will end up with an empty graph (cop-win) or a non-empty graph (robber-win)

We can implement this algorithm efficiently in $O(n^3)$ time by use of this theorem. Implementation for a single case is shown below. Case separation is then simply input parsing.

#include <iostream>
#include <vector>
#include <cmath>
#include <string.h>
#include <queue>

using namespace std;

int matrix[1005][1005];
int intree[1005], inqueue[1005];
int N, M;

bool cover(int u, int v) {
  for (int i = 0; i < N; i++) {
    if (intree[i]) {
      if (matrix[u][i] == 1 && matrix[v][i] == 0)
        return false;
    }
  }
  return true;
}

bool copwin() {
  queue<int> q;
  int treesize = N;
  for (int i = 0; i < N; i++) {
    intree[i] = 1;
    inqueue[i] = 0;
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (i != j && !inqueue[i] && matrix[i][j] && cover(i, j)) {
        q.push(i);
        inqueue[i] = true;
        break;
      }
    }
  }
  while (!q.empty()) {
    int c = q.front();
    q.pop();
    intree[c] = false;
    inqueue[c] = false;
    treesize--;
    for (int i = 0; i < N; i++) {
      if (matrix[c][i]) {
        if (intree[i] && !inqueue[i]) {
          for (int j = 0; j < N; j++) {
            if (i != j && matrix[i][j] && cover(i, j)) {
              q.push(i);
              inqueue[i] = true;
              break;
            }
          }
        }
      }
    }
  }
  return (treesize <= 0);
}

int main() {
  memset(matrix, 0, sizeof matrix);
  cin >> N >> M;
  for (int i = 0; i < N; i++) {
    matrix[i][i] = 1;
  }
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    matrix[u-1][v-1] = matrix[v-1][u-1] = 1;
  }
  cout << (copwin() ? "Kyon is doomed!" : "Safe!") << endl;
}

An alternate solution is to check for instances of $C_k, k \ge 4$ in $G$ , as any k-cycle of length 4 or greater cannot be folded.