SGU-103 Traffic Lights

Problem Link

The Problem in short:
Given an undirected weighted graph where each node contains a traffic light. The light shows two colors: Blue and Purple. Blue is visible for t_b seconds and Purple is visible for t_p seconds. This keeps repeating periodically. These two values may differ for different nodes. Cars can cross an edge (u,v) iff both u and v has same color at the moment when the car departs from u to v.

Now, given a source S and a destination T and the initial state of every node (there current color and how much time is remaining for that color), calculate the minimum time to reach from S to T.

Solution:
Run Dijkstra's from S. The tricky part is: given a time t and a node u such that, the current time is t and the car is at u, when will the light at u and the light at v show the same color ?

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<assert.h>
#include<stdlib.h>
#include<time.h>

#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

#define FOR(i,n) for(int i=0;i<(n);++i)
#define REP(i,a,b) for(int i=(a);i<=(b);++i)
#define CLR(a,x) memset(a,(x),sizeof(a))

typedef long long LL;
typedef pair<int,int> pii;

struct State {
    int at;
    int when;

    State(){}
    State(int _at, int _when){at = _at; when = _when;}

    bool operator < (const State other) const
    {
        return when > other.when;
    }
};

const int INF = (1<<29);

vector<int> adj[305];
int nodes, edges;
int cost[305][305];
int from,to;
int dist[305], parent[305];

int remaining[305], initColor[305], duration[305][2];

typedef pair<int,int> colorInfo;

colorInfo getColorInfo(int u, int t)
{
    if(t < remaining[u])
        return colorInfo(initColor[u],remaining[u]-t);

    int M = duration[u][0]+duration[u][1];
    int r = (t-remaining[u])%M;
    if(r < duration[u][1-initColor[u]])
        return colorInfo(1-initColor[u],duration[u][1-initColor[u]]-r);
    else
        return colorInfo(initColor[u],duration[u][initColor[u]]-(r-duration[u][1-initColor[u]]));
}

void getNext4InterestingTime(int u, int t, vector<int>& VT)
{
    VT.push_back(t);
    colorInfo info = getColorInfo(u,t);
    t += info.second;
    VT.push_back(t);

    FOR(i,4)
    {
        if(i%2==0)
            t += duration[u][1-info.first];
        else
            t += duration[u][info.first];

        VT.push_back(t);
    }
}

int calcTime(int u, int v, int t) // currently at u, current time t, want to go to v
{
    vector<int> interestingTime;

    getNext4InterestingTime(u,t,interestingTime);
    getNext4InterestingTime(v,t,interestingTime);

    sort(interestingTime.begin(),interestingTime.end());

    FOR(i,interestingTime.size())
    {
        if(getColorInfo(u,interestingTime[i]).first == getColorInfo(v,interestingTime[i]).first)
            return interestingTime[i];
    }

    return -1;
}

int solve()
{
    REP(i,1,nodes)
        dist[i] = INF;
    dist[from] = 0;
    parent[from] = from;

    State source(from,0);

    priority_queue<State> pq;
    pq.push(source);

    while(pq.empty()==false)
    {
        State u = pq.top();
        pq.pop();

        if(u.when > dist[u.at])
            continue;

        FOR(i,adj[u.at].size())
        {
            int x = adj[u.at][i];
            int y = calcTime(u.at,x,u.when);
            if(y == -1) continue;

            y += cost[u.at][x];
            if(dist[x] > y)
            {
                parent[x] = u.at;
                dist[x] = y;
                pq.push(State(x,y));
            }
        }
    }

    return dist[to];
}

int main()
{
    scanf("%d%d",&from,&to);
    scanf("%d%d",&nodes,&edges);

    FOR(i,nodes)
    {
        char s[5];
        scanf("%s%d%d%d",s,&remaining[i+1],&duration[i+1][0],&duration[i+1][1]);

        if(s[0]=='B')
            initColor[i+1] = 0;
        else
            initColor[i+1] = 1;
    }

    FOR(e,edges)
    {
        int u,v,w; scanf("%d%d%d",&u,&v,&w);
        adj[u].push_back(v);
        adj[v].push_back(u);
        cost[u][v] = cost[v][u] = w;
    }

    int ans = solve();

    if(ans >= INF)
    {
        puts("0");
    }
    else
    {
        vector<int> path;

        while(1)
        {
            path.push_back(to);
            if(to==from)
                break;
            to = parent[to];
        }

        cout<<ans<<"\n";

        for(int i=path.size()-1;i>=0;--i)
        {
            printf("%d",path[i]);
            if(i>0)
                printf(" ");
        }

        puts("");
    }

    return 0;
}

SPOJ :: KOICOST

Problem Link

The Problem in Short:

Given an undirected weighted graph.
There is a function Cost(u,v), which is defined as follows:
While there is a path between vertex u and v, delete the edge with the smallest weight. Cost(u,v) is the sum of the weights of the edges that were deleted in this process.
your task is to calculate the sum of Cost(u,v) for all pairs of vertices u and v, where u < v

The Solution:

To describe the solution we'll need a few notations:

bound(x,y) = the last edge, that has to be deleted if we want to disconnect vertex x and y by the process described in the problem statement.
f(u,v) = number of pair of vertices (x,y) such that, bound(x,y) = edge (u,v)
w(u,v) = weight of the edge (u,v)
csum(u,v) = cumulative sum of weights of all edge (u',v') such that w(u',v') <= w(u,v)

so, result = sum over ( csum(u,v)*f(u,v) ) for all edge (u,v)


Now, the problem is to calculate f(u,v) efficiently.

Consider the following process which is the reverse of the process described in the problem statement.

Lets assume that, initially all the vertices are disconnected. We add the edges one by one in the decreasing order of their weights.

define, g(u,v) = the number of pair of vertices (x,y) such that, (x,y) becomes connected when we add the edge (u,v) in the reverse process.

Note that, f(u,v) = g(u,v) (the proof is left to the reader)

Here is the algorithm that calculates g(u,v) for all the edges.

1. sort all the edges in the decreasing order of their weights
2. create a disjoint set of for all the nodes. (yes, we'll need the disjoint-set data structure)
3. in the root of each disjoint set, store the size of that set.
let's denote by sz(u), the size of the disjoint set that vertex u is in.

4. For each edge (u,v):

if u and v are connected already (i.e. in the same set)
f(u,v) = g(u,v) = 0
else:
f(u,v) = g(u,v) = sz(u) * sz(v)
result = result + f(u,v)*csum(u,v)
disjoint_set_union(u,v)

SPOJ :: PROBOR

Problem Link

type: dynamic programing, probability, expected value.

Solution:

define, dp[i][j][b] = after performing the probabilistic OR on the 0-th to i-th number, what is the probability that, the j-th bit is b.

expected_value = 1*dp[n-1][0][1] + 2*dp[n-1][1][1] + ... 2^k * dp[n-1][k][1] + ...

...hmm, it feels good to be back after a long long break.