Saturday, November 15, 2014

Topcoder SRM 638 Div. 1 Hard - CandleTimer

Follow up to this post

Problem Statement:
Topcoder SRM 638 Div. 1 HARD - CandleTimer

Solution:
Just solved this problem, and I must say that this problem is very challenging (at least for me) in a sense that there are quite a lot of stuff going on. The way the candles are burnt rings some bells to the intuition behind Dijkstra algorithm, and indeed the way to solve this problem is through some modification of Dijkstra.



Let's first break up the problem into smaller concepts. Suppose we reduce the problem to this: find the time needed for the tree to be completely burnt, given the set \(L\), which contains the leaves that we initially ignite. Now I'm telling you that we can model the path of the flames using Dijkstra (surprise surprise). Let d[i] be the array of distances of vertices, initialized to \(\infty\), and for each j such that \(j \in L\), initialize d[j] = 0. This indicates that vertex j is "passed" by a flame at time 0. Then we run a multiple source Dijkstra algorithm to find the minimum distance of each vertex i to any of the vertices that has already been passed by a flame. In the end of the algorithm, you will have d[i] be the time in which vertex i is passed by a flame. From here, we can determine what was the time taken for all candles to be completely burn:
1. Initialize time_taken to 0.
2. Iterate through all edges u-v:
2.1 We know d[u] and d[v]. Hence we check:
2.1.1 If |d[u] - d[v]| \(\geq\) length(u,v), then the time_taken is at least max{d[u], d[v]}.
2.1.2 Otherwise, WLOG, assume that d[u] < d[v]. This means that the flame will start burning from u, then after d[v]-d[u] time, another flame will arrive at v. Calculate the time needed for that edge to be completely burnt, and update time_taken accordingly using this information.

Now, to solve the problem, we use the following observation:
Let i, j be leaves of the tree. Let dist(i,j) be the distance between leaf i and leaf j. Then we have 2 possibility:
1. We want to check whether the tree can be totally burnt in dist(i,j) time. This means we burn only one of the leaf. Suppose we burn i. Then after dist(i,j) time, the flame will reach j. This means that dist(i,j) will be the time taken, if all other parts of the tree is burnt in this time frame. We employ a greedy approach here: We check for all other leaf k, if  dist(k,j) is bigger than dist(i,j), then we can burn leaf k too. Otherwise, we should not burn leaf k, as the flame from k will reach j faster than that of i, interfering the main burning process. Each burning of leaf is represented as d[i] = 0. Afterwards, we run the above Dijkstra and obtain the time taken to burn the whole tree and check whether it is indeed equal to dist(i,j).
2. Another scenario is if we burn both i and j, then we want to check whether dist(i,j)/2 is the time needed. The process is exactly the same as that of part 1 with an appropriate test whether to burn leaf k or not.

The whole approach runs in roughly \(O(N^3\lg{N})\).

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

/* using multiple source dijkstra! */
int maxint = (int) 1e8;
int dist[203][203]; // distance between leaves
int d[203];    // distance for dijkstra
int N;              // number of edges
int mark[800003];
vector<vector<pair<int,int> > > adj;
vector<int> len;
vector<int> A;
vector<int> B;

int time_needed() {
    priority_queue<pair<int, int> > pq;
    
    for (int i=0;i<=N;++i){
        if(d[i] == 0) pq.push(make_pair(-d[i], i));
    }
    while(!pq.empty()){
        int cur = -pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if(cur > d[u]) continue;
        for(int i=0;i<adj[u].size();++i){
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if(d[v] > cur + w) {
                d[v] = cur + w;
                pq.push(make_pair(-d[v], v));
            }
        }
    }
    int max_time = 0;
    for(int i=0;i<N;++i){
        int k = max(d[A[i]], d[B[i]]) - min(d[A[i]], d[B[i]]);
        if( k >= len[i] ) {
            max_time = max(max_time, max(d[A[i]], d[B[i]]) );
        } else {
            max_time = max(max_time, (k + len[i])/2 + min(d[A[i]], d[B[i]]));
        }
    }
    return max_time;
}


class CandleTimer {
public:
    int differentTime(vector<int> tA, vector<int> tB, vector<int> tlen){
        N = tA.size();
        A = tA;
        B = tB;
        len = tlen;
        adj = vector<vector<pair<int,int> > > (N+3);
        for(int i=0;i<N;++i){
            len[i] *= 2;
        }
        for(int i=0;i<=N;++i){
            for(int j=0;j<=N;++j){
                dist[i][j] = maxint;
            }
        }
        for(int i=0;i<=N;++i){
            dist[i][i] = 0;
        }
        for(int i=0;i<N;++i){
            adj[A[i]].push_back(make_pair(B[i], len[i]));
            adj[B[i]].push_back(make_pair(A[i], len[i]));
            dist[A[i]][B[i]] = len[i];
            dist[B[i]][A[i]] = len[i];
        }
        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]);
                }
            }
        }
        for(int i=0;i<=800000;++i){
            mark[i] = 0;
        }
        for(int i=0;i<=N;++i){
            for(int j=0;j<=N;++j){
                if(i == j) continue;
                if(adj[i].size() != 1 || adj[j].size() != 1) continue;
                if(mark[dist[i][j]]) continue;
                for(int k=0;k<=N;++k){
                    d[k] = maxint;
                }
                d[i] = 0;
                for(int k=0;k<=N;++k){
                    if(i == k || j == k || adj[k].size() != 1) continue;
                    if(dist[i][j] < dist[j][k]) {
                        d[k] = 0;
                    }
                }
                if(time_needed() == dist[i][j]) {
                    mark[dist[i][j]] = 1;
                }
            }
        }
        for(int i=0;i<=N;++i){
            for(int j=0;j<=N;++j){
                if(i==j) continue;
                if(adj[i].size()!=1 || adj[j].size()!=1) continue;
                if(mark[dist[i][j]/2]) continue;
                for(int k=0;k<=N;++k){
                    d[k] = maxint;
                }
                d[i] = d[j] = 0;
                for(int k=0;k<=N;++k){
                    if(i==k || k==j || adj[k].size()!=1) continue;
                    if(dist[i][j] <= max(dist[i][k], dist[j][k])) {
                        d[k] = 0;
                    }
                }
                if(time_needed() == dist[i][j]/2) {
                    mark[dist[i][j]/2] = 1;
                }
            }
        }
        int ans = 0;
        for(int i=0;i<=800000;++i){
            if(mark[i]) ++ans;
        }
        return ans;
    }
};