## Sunday, December 21, 2014

### Codeforces Round 270 Problem D - Design Tutorial: Inverse The Problem

Problem Statement:
472D - Design Tutorial: Inverse The Problem

Solution:
Pretty interesting problem. Given a matrix of distances between nodes dist[u][v], return a weighted tree that satisfies this matrix. Here is my approach (I believe this is not the most efficient (or even efficient) or clever idea, but it worked :P)

First, based on the distances, run Dijkstra algorithm choosing any node as the source, and we will have a shortest path tree with as that source node as the root. We will also have the information of the shortest distances from root to all other nodes, d[u]. Then the idea is, for each pair of node, we check whether the distance matrix is consistent with this information on shortest distances from root. For each node u and v, we have two cases:
1. The lowest common ancestor of u and v is u or v themselves. Then if the tree is valid, dist[u][v] = |d[u] - d[v]|.
2. The lowest common ancestor of u and v is another node p. Then p is the root of a subtree containing u and v, hence we must have dist[u][v] = d[u] + d[v] - 2 * d[p].

If all these are consistent, then we have found the desired tree. Finding lowest common ancestor can be done in $$O(N\lg{N})$$ using segment tree on the euler path of the shortest path tree.

Implementation:

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstring>
using namespace std;
long long INF = (long long) 1e10;
int vis[2003];
int dist[2003][2003];
int idx[2003];
int height[2003];
int segtree[16003];
long long d[2003];
vector<int> euler;
vector<vector<int> > tree;
int n;
bool ok = true;
void djikstra(int source){
for(int i=0;i<n;++i){
d[i] = INF;
}
d[source] = 0;
int cnt = 0;
while(cnt != n){
int cur = -1;
for(int i=0;i<n;++i){
if(vis[i]) continue;
if(cur == -1 || d[cur] > d[i]){
cur = i;
}
}
if(d[cur] == 0 && cur != source) {
ok = false;
break;
}
vis[cur] = 1;
}
for(int i=0;i<n;++i){
if(vis[i]) continue;
if(d[i] >= d[cur] + dist[cur][i]){
d[i] = d[cur] + dist[cur][i];
}
}
++cnt;
}
}

void dfs(int u, int level) {
vis[u] = 1;
euler.push_back(u);
idx[u] = euler.size()-1;
height[u] = level;
for(int i=0;i<tree[u].size();++i){
int v = tree[u][i];
if(vis[v]) continue;
dfs(v, level+1);
euler.push_back(u);
}
}

void build(int p, int L, int R){
if(L==R){
segtree[p] = euler[L];
return;
}
int M = (L+R)/2;
build(2*p, L, M);
build(2*p+1, M+1, R);
segtree[p] = (height[segtree[2*p]] < height[segtree[2*p+1]] ? segtree[2*p] : segtree[2*p+1]);
}

int rmq(int p, int L, int R, int S, int T){
if(R < S || T < L) return -1;
if(S <= L && R <= T) {
return segtree[p];
}
int M = (L+R)/2;
int left = rmq(2*p, L, M, S, T);
int right = rmq(2*p+1, M+1, R, S, T);
if(left == -1) return right;
if(right == -1) return left;
return (height[left] < height[right] ? left : right);
}

int main(){
scanf("%d", &n);
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
scanf("%d", &dist[i][j]);
}
}
tree = vector<vector<int> > (n+3);
d[0] = 0;
djikstra(0);
if(!ok){
printf("NO\n");
return 0;
}
memset(vis, 0, sizeof vis);
dfs(0,0);
build(1,0,euler.size()-1);
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(idx[j] < idx[i]) continue;
int par = rmq(1, 0, euler.size()-1, idx[i], idx[j]);
if(i == par || par == j || i == j) {
int tmp = max(d[i]-d[j], d[j] - d[i]);
if(dist[i][j] != tmp || dist[i][j] != dist[j][i]){
ok = false;
break;
}
} else {
if(dist[i][j] != d[i] + d[j] - 2*d[par] ||
dist[j][i] != dist[j][i]) {
ok = false;
break;
}
}
}
if(!ok)break;
}
if(ok) printf("YES\n");
else printf("NO\n");
return 0;
}