PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Jay Sharma
Tester: Nishank Suresh
Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
Observation, DFS
PROBLEM
You are given a tree having N nodes. Each node of this tree is colored either Black or White but you don’t know the initial color of any node.
You can ask up to Q queries. In each query, you will give a node to the grader. The grader will flip the color of this node and then return the number of edges in the tree connecting nodes of different colors. Note that the flipping of color is permanent, meaning that the color of the node remains flipped after the query.
Your task is to make the color of all nodes the same.
QUICK EXPLANATION
- Root the tree at any node, and for each node, attempt to find out whether it has the same color as its parent node or not.
- Let’s assume we have already calculated this information for all children of the current node, and we aim to compute it for the current node.
- Make a query at the current node. Assuming the answer to the previous query was P and the answer to the current query is Q, and there are A children with the same color as the current node, and B nodes with the opposite color as the current node, then we can calculate w = (Q-P+A-B+1)/2, and determine if it has the same color as its parent or not, by checking if w = 0 or w = 1.
- After computing this information, one of the colors must have up to \left\lfloor \frac{N}{2} \right\rfloor nodes with that color. We can compute this via DFS, and flip the color of those nodes.
EXPLANATION
First of all, since there’s no way to identify the actual color or node by any query, we shall assume the color of one node, and determine the color with respect to the color of that node.
Let’s assume node 1 is the root and is colored white. Apart from node 1, we need to determine whether node u as same or opposite color as the parent of node u. Let’s denote parent of node u as P_u. Also, denote S_u = 0 if node u has same color as it’s parent, otherwise S_u = 1.
Computing S_u for leaf nodes u
Let’s try computing S_u for leaf node u. If we consider the answer to the previous and current queries, the only pairs changed are related to node u. Let’s assume P denotes the answer to the previous query, and C is the answer to the current query after the color of node u is flipped. Only two situations are possible.
- C = P+1: In this case, a new pair with opposite colors got created, which means, currently, node u has opposite color as node P_u, which implies S_u = 1.
- C = P-1: In this case, an existing pair with opposite colors got removed, which means, currently, node u has same color as node P_u, which implies S_u = 0.
Computing S_u for non-leaf nodes u
Generalizing the above approach, now we also need to consider children of node u as well. Let’s assume we are computing it in a bottom-up manner, where S_v is already computed for all children of node u.
When we make a query for node u, S_v gets flipped for all immediate children v of node u, as the color of u got changed. We need to maintain S_u for current colors.
Let’s say we have made a query for node u, and C is the response to a query to the current query and P is a response to the previous query.
Let’s assume there are a children of u with the same color and b nodes with opposite color after the flipping color of the current node.
Let’s assume D denotes the number of pairs of opposite-colored nodes, with no endpoint in pair being node u.
P = D + (1-S_u) + a
C = D + S_u + b
Subtracting these, we can obtain S_u = (C - P + a - b +1)/2. This is enough to determine whether node u has same or opposite color as P_u using just 1 query.
It took N-1 queries for each non-root nodes, but we also need number of pairs before first query, so, we need to make 1 additional query. Hence, we used up exactly N queries and we know for each node whether it has same color as its parent or not.
By running a DFS, we can determine color of each node wrt color root node. One of the color is guaranteed to have \leq N/2 nodes of that color, so once we find colors, we can flip colors of those nodes, taking at most N/2 operations.
Hence, we took at most 3*N/2 operations.
TIME COMPLEXITY
The time complexity is O(N) per test case.
SOLUTIONS
Setter's Solution
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
void dfs1(vector<int> adj[],int parent[],int u)
{
for(int i=0;i<(int)adj[u].size();i++)
{
int v=adj[u][i];
if(v!=parent[u])
{
parent[v]=u;
dfs1(adj,parent,v);
}
}
}
void dfs2(vector<int> adj[],int parent[],int diff[],int u,int &prev)
{
int x=0,y=0;
for(int i=0;i<(int)adj[u].size();i++)
{
int v=adj[u][i];
if(v!=parent[u])
{
dfs2(adj,parent,diff,v,prev);
if(diff[v])
y++;
else
x++;
}
}
if(u!=0)
{
cout << u+1 << endl;
int next;
cin >> next;
int w=(prev-next+x-y+1)/2;
diff[u]=1-w;
for(int i=0;i<(int)adj[u].size();i++)
{
int v=adj[u][i];
if(v!=parent[u])
diff[v]=1-diff[v];
}
prev=next;
}
}
void dfs3(vector<int> adj[],int parent[],int diff[],int c[],int u)
{
for(int i=0;i<(int)adj[u].size();i++)
{
int v=adj[u][i];
if(v!=parent[u])
{
c[v]=c[u]^diff[v];
dfs3(adj,parent,diff,c,v);
}
}
}
int main()
{
int tc=1;
cin >> tc;
while(tc--)
{
int n,q;
cin >> n >> q;
vector<int> adj[n];
int parent[n];
for(int i=1;i<n;i++)
{
int u,v;
cin >> u >> v;
u--,v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
parent[0]=0;
dfs1(adj,parent,0);
int diff[n];
cout << 1 << endl;
int prev;
cin >> prev;
dfs2(adj,parent,diff,0,prev);
int c[n];
c[0]=1;
dfs3(adj,parent,diff,c,0);
int white=0,black=0;
for(int i=0;i<n;i++)
{
if(c[i]==1)
white++;
else
black++;
}
int less;
if(black<white)
less=0;
else
less=1;
for(int i=0;i<n;i++)
{
if(c[i]==less)
{
cout << i+1 << endl;
int v;
cin >> v;
}
}
cout << 0 << endl;
int result;
cin >> result;
assert(result==1);
}
return 0;
}
Tester's Solution
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
auto solve = [&] () {
int n, q; cin >> n >> q;
vector<vector<int>> tree(n+1);
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
auto query = [&] (int u) {
cout << u << endl;
int res; cin >> res;
if (res == -1) exit(0);
return res;
};
int ans = query(1), samect = 0;
vector<int> change(n+1), col(n+1);
auto dfs = [&] (const auto &self, int u, int p) -> int {
int diff = 0, children = 0;
for (int v : tree[u]) {
if (v == p) continue;
int add = self(self, v, u);
diff += add;
++children;
}
if (u == 1) return 0;
int cur = query(u);
for (int v : tree[u]) {
if (v != p)
change[v] ^= 1;
}
int x = (ans + children - 2*diff + 1 - cur)/2;
ans = cur;
return change[u] = 1 - x;
};
auto dfs2 = [&] (const auto &self, int u, int p) -> void {
samect += col[u] == 0;
for (int v : tree[u]) {
if (v == p) continue;
col[v] = change[v] ^ col[u];
self(self, v, u);
}
};
dfs(dfs, 1, 0);
dfs2(dfs2, 1, 0);
int which = samect > n - samect;
for (int i = 1; i <= n; ++i) {
if (col[i] == which)
query(i);
}
query(0);
};
int t; cin >> t;
for (int test = 1; test <= t; ++test) {
solve();
}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class INTREENCLR{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), Q = ni();
int[] from = new int[N-1], to = new int[N-1];
for(int i = 0; i< N-1; i++){
from[i] = ni()-1;
to[i] = ni()-1;
}
int[][] tree = tree(N, from, to);
boolean[] same = new boolean[N];
//same[i] denotes whether node i has same color as its parent or not
query(0);
dfs(tree, same, 0, -1);
int[] col = new int[N];
color(tree, col, same, 0, -1);
int[] cnt = new int[2];
for(int i = 0; i< N; i++)cnt[col[i]]++;
int flip = cnt[0] < cnt[1]?0:1;
for(int i = 0; i< N; i++)if(col[i] == flip)query(i);
pni(0);
hold(ni() == 1);
}
void color(int[][] tree, int[] col, boolean[] same, int u, int p){
for(int v:tree[u]){
if(v == p)continue;
col[v] = same[v]?col[u]:(1-col[u]);
color(tree, col, same, v, u);
}
}
long prevQuery = -1, curQuery = -1;
void dfs(int[][] tree, boolean[] sameColor, int u, int p) throws Exception{
for(int v:tree[u])if(v != p)dfs(tree, sameColor, v, u);
if(p == -1)return;
query(u);
int same = 0, diff = 0;
for(int v:tree[u]){
if(v == p)continue;
sameColor[v] = !sameColor[v];
// Since after query on u, color of u is flipped
if(sameColor[v])same++;
else diff++;
}
long w = (curQuery - prevQuery + same - diff +1)/2;
sameColor[u] = w == 0;
}
void query(int u) throws Exception{
pni(1+u);
prevQuery = curQuery;
curQuery = nl();
hold(curQuery != -1);
}
//creates adjacency list representation using jagged arrays in java, faster than array of lists
int[][] tree(int N, int[] from, int[] to){
int[][] g = new int[N][];
int[] c = new int[N];
for(int x:from)c[x]++;
for(int x:to)c[x]++;
for(int i = 0; i< N; i++)g[i] = new int[c[i]];
for(int i = 0; i< N-1; i++){
g[from[i]][--c[from[i]]] = to[i];
g[to[i]][--c[to[i]]] = from[i];
}
return g;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new INTREENCLR().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 