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.