COLRGRPH - Editorial

PROBLEM LINK:

Practice
Contest Division 3
Contest Division 2
Contest Division 1

Setter: Riley Borgard
Tester: Aryan Choudhary
Editorialist: Hriday G

DIFFICULTY

Easy-Medium

PREREQUISITES

Graphs

PROBLEM

There is a hidden undirected graph with n vertices. There are no self-loops or multiple edges. Each vertex is colored black or white, and the colors are also hidden from you. In one query you can ask for the colour of a node v. This will simultaneously flip the colours of each of its adjacent nodes. In at most 6000 queries, find the adjacency matrix of the graph.

QUICK EXPLANATION

Solve the problem for each subgraph consisting of the first i nodes. To solve the problem for the subraph with i+1 nodes, compare the parities of the degrees of each of the first i nodes and determine all the edges leaving the i+1-th node. Remove any overlap of queries and it should be enough to pass under the given constraints.

EXPLANATION

Suboptimal solution in 3 \cdot \binom{n}{2} queries

Consider two nodes u and v. Perform the queries — \displaystyle \mathrm{query}(v) \rightarrow \mathrm{query}(u) \rightarrow \mathrm{query}(v). If the colour of v returned by the first query is not the same as the one returned by the third query, then u must be adjacent to v, i.e. an edge exists between u and v.
This means that we have a way to check the existence of an edge in 3 queries. There are at most \binom{n}{2} distinct undirected edges that need to be checked. Hence in this manner we can find the adjacency matrix of the graph in 3 \cdot \binom{n}{2} queries. We can even do so using 2 queries per edge by choosing an order of edges such that what should be the third query of the i-th edge is also the first query of the i+1-th edge being queried. However this is still too many queries and will not work.

A solution which works in n + \binom{n}{2} queries

What else can we determine from the queries?
We can find the parity of the degree of a node v in n queries.

How?

\displaystyle \mathrm{query}(v) \rightarrow \forall (u \neq v) \, \mathrm{query}(u) \rightarrow \mathrm{query}(v).
For example, if v = n, \displaystyle [\mathrm{query}(n) \rightarrow \mathrm{query}(1) \rightarrow \mathrm{query}(2) \rightarrow \ldots \rightarrow \mathrm{query}(n-1) \rightarrow \mathrm{query}(n)].

If the answers to the first and last queries are the same, then there are an even number of nodes adjacent to v. In other words, v has an even degree. Otherwise, if the answers are different v has an odd degree.

Now assume we have already found the adjaceny matrix for a subgraph of the original graph, say the first k nodes. Then we can add the k+1-th node to it and find the new parity of the degree of each node i (1 \leq i \leq k).

Finding the parity of degree of each node

\displaystyle \mathrm{query}(1) \rightarrow \mathrm{query}(2) \rightarrow \ldots \rightarrow \mathrm{query}(k) \rightarrow \mathrm{query}(k+1) \rightarrow \mathrm{query}(1) \rightarrow \mathrm{query}(2) \rightarrow \ldots \rightarrow \mathrm{query}(k).

Each node i (1 \leq i \leq k) is queried twice and all nodes j (1 \leq j \leq k+1, \, j \neq i) are queried once each, in between. Compare the answers to the two queries to determine the new parity of i.

For each i, if this value does not match the parity of its degree before adding node k+1, it means that there must be an edge between i and k+1. In such a way, we can find all edges leaving node k+1 and subsequently the adjaceny matrix for the subgraph of the first k+1 nodes.

This would take \sum_{i=1}^n 2i - 1 = n^2 queries, which still exceeds the query limit.

If you write down the first few sets of queries, we can notice that there is a lot of overlap which we can avoid.

Click

Consider the case when n = 5
\begin{matrix} 1 & & & & & & & & \\ 1 & 2 & 1 & & & & & & \\ 1 & 2 & 3 & 1 & 2 & & & & \\ 1 & 2 & 3 & 4 & 1 & 2 & 3 & & \\ 1 & 2 & 3 & 4 & 5 & 1 & 2 & 3 & 4 \\ \end{matrix}

Removing repetitions, we get

Click

\begin{matrix} 1 & & & & & & & & \\ 1 & 2 & & & & & & & \\ 1 & 2 & 3 & & & & & & \\ 1 & 2 & 3 & 4 & & & & & \\ 1 & 2 & 3 & 4 & 5 & 1 & 2 & 3 & 4 \\ \end{matrix}

This would take n-1 + \sum_{i=1}^n i \leq n + \frac{n(n+1)}{2} queries, which is sufficient to pass all test cases under the given constraints.

Setter's Solution

#include <bits/stdc++.h>

using namespace std;

bool query(int v) {
    cout << "? " << v << endl;
    char c;
    cin >> c;
    return c == 'B';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<bool>> q(n + 1);
    vector<int> ve;
    ve.push_back(1);
    for(int i = 1; i <= n; i++) {
        ve.push_back(i);
    }
    for(int k : ve) {
        for(int i = k; i <= n; i++) {
            q[i].push_back(query(i));
        }
    }
    vector<vector<bool>> adj(n + 1, vector<bool>(n + 1));
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            adj[i][j] = adj[j][i] = (q[i][j - 1] ^ q[i][j + 1]);
        }
    }
    cout << "!\n";
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cout << adj[i][j];
        }
        cout << '\n';
    }
    cout << flush;
}
Tester's Solution
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
// #define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

vi readVectorInt(int n,lli l,lli r){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);

    const lli n=readIntLn(1,100);
    vector<vector<bool>> e(n,vector<bool>(n));
    vector<bool> col(n);
    auto query=[&](lli v){
        cout<<"? "<<v+1<<endl;
        auto s=readStringLn(1,1);
        assert(s=="B"||s=="W");
        col[v]=(s=="W");
        return col[v];
    };

    auto prt=[&](){
        cout<<"!"<<endl;
        for(auto &v:e){
            for(auto x:v)
                cout<<x;
            cout<<endl;
        }
        exit(0);
    };

    for(int i=n-1;i>=0;--i)
        query(i);
    vector<vector<bool>> cols;
    cols.pb(col);
    for(int i=0;i<n;++i){
        for(int j=n-1;j>=i;--j)
            query(j);
        cols.pb(col);
        query(i);
        const lli len=sz(cols);
        if(len<=2)
            continue;
        const auto &a=cols[len-3],&b=cols[len-1];
        for(int j=i;j<n;++j){
            if(a[j]==b[j])
                continue;
            e[i-1][j]=e[j][i-1]=1;
        }
    }
    prt();

    aryanc403();
    readEOF();
    return 0;
}

Feel free to share your approach. Suggestions are welcomed.

1 Like

I had a different approach. It is as follows:

Query for the adjacent nodes to node 1. This will be done in 3n queries
The order of the queries are : 1, i, 1. Note that it is important for i to be from 2 to n here.
You can see that after the ith node is queried, we have an odd number of 1s. Thus, for all the adjacent nodes to 1 you need to change their current color.

We have the current colors of each node, and note that after removing the 1s (which we can rightfully do so, since we have taken into consideration every 1), we have a sequence from 2, 3, 4, ..., n. If we ask for n - 1, we will get whether its color has changed because of n (in which case it is adjacent to n), or it hasn’t changed (thus, it isn’t adjacent).
Now, when we query n - 2, the change in color will depict the same information in the above paragraph (i.e it is adjacent to n or not)

Reason for this

Between the last n - 2 and this n - 2 query, we have queries n - 1 twice and n once. Querying the same thing twice will change its parity back to originally what it was…so effectively, we have queried n once.

The same thing works for n - 3, n - 42.
After this, we’ve got the adjacent nodes for nodes 1 and n. Now, we start from 2, and the process carries on until there is only a single node left, in which we don’t have to do anything. Querying like this will lead to n * (n + 1) / 2, and to sum that up with the queries used before this, it will lead to approximately 3 * n + \frac{n*(n+1)}{2} queries, which is a bit inefficient.

I also figured out a way to do 2 * n + \frac{n * (n + 1)}{2}, and that is just to remove the last 1 to get the adjacent nodes for 1, but was apparently too lazy to code it, since the above one passes with less effort.

Edit: My submission link: https://www.codechef.com/viewsolution/49179175

7 Likes

I used divide and conquer method to solve the problem. If we have n nodes then cut the graph into two halves. Left having first n/2 nodes and Right having (n-n/2) nodes. Get the graph of left and right half recursively. Then merge the left half and Right Half.

1 Like

how you merged two half ?

1 Like

how will you merge two halves?

Video Tutorial ?

2 Likes

How though, when you initially keep quering from 2 to n, it is possible that the colour of 2 is changed by some other number say 4 which is adjacent to 2. So we wont know the colour of 2 which you are storing initially. Can you please explain again. Thank you

Yes it will be, but once we are querying backwards (from n - 1 to 2), then for any node i, all the nodes from i + 1, i + 2 ... n - 1 will be queried twice between the queries in which we obtain the color of node i, thus effectively bringing the same color back regardless of the node being adjacent.
Twice because first time it will be done while querying 2, 3, 4, .. n, and the next time it will be done backwards (except n, which is queried only once)

Nice!! Thanks

1 Like

Suppose we have nodes {1,2,3,4,5,6} currently. So in the left half we have nodes { 1,2,3} and in the right half we have nodes {4,5,6}.

So we call recursively for nodes {1,2,3} and nodes {4,5,6} and get their graphs.

Now we need to merge these 2 graphs and get edges between nodes {1,2,3} and nodes {4,5,6}

First we query the colors of nodes 1,2 and 3. So we have their colors now.
Now query node 4, then query node 1,2,3 again. If the color of any node is changed then we say there is a edge between these two. Say the color of node 1 was “W” then after we query node “4” the color of node 1 became “B”. So there is an edge between node 1 and 4.
Similarly query node 5 , then query node 1,2,3 to determine the edges.
Finally query node 6 and then 1,2,3.

Link to my code:
https://pastebin.ubuntu.com/p/TtKsvq6jby/

can anyone pls help me to figure out the why my code is giving WA? I exactly followed the editorial.

my code

Thanks in Advance.