Competitive Programming (Draughts) | CodeChef

This problem was asked in February challenge 2014. Around 900 people were able to solve this problem during challenge duration.

It’s a nice problem, requiring the knowledge of graphs. It’s not very intuitive for beginners. And also not very straightforward for someone not doing competitive programming.

CodeChef Problem Link

Problem Statement

Furik and Rubik have come to the sanatorium, which consists of N rooms and M passageways. Each passageway connects two rooms, and there is at most one way to move between each pair of rooms. Some rooms have opened windows. There is a draught between two different rooms if both rooms have opened windows, and are connected with each other by some way.

Furik is interested in one question: what is the number of pairs of rooms, which have a draught between them. Rubik wants to know what is the number of the rooms, which have at least one draught passing through the room.

In a single line print two numbers, denoting the answers to Furik and Rubik questions.

Constraints

• 1 ≤ N ≤ 50000 (5 × 10⁴)
• 0 ≤ M ≤ N − 1
• There is at most one way to move between each pair of rooms, that is, the given graph is a forest

Note: We advise you to try this problem once without reading the solution (ahead).

Explanation

As constraints say N <= 5 x 10^4, permissible solution should be O(n) or O(n*logn).

A point to note is that given graph (of rooms/nodes) is a forest. This means there could be multiple unconnected trees/nodes. For instance:

Consider the given example, N ie rooms = 6 and M ie connection = 4. Also let, window is opened in the following rooms: [6, 1, 2, 3]

Now problem statement states, there can be only at most 1 path between a pair of rooms, so there are no cycles. For traversing the forest we would use DFS (Depth-first search). Now let’s analyse the given problems

• Problem 1

Since there’s only one path possible between two rooms, we just need to count the number of rooms having window open in a single tree. And then calculate the number of pairs, using combinatorics {n \choose 2} ie
((n)*(n-1))/2. Adding the number of pairs from different trees will give the required solution.

• Problem 2

For second problem, we just need to count the number of rooms which lie between two rooms having open windows. For instance:

In above tree: (1) – signifies window is open and (0) – signifies window is closed.

Let’s start DFS from root 6 (start with counter 1). Then we encounter node 1 (and update our counter to 2), when we encounter node 2, its window is closed. We encountered our first open window at 6, but since it’s a dead end, we backtrack and move to node 1, (updating our counter from 3 to 2). Then we encounter node 5, its window is open so we add the counter value to answer. Adding the number of rooms having one draught passing through them from different trees will give the required solution.

Code Implementation

//
//  main.cpp
//  Codechef Draught
//
//  Created by Himanshu on 24/08/21.
//

#include <iostream>
#include <vector>
using namespace std;
long long tmp = 0;

void dfs(int x, vector<int> graph[], int vis[], int window[], long long &cPath, long long &cNode) {
    tmp++;
    vis[x] = 1;

    // Set tmp = 0, and add the number of paths(tmp) between 
    // two rooms having a window each
    if (window[x] == 1) {
        cNode++;
        cPath += tmp;
        tmp = 0;
    }

    for (int i=0; i<graph[x].size(); i++) {
        int j = graph[x][i];
        if (vis[j] == 0) {
            dfs(j, graph, vis, window, cPath, cNode);
        }
    }

    // Backtracking and removing previously visited
    // node from Rubik's answer 
    tmp--;
    if (tmp < 0) {
        tmp = 0;
    }

}

int solve (vector<int> graph[], int window[], int n) {
    int vis[n+1];
    long long ansF = 0, ansR = 0, cPath = 0, cNode = 0;
    for (int i=1; i<=n; i++) {
        vis[i] = 0;
    }
    
    for (int i=1; i<=n; i++) {
        cNode = 0;
        cPath = 0;
        // Performing DFS on each tree, starting from a room 
        // having a window
        if (vis[i] == 0 && window[i] == 1){
            dfs(i, graph, vis, window, cPath, cNode);
            ansF += (cNode*(cNode-1))/2;
            if (cPath > 1) {
                ansR += cPath;
            }
        }
    }

    cout<<ansF<<" "<<ansR<<endl;
    return 0;
}

int main () {
    int n = 0, m = 0;
    cin>>n>>m;
    int window[n+1];
    vector<int> graph[n+1];
    int connect[m+1][2];
    
    for (int i=1; i<=n; i++) {
        cin>>window[i];
    }

    for (int i=1; i<=m; i++) {
        cin>>connect[i][0]>>connect[i][1];
        graph[connect[i][0]].push_back(connect[i][1]);
        graph[connect[i][1]].push_back(connect[i][0]);
    }
    
    solve(graph, window, n);
    
    return 0;
}

Here’s a working example: Ideone