Codeforces Round #356 (Div. 1) - D. Bear and Chase

Problem Statement:
Codeforces Round #356 (Div. 1) - D. Bear and Chase

Summary:
We are to maximise the probability of guessing the position of a target in an undirected graph, given that the procedure that we must follow is:
Step 1. Choose a node. The shortest distance to the target is revealed. We either guess where the target is, or go to step 2.
Step 2. Target moves to another node via an edge. Now choose a node again and the shortest distance to the target is revealed. Guess where the target is.
Initially each node has equal probability of containing the target. After Step 1, target moves to a neighbouring node with equal probability among the neighbours.



Solution:
Check out the cool editorial: http://codeforces.com/blog/entry/45310.
Let Adj(i) be the adjacent nodes to i, Ring(s, d) be the nodes which shortest distance from s is d. The strategy to solve this problem is by choosing the starting point s that maximises the probability of guessing correctly. When we choose an s, the target is at d distance away with probability |Ring(s,d)|/n. If we guess at step 1, then P(guessing correctly at step 1 | at Ring(s,d)) = 1/|Ring(s,d)|. What if we don't guess at step 1?

At step 2, target will move to another neighbouring node. If target was in node u, it will move to a neighbour v with probability 1/|Adj(u)|. We compute Neigh(s, d), which is the set of nodes that are a neighbour of at least 1 node in Ring(s, d). For each v in Neigh(s, d), we can compute P(v | Ring) the probability of target ending up at node v, given that it was at a node in Ring(s, d). This is simply the sum of P(v | u) * P(u) over all u, where P(v | u) = 1/|Adj(u)| means the probability of target moving to v from a node u, and P(u) = 1/|Ring(s,d)| is the probability of target in a node u in Ring(s, d), given that it's in the ring.

Now that we have the distribution, we iterate through all t and choose the one in which we can maximise the probability of guessing correctly. For each t, the distance from the target to t will be revealed, say dt. When we are given this information, what should we do? Let T(dt) be the set of nodes that is in Neigh(s, d) that is dt away from t. For each u in T(dt), we find the one with highest P(u | Ring). Say that node is v_dt. Then the probability of guessing target correctly, given target is dt away from t, is P(v_dt | Ring) / P(T(dt)), where P(T(dt)) is the probability of t is dt away from target.

So the strategy is to iterate through all node in Neigh(s, d) and compute all possible dt. Then for each dt, we find the maximum P(v_dt | Ring). Then the maximum probability of guessing correctly if we choose node t at step 2 is sum of P(v_dt | Ring)/P(T(dt)) * P(T(dt)) = sum of P(v_dt | Ring) for all possible dt.

Amongst all t, we choose the one that gives us the maximum probability, and we compare that with the probability from Step 1 to come up with the final maximum probability of Ring(s, d).

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
vector<vector<int>> adj;
int dist[401][401];
constexpr int inf = 12345;
int n;
void FloydWarshal() {
  for (int k=0;k<n;++k) {
    for (int i=0;i<n;++i) {
      for (int j=0;j<n;++j){
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
}
vector<int> ring[401][401];
void PrepareRing() {
  for (int i=0;i<n;++i){
    for(int j=0;j<n;++j){
      ring[i][dist[i][j]].push_back(j);
    }
  }
}
vector<int> neighbour_adj[401][401];
vector<double> neighbour_prob[401][401];
void PrepareNeighbour() {
  double temp[410];
  int vis[410];
  for (int i=0;i<n;++i){
    for (int d=0;d<n;++d){
      for (int j : ring[i][d]) {
        for (int k : adj[j]) {
          vis[k] = 0;
          temp[k] = 0;
        }
      }
      for (int j : ring[i][d]) {
        for (int k : adj[j]) {
          temp[k] += 1.0/n * 1.0/adj[j].size();
          vis[k] = 1;
        }
      }
      for (int j : ring[i][d]) {
        for (int k : adj[j]) {
          if (vis[k]) {
            neighbour_adj[i][d].push_back(k);
            neighbour_prob[i][d].push_back(temp[k]);
            vis[k] = 0;
          }
        }
      }
    }
  }
}
double SecondProb(int s, int d, int t) {
  double prob_second = 0;
  double max_for_t[410];
  for (int i = 0; i < neighbour_adj[s][d].size(); ++i){
    max_for_t[dist[t][neighbour_adj[s][d][i]]]=0;
  }
  for (int i = 0; i < neighbour_adj[s][d].size(); ++i){
    int j = neighbour_adj[s][d][i];
    max_for_t[dist[t][j]] = max(max_for_t[dist[t][j]], neighbour_prob[s][d][i]);
  }
  for (int i = 0; i < neighbour_adj[s][d].size(); ++i) {
    prob_second += max_for_t[dist[t][neighbour_adj[s][d][i]]];
    max_for_t[dist[t][neighbour_adj[s][d][i]]] = 0;
  }
  return prob_second;
}
double Solve() {
  double max_prob_s;
  for (int s=0;s<n;++s){
    double prob_s = 0;
    for(int d=0;d<n;++d){
      double max_prob_t = 0;
      if (ring[s][d].empty()) continue;
      for(int t=0;t<n;++t){
        double prob_t = max(1.0/n, SecondProb(s, d, t));
        max_prob_t = max(prob_t, max_prob_t);
      }
      prob_s += max_prob_t;
    }
    max_prob_s = max(prob_s, max_prob_s);
  }
  return max_prob_s;
}
int main(){
  int m;
  scanf("%d%d",&n,&m);
  int u,v;
  for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
      dist[i][j]=inf;
    }
    dist[i][i]=0;
  }
  adj.resize(n);
  for(int i=0;i<m;++i){
    scanf("%d%d",&u,&v);
    u--;v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
    dist[u][v] = dist[v][u] = 1;
  }
  FloydWarshal();
  PrepareRing();
  PrepareNeighbour();
  printf("%.12f\n",Solve());
  return 0;
}

The run time complexity analysis is another cool thing about this problem. The argument goes as follows: Fix start node s and current distance d. On step 1, we iterate through Ring(s, d). On step 2, we will at most iterate through Ring(s, d-1), Ring(s, d) and Ring(s, d+1). Then by checking the iteration s, d-1 and s, d+1, we conclude that Ring(s, d) is at most iterated 4 times, and hence overall every node in the graph is iterated at most 4 times, which is O(n) after going through all d, fixing s and t. Hence overall complexity is O(n^3).