ROOKPATH - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Ildar Gainullin
Tester: Nikolay Budin
Editorialist: Alei Reyes

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Eulerian Paths

PROBLEM:

There are m tiles in different cells of a n \times n chessboard.

Your goal is to start a rook in any of the given tiles and move it m-1 times (as it is a rook, you can only move it to any other cell on the same row or column), visiting all given tiles, and alternating the type of the used move (so you can’t move the rook to some cell in the same row two times in a row and you can’t move the rook to some cell in the same column two times in a row).

QUICK EXPLANATION:

Construct bipartite graph where Left represents the rows and Right the columns.
For each tile at cell (r,c), add an edge connecting vertex r from left to vertex c from right.
An eulerian path in such graph gives the order in which the cells can be visited.

EXPLANATION:

Finding a hamiltonian path in a general graph is NP-complete. Instead of thinking on how to go through all cells, sometimes is useful to find a graph where we have to go through all edges, which is a problem that can be solved in linear time (Eulerian Path ).

The structure of rows and columns in a chessboard can be represented very naturally by a bipartite graph.

Let’s construct an undirected bipartite graph G where Left represent the rows and Right the columns.
A tile at position (r,c) can be represented as an edge that connects r from Left to c from right.

If we follow a path in G, adjacent edges represent cells that can be reached by a rook because they share either a row or a column.

However a rook has two types of moves (horizontal and vertical), and we are interested in moving a rook from tile to tile by alternating the type of move.
It turns out that the bipartiteness of the graph also allows to model the two types of move. We can go through tile (r,c) by moving in the graph in two different ways:

  • r \rightarrow c, it means we moved towards (r,c) using a horizontal move. After visiting the tile we have to move using a vertical move i.e to a different row using an edge c \rightarrow r'
  • c \rightarrow r, it means we moved towards (r,c) using a vertical move. After visiting the tile we have to move using a horizontal move i.e to a different column using an edge r \rightarrow c'.

Therefore the problem is reduced to find a path that visits all edges of the graph exactly once i.e an eulerian path.

board

The following picture depicts the bipartite graph of the above board distribution. Each pawn represents a tile. If you start from node c and follow the arrows, you will walk through an eulerian path.

bipartite

SOLUTIONS:

Setter's Solution
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector <int> dsu(n + n);
    vector <int> deg(n + n);
    vector <int> empt(n + n);
    for (int i= 0; i < n + n; i++) dsu[i] = i;
    function<int(int)> get = [&] (int v) {
      if (v == dsu[v]) return v;
      else return dsu[v] = get(dsu[v]);
    };
    function<void(int,int)> uni = [&] (int u, int v) {
      dsu[get(u)] = get(v);
    };
    vector <vector <pair <int, int> > > g(2 * n);
    vector <char> used_e(m);
    map <pair <int, int>, int> id;
    for (int i = 0; i < m; i++) {
      int r, c;
      cin >> r >> c;
      r--, c--;
      empt[r]++, empt[n + c]++;
      id[{r, n + c}] = i;
      id[{n + c, r}] = i;
      g[r].push_back({n + c, i});
      g[n + c].push_back({r, i});
      deg[r] ^= 1, deg[c + n] ^= 1;
      uni(r, c + n);
    }
    bool bad = false;
    int cnt = 0;
    int start = 0;
    set <int> ok;
    for (int i = 0; i < n + n; i++) {
      if (!empt[i]) continue;
      ok.insert(get(i));
      if (deg[i]) cnt++;
      if (deg[i]) start = i;
    }
    if (bad || cnt > 2 || ok.size() > 1) assert(0);
    else {
      vector <int> ans;
      function<void(int)> dfs = [&] (int v) {
        while (!g[v].empty()) {
          int i = g[v].back().second;
          int to = g[v].back().first;
          g[v].pop_back();
          if (!used_e[i]) {
            used_e[i] = true;
            dfs(to);
          }
        }
        ans.push_back(v);
      };
      dfs(start);
      vector <int> p;
      for (int i = 1; i < (int) ans.size(); i++) {
        p.push_back(id[{ans[i - 1], ans[i]}]);
      }
      for (int i : p) {
        cout << i + 1 << ' ';
      }
      cout << '\n';
    }
  }
}
Tester's Solution
void solve() {
  int n, m;
  cin >> n >> m;
  map<pii, int> inds;
  vector<vector<pii>> graph;
  auto get_ind = [&](pii p) {
    if (!inds.count(p)) {
      int tmp = szof(inds);
      inds[p] = tmp;
      graph.push_back({});
    }
    return inds[p];
  };

  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    int a = get_ind({x, 1});
    int b = get_ind({y, 2});

    graph[a].push_back({b, i});
    graph[b].push_back({a, i});
  }

  vector<int> odd;
  for (int i = 0; i < szof(graph); ++i) {
    if (szof(graph[i]) % 2) {
      odd.push_back(i);
    }
  }

  if (szof(odd) == 2) {
    int a = odd[0];
    int b = odd[1];
    graph[a].push_back({b, m});
    graph[b].push_back({a, m});
    ++m;
  }

  vector<bool> used(m);
  vector<int> vcnt(szof(graph));

  vector<int> cycle;

  function<void(int)> dfs = [&](int v) {
    while (vcnt[v] < szof(graph[v])) {
      auto to = graph[v][vcnt[v]];
      ++vcnt[v];
      if (!used[to.ss]) {
        used[to.ss] = true;
        dfs(to.ff);
        cycle.push_back(to.ss);
      }
    }
  };

  dfs(0);

  if (szof(odd) == 2) {
    rotate(cycle.begin(), find(cycle.begin(), cycle.end(), m - 1), cycle.end());
    cycle.erase(cycle.begin());
  }

  for (int ind : cycle) {
    cout << ind + 1 << " ";
  }
  cout << "\n";
}

VIDEO EDITORIAL:

3 Likes

The problem says solution is always possible. Can you please specify the path when there are only 2 marks in different row and column (r1 =/= r2 && c1 =/= c2)?

1 Like

@amurto The problem says the solution is always possible satisfying the inputs given by the admin.
Those input are not valid for this problem

1 Like

How do we understand that for a given input ,this tour is not possible?

Can someone explain the path possible for 3*3 board of a rook, I ran the solution path but in that path rook is literally flying anywhere like the solution was 2 1 7 3 9 8 5 4 6 -> here i don’t understand how the rook goes from 7 to 3 or from 4 to 6 when 5 is already visited… I know I am wrong somewhere I understanding the question can someone help.

@Nikolay Budin Kindly include the template in your code otherwise how shall one understand what does “pii” mean?

For the Euler path traversal, which algo has been used?

I don’t remember the name of the algorithm. It is based in that if every vertex has even degree, then there is a cycle, if you remove that cycle from the graph we’ll get again a graph where all vertices have even degree, so you can repeat recursively. At the end you just have to glue the cycles to get an eulerian path.

1 Like

pii means pair<int,int>. I removed the template because it is long and doesn’t add anything meaningful.

Is the time limit too strict for java solutions? I don’t see any accepted ( 100pts ) Java solution. Also, my submission which is implementation of the editorial gives TLE on the last case.

cc @alei

Can you kindly provide some resource where I can find this algo?

Constraints looks fine, even java should AC this problem

https://cp-algorithms.com/graph/euler_path.html

1 Like

If anyone is facing difficulty in understanding the solution of ROOKPATH,then you can read the following explanation in easy language :

Problem - Given a Chessboard of N x N with M marked cells in it. A rook(elephant in chess) is placed at one of the marked cells.Move the rook in such a way that it goes to every marked cell once. Rook cannot move more than once in a row/column , in other words ,rook has to move in
a zig-zag manner (first he will move in a row(or column) , then in a column(or row) and so on)

Output - Print a path in which rook will visit all marked cells(only once).

It is a graph problem because a path has to be made.Rook is going from one
point to another.It can be somewhere related to DFS because in DFS we go
from one point to the another and so on.
Solutions-

METHOD 1(For 15 points):

Bruteforce method - As you don’t know how to choose the marked cell from
which the rook will start the path,Run a DFS from every marked cell(node) and
stop the process when you find a marked cell which leads to a path in which all the marked cells are visited once and
print the path.

Considering nodes as the ‘marked cells’ and edges are the ‘rows and columns’.

for example , take two marked cells as (1,1) and (3,1)
In this example, first node is (1,1) and second node is (3,1) and
connecting edge between these two nodes is 1st column.

Time complexity of the Bruteforce approach:

For 100 points

  • no. of marked cells * O(nodes + edges)
  • no. of marked cells * O(no. of marked cells + edges)
  • 50000 * (50000 + rows + columns)
  • 50000 * (50000 + 2 * N)
  • 50000 * (50000 + 2 * 50000)
  • 50000 * (50000 + 100000)
  • 50000 * 150000
  • 7.5* 10^9
  • > 1 sec (Time limit of the problem)
  • TLE for 100 points

for 10 points

  • 15 * (15 + 2*50000)
  • 15 * 100015
  • 1.5 * 10^6
  • < 1sec
  • AC for 10 points

METHOD 2 (efficient approach - 100 points):

In order to make the solution time-efficient , instead of checking every marked cell which will lead to the full path , we must know before-hand which marked cell will lead to the full path. As the rook is only allowed to move in a zig-zag manner (first he will move in a row(or column) , then in a column(or row) and so on) ,
You can relate it with bi-partite graphs , as it is also designed in a manner
that the edge will connect from partition 1 to partition 2 and vice-versa as well.

Like this:  

Rows     Columns
1          5
2          6
3          7
4          8

Second thing is that the rook can only visit a marked cell once.This can be related to ‘eulerian path’. Eulerian path is a path in graph that visits every “edge” exactly once.

It means that our marked cell will represented as an ‘edge’ and node will represented as rows and columns.

for example , take a marked cell as (1,3).
In this example, first node is 1 (node in Partition-1 of bi-partite graph) and second node is 3 (node in Partition-2 of bi-partite graph) and
connecting edge between these two nodes is (1,3) , which will be represented as a single number in the implementation.

Now coming to the point how will we chose the marked cell from where we will start our DFS.

CASE:1
If degree of all the nodes in the bi-partite graph are even , then you can randomly take any marked cell(node)
and start the DFS and you will get your full path.

CASE:2
If exactly two nodes have odd degree , then you will choose the node(marked cell) out of these 2 nodes and 
run the DFS and you will get your full path.

Degree of a node means the no. of edges connected to that node.

Time complexity of the Efficient approach (For 100 points) -

  • 1 * O(nodes + edges)
  • 1 * O(no. of marked cells + edges)
  • 1 * (50000 + rows + columns)
  • 1 * (50000 + 2*N)
  • 1 * (50000 + 2*50000)
  • 1 * (50000 + 100000)
  • 1 * 150000
  • 1.5 * 10^5
  • < 1 sec (Time limit of the problem)
  • AC for 100 points

Implementation:
This is my well-commented code - Click Here

4 Likes

Implementation is also added!

2 Likes

How did you know so much??It’s awesomee

1 Like

@alei Sorry to disturb you, I would like to know the deficiency of the following approach

  1. Construct the bipartite graph as instructed by you.
  2. Run dfs from each vertex and check whether that visits all the vertices in the graph.If so, we have found an eulerian tour.

Do you find any deficiency in this approach? I am getting wrong ans…
Thanks in advance…

1 Like

dfs always visits all vertices of a connected graph. We are interested in visitng all edges exactly once (is possible to visit any vertex multiple times).
Maybe this helps:

Thanks for your concern.

Thanks Brother!
Before solving this problem i haven’t solve any problem based on eulerian path and bipartite graph.

When i read the editorial and also watched video editorial , i couldn’t understand the approach.But then i tried to dry run the problem on pen and paper for so long and then i actually got to understand the solution.

Therefore i thought that i should write a beginner friendly explanation for those people who are still confused after reading the editorial.