City Grid - Editorial

Problem Link

E_CODENITE24

Author: aryansanghi

Solution

Consider a path that has been taken. Suppose the person is at a previously unvisited point p currently. An edge is called good if it’s mirror either doesn’t exist or has been visited already, i.e. for edge ((a_1, b_1), (a_2, b_2)), the edge ((a_1, b_1), (2\times a_1-a_2, 2 \times b_1-b_2)) is either not present or already travelled along. Else, the edge is bad

Observations

  1. A person can’t travel along a bad edge. It is because if he travels along it, its mirror edge can’t be travelled anytime in the future as it is not allowed to visit a vertex more than once and edges can’t be travelled along more than once.
  2. There can only be exactly one good edge. If there are no good edges, the person can’t move anywhere as observed. If there is more than one good edge, the person can’t move along the other good edge anytime after because of the same reasons.
  3. There are exactly two odd degree vertices, one where the path starts and one where it ends. It’s because for every other vertex, the person enters it once and leaves it once when visiting it and every other time he adds two edges to it as he enters and immediately leaves it.
  4. If the person goes to a visited vertex, he can’t change directions and needs to keep moving along the same direction.

Algorithm

  1. Start at the lexicographically minimum point with an odd degree.
  2. If the current vertex is not visited, find the number of good edges. If the value is more than one or is equal to zero, then stop and start from the other odd degree vertex. Else, move along the good edge.
  3. If the current vertex is visited, then check if it is possible to move along the direction he was moving along when he visited the vertex. If yes, move along it. Else, start from the other odd degree vertex.

Code

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long

void solve() {
    int n, m; cin >> n >> m;
    vector<vector<vector<pair<int, int>>>> adj(n, vector<vector<pair<int,int>>> (n)), adj2;

    for(int i = 0; i < m; ++i) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        a--; b--; c--; d--;
        adj[a][b].push_back({c, d});
        adj[c][d].push_back({a, b});
    }

    vector<pair<int, int>> starts;
    for(int i = 0; i < n; ++i) 
        for(int j = 0; j < n; ++j) {
            sort(adj[i][j].begin(), adj[i][j].end());
            if(adj[i][j].size() % 2) starts.push_back({i, j});
        }
    adj2 = adj;

    assert(starts.size() == 2);

    auto isMirror = [](vector<pair<int, int>> &x, pair<int, int> from, pair<int, int> to) {
        int dx = to.first - from.first;
        int dy = to.second - from.second;
        pair<int, int> mirror = {from.first - dx, from.second - dy};
        return binary_search(x.begin(), x.end(), mirror);
    };

    pair<int, int> curr = starts.front(), last = {-1, -1};
    vector<vector<bool>> vis(n, vector<bool> (n, false));
    vector<pair<int, int>> path;
    int ne = m;

    while(curr != starts.back()) {
        auto [x, y] = curr;
        if(vis[x][y]) {
            pair<int, int> temp = {2*x - last.first, 2*y - last.second};
            if(binary_search(adj[x][y].begin(), adj[x][y].end(), temp)) {
                last = curr; 
                curr = temp;
                ne--;
            } else {
                path.clear();
                break;
            }
        } else {
            path.push_back(curr);
            vis[x][y] = true;

            if(last != make_pair(-1LL, -1LL)) adj[x][y].erase(find(adj[x][y].begin(), adj[x][y].end(), last));
            int cnt = 0;
            pair<int, int> edg;
            for(auto ed : adj[x][y]) {
                if(!isMirror(adj[x][y], {x, y}, ed)) {
                    cnt++;
                    edg = ed;
                }
            }

            if(cnt == 1) {
                last = curr;
                curr = edg;
                ne--;
            } else {
                path.clear();
                break;
            }
        }
    }

    if(path.size()&&!ne) {
        cout << path.size() + 1<< endl;
        for(auto [x, y] : path) cout << x+1 << " " << y+1 << endl;
        cout << starts.back().first + 1 << ' ' << starts.back().second + 1 << endl;
        return;
    }
    
    path.clear();
    curr = starts.back(), last = {-1, -1};
    vis.assign(n, vector<bool> (n, false));
    ne = m;

    while(curr != starts.front()) {
        auto [x, y] = curr;
        if(vis[x][y]) {
            pair<int, int> temp = {2*x - last.first, 2*y - last.second};
            if(binary_search(adj2[x][y].begin(), adj2[x][y].end(), temp)) {
                last = curr; 
                curr = temp;
                ne--;
            } else {
                cerr << "Error" << endl;
                exit(0);
            }
        } else {
            path.push_back(curr);
            vis[x][y] = true;

            if(last != make_pair(-1LL, -1LL)) adj2[x][y].erase(find(adj2[x][y].begin(), adj2[x][y].end(), last));
            int cnt = 0;
            pair<int, int> edg;
            for(auto ed : adj2[x][y]) {
                if(!isMirror(adj2[x][y], {x, y}, ed)) {
                    cnt++;
                    edg = ed;
                }
            }

            if(cnt == 1) {
                last = curr;
                curr = edg;
                ne--;
            } else {
                cerr << "Error" << endl;
                exit(0);
            }
        }
    }

    if(path.size()&&!ne) {
        cout << path.size() + 1 << endl;
        for(auto [x, y] : path) cout << x+1 << " " << y+1 << endl;
        cout << starts.front().first + 1 << ' ' << starts.front().second + 1 << endl;
        return;
    }

    cerr << "none found" << endl;
    exit(0);
}

int32_t main() {
    int _TC = 0; cin >> _TC;
    for(int _ct = 1; _ct <= _TC; ++_ct) {
        solve(); cout<<endl;
    }
}