HackerEarth Delete and Cut Game problem solution

In this HackerEarth Delete and Cut Game problem solution, You are given a connected graph with N nodes and M edges. Two players A and B are playing a game with this graph. A person X chooses an edge uniformly, randomly, and removes it. If the size (number of nodes in component) of two non-empty connected component created are EVEN, then A wins otherwise player B wins.

Find the probability of winning the game for A and B. The probability is of the P/Q form where P and Q are both coprimes. Print PQ-1 module 1000000007.

Note: X can only select the edges which divide the graph into two non-empty connected components after they are removed. If no such edge is present in the graph, then the probability to win can be 0 for both A and B.

HackerEarth Delete and Cut Game problem solution.

#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
const int N = 100009;
const int M = 100009;

vector<int>E[N];
vector<int>graph[N];

int U[M], V[M];
bool isbridge[M];
int visited[N];
int arr[N],T;
int cmpno;
queue<int> Q[N];
int compo[N];
int region[N];
int sz;

int dp[N];

ll power(ll a, ll n)
{
    if(n == 0) return 1;

    ll ans = 1;
    ll val = a;

    while(n)
    {
        if(n%2)
        {
            ans *= val;
            ans %= mod;
        }

        val *= val;
        val %= mod;
        n /= 2;
    }

    return ans;
}

int adj(int u, int e)
{
    return U[e] == u ? V[e]:U[e];
}

int dfs0(int u, int edge)
{
    visited[u] = 1;
    arr[u] = T++;
    int dbe = arr[u];

    for(int i = 0 ; i < graph[u].size() ; i++)
    {
        int e = graph[u][i];
        int w = adj(u,e);

        if(!visited[w])
        {
            dbe = min(dbe,dfs0(w,e));
        }
        else if(e != edge)
        {
            dbe = min(dbe, arr[w]);
        }
    }

    if(dbe == arr[u] && edge != -1)
    {
        isbridge[edge] = true;
    }

    return dbe;
}

void dfs2(int v)
{
    int currcmp = cmpno;
    sz = max(sz,currcmp+1);
    Q[currcmp].push(v);
    visited[v]=1;
    while(!Q[currcmp].empty())
    {
        int u = Q[currcmp].front();
        region[currcmp]++;
        compo[u]=currcmp;
        Q[currcmp].pop();
        for(int i=0;i<(int)graph[u].size();i++)
        {
            int e = graph[u][i];
            int w = adj(u,e);
            if(visited[w])continue;
            if(isbridge[e])
            {
                cmpno++;
                E[cmpno].push_back(currcmp);
                E[currcmp].push_back(cmpno);
                dfs2(w);
            }
            else
            {
                Q[currcmp].push(w);
                visited[w]=1;
            }
        }
    }
}

int dfs1(int u)
{
    visited[u] = true;
    int flag = 0;
    int sum = 0;
    for(int i = 0 ; i < E[u].size() ; i++)
    {
        int v = E[u][i];
        if(!visited[v])
        {
            flag = 1;
            sum += dfs1(v);
        }
    }

    if(!flag)
    {
        dp[u] = region[u];
        return dp[u];
    }
    
    dp[u] = sum + region[u];
    return dp[u];
}


int main(){
    int n,m;
    cin>>n>>m;

    for(int i = 0 ; i < m ; i++)
    {
        int u,v;
        cin>>u>>v;
        u--;
        v--;
        U[i] = v;
        V[i] = u;

        graph[u].push_back(i);
        graph[v].push_back(i);
    }

    dfs0(0,-1);
    memset(visited,0,sizeof(visited));
    dfs2(0);
    memset(visited,0,sizeof(visited));
    dfs1(0);

    ll winA = 0;
    ll winB = 0;

    for(int i = 0 ; i < sz ; i++)
    {
        for(int j = 0 ; j < E[i].size() ; j++)
        {
            int v = E[i][j];
            int f = min(dp[i],dp[v])%2;
            int s = (n - min(dp[i],dp[v]))%2;
            if(f == 0 && s == 0)
            {
                winA++;
            }
            else
            {
                winB++;
            }
        }
    }   

    winA /= 2;
    winB /= 2;

    int temp = winA + winB;

    winA *= power(temp,mod-2);
    winA %= mod;

    winB *= power(temp,mod-2);
    winB %= mod;

    cout<<winA<<" "<<winB<<endl;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 17, mod = 1e9 + 7;

struct E{
    int v, u;
    bool bl;
    int o(int x){
        return x == v ? u : v;
    }
}  e[maxn];
int n, m, sz[maxn], hi[maxn], h[maxn];
vector<E*> g[maxn];
bool mark[maxn];
void dfs(int v = 0, int p = -1){
    mark[v] = 1;
    sz[v] = 1;
    hi[v] = h[v];
    for(auto e : g[v]){
        int u = e -> o(v);
        if(u != p)
            if(!mark[u]){
                h[u] = h[v] + 1;
                dfs(u, v);
                sz[v] += sz[u];
                if(hi[u] == h[u])
                    e -> bl = 1;
                hi[v] = min(hi[v], hi[u]);
            }
            else
                hi[v] = min(hi[v], h[u]);
    }
}
int rev(int a){
    int ans = 1;
    for(int b = mod - 2; b; b >>= 1, a = (ll) a * a % mod)
        if(b & 1)
            ans = (ll) ans * a % mod;
    return ans;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> e[i].v >> e[i].u;
        e[i].v--, e[i].u--;
        g[e[i].v].push_back(&e[i]);
        g[e[i].u].push_back(&e[i]);
    }
    dfs();
    int a = 0, b = 0;
    for(int i = 0; i < m; i++)
        if(e[i].bl){
            int cmp = min(sz[e[i].v], sz[e[i].u]);
            if(n % 2 == 0 && cmp % 2 == 0)
                a++;
            else
                b++;
        }
    cout << (ll) a * rev(a + b) % mod << ' ' << (ll) b * rev(a + b) % mod << 'n';
}

HackerEarth Delete and Cut Game problem solution.

Second solution

Leave a Reply