[A](https://mirror.codeforces.com/gym/105137/problem/A)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
↵
↵
<spoiler summary="solution">↵
↵
The optimal way to hit $ n $ runs in minimum balls is to hit $ 6 $ runs on every ball until you reach $ n $ runs. ↵
The optimal way to hit $ n $ runs in maximum balls is to hit $ 4 $ runs on every ball until you reach $ n $ runs. ↵
Time Complexity: $ O(1) $.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
int n;↵
cin>>n;↵
cout<<((n+5)/6)<<" "<<((n+3)/4)<<"\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
[B](https://mirror.codeforces.com/gym/105137/problem/B)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
↵
<spoiler summary="solution">↵
↵
From the definition of the Good string it clearly seems that string must contain either all 0’s or 1’s.↵
↵
So all 0’s are converted into 1’s in the following ways:↵
↵
1. Using Operation 1 by using $ a $ coins per operation.↵
↵
2. Using Operation 2 by using $ b $ coins per operation by using any extra '1' in the string.↵
↵
All 1’s are converted into 0’s in the following ways:↵
↵
1. Using Operation 1 by using $ a $ coins per operation.↵
↵
2. Using Operation 2 for pair of 1’s using $ b $ coins per operation. If there is single '1' left this can be converted to '0' by either using $ a $ coins or $ 2b $ coins.↵
↵
The minimum coins will get in one of the above scenarios.↵
Time Complexity: $ O(n) $.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
int n,a,b;↵
cin>>n>>a>>b;↵
string s;↵
cin>>s;↵
int cnt0=count(s.begin(),s.end(),'0');↵
int cnt1=n-cnt0;↵
int ans1=a*cnt0;↵
int ans2=b*cnt0;↵
int ans3=a*cnt1;↵
int ans4=((cnt1/2)*b+(cnt1%2)*(min(a,2*b)));↵
cout<<min({ans1,ans2,ans3,ans4})<<"\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[C](https://mirror.codeforces.com/gym/105137/problem/C)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
<spoiler summary="solution">↵
↵
The lower bound of $ F(p) $ will be $ \log_2(n) + 1 $.↵
↵
Mathematically,↵
Let's consider $ \sum \frac{p_i}{i} \geq \log_2(n) + 1 $ (ans).↵
↵
Let $ 2^x \leq n \leq 2^{x+1} $,↵
$ m = 2^{x+1} $.↵
↵
Array $ b = p $.↵
$ \left\lfloor \frac{p_m}{m} \right\rfloor \geq \left\lfloor \frac{2^{x+1}}{m} \right\rfloor = \left\lfloor \frac{(2^x+2^x)}{m} \right\rfloor \geq \left\lfloor \frac{(b_m+m)}{m} \right\rfloor $.↵
↵
So $ \sum \frac{p_i}{i} \geq \sum \frac{(b_i+i)}{i} = \sum \frac{(p_i+i)}{i} = \sum \frac{p_i}{i} + 1 \geq \text{ans} + 1 $.↵
↵
Hence showed that lower bound will be limited to $ \log_2(n) + 1 $.↵
↵
So construct the permutation accordingly.↵
↵
Time Complexity: $ O(n+\log n) $.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
int n;↵
cin>>n;↵
vector<int> a(n+1);↵
for(int i=1;i<=n;i++) a[i]=i-1;↵
int p=n;↵
while(p!=0){↵
int x=p/2;↵
x++;↵
swap(a[x],p);↵
}↵
for(int i=1;i<=n;i++) cout<<a[i]<<" ";↵
cout<<endl;↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[D](https://mirror.codeforces.com/gym/105137/problem/D)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
↵
<spoiler summary="solution">↵
↵
From the given queries we only know the information about number of zeroes and ones in the hidden string but how we can get to know the positions of ‘01’ and ‘10’ (Binary Search it!)↵
↵
Just know the first character by asking queries like 000…n times and 1000…(n-1) times.↵
↵
Later do the binary search to know the first occurrence of the character other than first character, similarly, do the binary search for another substring position.↵
↵
Total queries used are $ 2\log(n) + 2 < 40 $.↵
↵
Time Complexity: $ O(n\log n) $.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
//t=1;↵
while(t--){↵
int n;↵
cin>>n;↵
string s="";↵
for(int i=0;i<n;i++) s+='0';↵
int cnt0,cnt1;↵
cout<<"? "<<s<<endl;↵
cin>>cnt0;↵
cnt1=n-cnt0;↵
if(cnt0==n || cnt0==0) cout<<"! -1 -1"<<endl;↵
else{↵
int pos1=-1,pos2=-1;↵
s[0]='1';↵
int x;↵
cout<<"? "<<s<<endl;↵
cin>>x;↵
if(x<cnt0){↵
pos1=0;↵
int l=pos1,r=n-1;↵
while(l<=r){↵
int m=(l+r)/2;↵
string s1="";↵
for(int i=0;i<=m;i++) s1+='1';↵
for(int i=m+1;i<n;i++) s1+='0';↵
cout<<"? "<<s1<<endl;↵
cin>>x;↵
if(x==(cnt0-(m+1))){↵
pos1=m;↵
l=m+1;↵
}↵
else r=m-1;↵
}↵
if((pos1+1)==cnt0) cout<<"! "<<pos1+1<<" "<<"-1"<<endl;↵
else{↵
pos2=pos1+1;↵
l=pos2,r=n-1;↵
while(l<=r){↵
int m=(l+r)/2;↵
string s1="";↵
for(int i=0;i<=m;i++) s1+='1';↵
for(int i=m+1;i<n;i++) s1+='0';↵
cout<<"? "<<s1<<endl;↵
cin>>x;↵
x+=pos1+1;↵
if(x==(cnt0+(m-pos1))){↵
pos2=m;↵
l=m+1;↵
}↵
else r=m-1;↵
}↵
cout<<"! "<<pos1+1<<" "<<pos2+1<<endl;↵
}↵
}↵
else{↵
pos2=0;↵
int l=pos2,r=n-1;↵
while(l<=r){↵
int m=(l+r)/2;↵
string s1="";↵
for(int i=0;i<=m;i++) s1+='1';↵
for(int i=m+1;i<n;i++) s1+='0';↵
cout<<"? "<<s1<<endl;↵
cin>>x;↵
if(x==(cnt0+(m+1))){↵
pos2=m;↵
l=m+1;↵
}↵
else r=m-1;↵
}↵
if((pos2+1)==cnt1) cout<<"! -1"<<" "<<pos2+1<<endl;↵
else{↵
pos1=pos2+1;↵
l=pos1,r=n-1;↵
while(l<=r){↵
int m=(l+r)/2;↵
string s1="";↵
for(int i=0;i<=m;i++) s1+='1';↵
for(int i=m+1;i<n;i++) s1+='0';↵
cout<<"? "<<s1<<endl;↵
cin>>x;↵
x-=(pos2+1);↵
if(x==(cnt0-(m-pos2))){↵
pos1=m;↵
l=m+1;↵
}↵
else r=m-1;↵
}↵
cout<<"! "<<pos1+1<<" "<<pos2+1<<endl;↵
}↵
}↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
[E](https://mirror.codeforces.com/gym/105137/problem/E)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
<spoiler summary="solution">↵
↵
In this problem we need to find the highest ancestor of the node which is empty.↵
↵
We can do Binary Lifting, HLD etc., Time limit given to get accept any solution.↵
↵
Time Complexity: $O(nlogn)$ (Binary Lifting)↵
↵
Time Complexity: $O(nlog^2 n)$ (HLD)↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int n,m;↵
vector<vector<int>> adj;↵
vector<int> H,pH,tree,pos,horder,sz,par;↵
↵
int getsum(int qs, int qe, int ss, int se, int si){↵
if(se<qs || ss>qe) return 0;↵
if(qs<=ss && qe>=se) return tree[si];↵
int mid=(ss+se)/2;↵
int v1=getsum(qs,qe,ss,mid,2*si+1);↵
int v2=getsum(qs,qe,mid+1,se,2*si+2);↵
return v1+v2;↵
}↵
↵
void update(int ss, int se, int i, int si, int diff){↵
if(i<ss || i>se) return;↵
tree[si]=tree[si]+diff;↵
if(se>ss){↵
int mid=(ss+se)/2;↵
update(ss,mid,i,2*si+1,diff);↵
update(mid+1,se,i,2*si+2,diff);↵
}↵
}↵
↵
void dfs(int x, int p){↵
sz[x]=1;↵
par[x]=p;↵
int pp=-1,maxi=0;↵
for(auto i:adj[x]){↵
if(i!=p){↵
dfs(i,x);↵
sz[x]+=sz[i];↵
if(sz[i]>maxi){↵
maxi=sz[i];↵
pp=i;↵
}↵
}↵
}↵
if(pp!=-1){↵
H[pp]=x;↵
}↵
}↵
↵
void dfs1(int x, int p){↵
if(H[x]==p) pH[x]=pH[p];↵
for(auto i:adj[x]){↵
if(i!=p){↵
dfs1(i,x);↵
}↵
}↵
}↵
↵
void dfs2(int x, int p){↵
horder.push_back(x);↵
for(auto i:adj[x]){↵
if(i!=p){↵
if(H[i]==x) dfs2(i,x);↵
}↵
}↵
for(auto i:adj[x]){↵
if(i!=p){↵
if(H[i]!=x) dfs2(i,x);↵
}↵
}↵
}↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
cin>>n>>m;↵
adj.clear();↵
adj.resize(n);↵
for(int i=0;i<n-1;i++){↵
int u,v;↵
cin>>u>>v;↵
u--;↵
v--;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
H.clear();↵
H.resize(n);↵
for(int i=0;i<n;i++) H[i]=i;↵
pH.clear();↵
pH.resize(n);↵
for(int i=0;i<n;i++) pH[i]=i;↵
tree.clear();↵
tree.resize(4*n,0);↵
pos.clear();↵
pos.resize(n);↵
sz.clear();↵
sz.resize(n);↵
par.clear();↵
par.resize(n);↵
horder.clear();↵
dfs(0,-1);↵
dfs1(0,-1);↵
dfs2(0,-1);↵
for(int i=0;i<n;i++) pos[horder[i]]=i;↵
while(m--){↵
int x;↵
cin>>x;↵
x--;↵
if(getsum(pos[x],pos[x],0,n-1,0)==1) cout<<"-1 ";↵
else{↵
int prev=x;↵
while(pH[x]!=0 && getsum(pos[pH[x]],pos[x],0,n-1,0)==0){↵
prev=pH[x];↵
x=par[pH[x]];↵
}↵
int l=pos[pH[x]],r=pos[x],ans=prev;↵
while(l<=r){↵
int mid=(l+r)/2;↵
if(getsum(mid,pos[x],0,n-1,0)==0){↵
ans=horder[mid];↵
r=mid-1;↵
}↵
else l=mid+1;↵
}↵
cout<<ans+1<<" ";↵
update(0,n-1,pos[ans],0,1);↵
}↵
}↵
cout<<"\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
[F](https://mirror.codeforces.com/gym/105137/problem/F)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
<spoiler summary="solution">↵
↵
The Naveen’s array elements are the integers which has even number of set bits.↵
↵
The Pavan Kalyan’s array elements are the integers which has odd number of set bits.↵
↵
You can get it in OEIS but mentioned in statement for fun activity.↵
↵
Now you need to find the number of simple of paths whose Bitwise Xor has even set bits and odd set bits. For that, Fix a root of the tree and create an array whose elements indicates ‘1’ if there are odd set bits in the bitwise Xor of the path between the root and that particular node and ‘0’ for vice-versa.↵
↵
Let u→v path bitwise Xor has even set bits and v→w path bitwise Xor has even set bits the u→w path bitwise Xor has even set bits.↵
↵
Proof: u→w path bitwise Xor bits= number of bits in u→v + number of bits in v→w – 2*(number of common bits in u→v and v→w).↵
↵
it is even+even-even which is even.↵
↵
From the above fact we can find the answer to queries easily.↵
↵
Time Complexity: $O(n+q \cdot log(10^9))$.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
const ll N=2e6+10;↵
ll n;↵
vector<vector<pair<ll,ll>>> adj;↵
vector<ll> X;↵
vector<bool> vis;↵
↵
void bfs(ll s){↵
vis[s]=true;↵
X[s]=0;↵
queue<ll> q;↵
q.push(s);↵
while(q.size()>0){↵
ll u=q.front();↵
q.pop();↵
for(auto v:adj[u]){↵
if(!vis[v.first]){↵
vis[v.first]=true;↵
X[v.first]=v.second^X[u];↵
q.push(v.first);↵
}↵
}↵
}↵
}↵
↵
int main(){↵
fast;↵
ll t;↵
t=1;↵
while(t--){↵
ll q;↵
cin>>n>>q;↵
adj.clear();↵
adj.resize(n);↵
for(ll i=0;i<n-1;i++){↵
ll u,v,w;↵
cin>>u>>v>>w;↵
u--;↵
v--;↵
adj[u].push_back({v,w});↵
adj[v].push_back({u,w});↵
}↵
X.clear();↵
X.resize(N,0);↵
vis.clear();↵
vis.resize(N,false);↵
bfs(0);↵
ll cnt0=0,cnt1=0;↵
for(ll i=0;i<n;i++){↵
if((__builtin_popcount(X[i]))%2) cnt1++;↵
else cnt0++;↵
}↵
while(q--){↵
ll q1;↵
cin>>q1;↵
if(q1==1){↵
ll u,v,w;↵
cin>>u>>v>>w;↵
u--;↵
v--;↵
if(vis[v]) swap(u,v);↵
vis[v]=true;↵
X[v]=X[u]^w;↵
if((__builtin_popcount(X[v]))%2) cnt1++;↵
else cnt0++;↵
}↵
else{↵
ll c;↵
cin>>c;↵
if(c==0) cout<<(cnt1*(cnt1-1))+(cnt0*(cnt0-1))<<endl;↵
else cout<<(2*cnt0*cnt1)<<endl;↵
}↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[G](https://mirror.codeforces.com/gym/105137/problem/G)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
<spoiler summary="solution">↵
↵
Observe that the given tree is similar to undirected tree but instead of single edge there are two directed edges with facing opposite directions.↵
↵
First, let’s get the upper bound of the ans. For each tree edge let cnt be the number of times we pass through this edge. Since there are only two directions for this edge, ans will increase from this edge is at most min(cnt, 2). Thus, the upper bound of the ans is sum of min(cnt, 2) over all edges.↵
↵
For the constructive part, Take two paths that involve u. Suppose that they are (u,v) and (u,w). Let (u,in) be the intersection of these two paths. Now, we add a restriction: if we choose v → u we must choose u → w, and if we choose u→ v we must choose w → u. With this restriction, we can ensure that the edges between u and in are covered in both directions, and in the future we can ignore those edges. Thus, v→ u and u→w is equivalent to v→w, and u→v and w → u is equivalent to w→ v. Now we can remove two paths (u,v) and (u,w) and add (v,w) instead. Repeat this process for every edge to get the optimal selection.↵
↵
Time Complexity: $O(nm+n^2)$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
const int N=10010;↵
int n,m;↵
vector<vector<int>> adj;↵
vector<int> path,vec;↵
vector<vector<pair<int,int>>> adj1;↵
vector<pair<int,int>> res1;↵
vector<bool> vis;↵
↵
void dfs(int x, int p, int ff){↵
vec.push_back(x);↵
if(x==ff){↵
path=vec;↵
}↵
for(auto i:adj[x]){↵
if(i!=p){↵
dfs(i,x,ff);↵
}↵
}↵
vec.pop_back();↵
}↵
↵
void dfs1(int x){↵
while((int)adj1[x].size()>0){↵
auto it=adj1[x].back();↵
adj1[x].pop_back();↵
if(!vis[it.second]){↵
vis[it.second]=true;↵
dfs1(it.first);↵
res1[it.second]={it.first,x};↵
}↵
}↵
}↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
cin>>n>>m;↵
adj.clear();↵
adj.resize(n);↵
for(int i=0;i<n-1;i++){↵
int u,v;↵
cin>>u>>v;↵
u--;↵
v--;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
vector<pair<int,int>> res(m);↵
for(int i=0;i<m;i++){↵
cin>>res[i].first>>res[i].second;↵
}↵
adj1.clear();↵
adj1.resize(n+1);↵
int ans=0;↵
map<pair<int,int>,int> mp;↵
for(int i=0;i<m;i++){↵
adj1[res[i].first].push_back({res[i].second,i+1});↵
adj1[res[i].second].push_back({res[i].first,i+1});↵
vec.clear();↵
path.clear();↵
dfs(res[i].first-1,-1,res[i].second-1);↵
for(int j=0;j<(int)path.size()-1;j++){↵
int u=path[j],v=path[j+1];↵
if(u>v) swap(u,v);↵
mp[{u,v}]++;↵
}↵
}↵
int cnt=m+1;↵
for(int i=0;i<n;i++){↵
for(auto j:adj[i]){↵
if(j<i && mp[{j,i}]>0){↵
ans+=min(2,mp[{j,i}]);↵
if(mp[{j,i}]%2){↵
adj1[i+1].push_back({j+1,cnt});↵
adj1[j+1].push_back({i+1,cnt});↵
cnt++;↵
}↵
}↵
}↵
}↵
res1.clear();↵
res1.resize(N);↵
vis.clear();↵
vis.resize(N,false);↵
for(int i=1;i<=n;i++) dfs1(i);↵
cout<<ans<<"\n";↵
for(int i=1;i<=m;i++){↵
if(res1[i].first==res[i-1].first) cout<<"1 ";↵
else cout<<"2 ";↵
}↵
cout<<"\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
↵
↵
<spoiler summary="solution">↵
↵
The optimal way to hit $ n $ runs in minimum balls is to hit $ 6 $ runs on every ball until you reach $ n $ runs. ↵
The optimal way to hit $ n $ runs in maximum balls is to hit $ 4 $ runs on every ball until you reach $ n $ runs. ↵
Time Complexity: $ O(1) $.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
int n;↵
cin>>n;↵
cout<<((n+5)/6)<<" "<<((n+3)/4)<<"\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
↵
[B](https://mirror.codeforces.com/gym/105137/problem/B)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
↵
<spoiler summary="solution">↵
↵
From the definition of the Good string it clearly seems that string must contain either all 0’s or 1’s.↵
↵
So all 0’s are converted into 1’s in the following ways:↵
↵
1. Using Operation 1 by using $ a $ coins per operation.↵
↵
2. Using Operation 2 by using $ b $ coins per operation by using any extra '1' in the string.↵
↵
All 1’s are converted into 0’s in the following ways:↵
↵
1. Using Operation 1 by using $ a $ coins per operation.↵
↵
2. Using Operation 2 for pair of 1’s using $ b $ coins per operation. If there is single '1' left this can be converted to '0' by either using $ a $ coins or $ 2b $ coins.↵
↵
The minimum coins will get in one of the above scenarios.↵
Time Complexity: $ O(n) $.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
int n,a,b;↵
cin>>n>>a>>b;↵
string s;↵
cin>>s;↵
int cnt0=count(s.begin(),s.end(),'0');↵
int cnt1=n-cnt0;↵
int ans1=a*cnt0;↵
int ans2=b*cnt0;↵
int ans3=a*cnt1;↵
int ans4=((cnt1/2)*b+(cnt1%2)*(min(a,2*b)));↵
cout<<min({ans1,ans2,ans3,ans4})<<"\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[C](https://mirror.codeforces.com/gym/105137/problem/C)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
<spoiler summary="solution">↵
↵
The lower bound of $ F(p) $ will be $ \log_2(n) + 1 $.↵
↵
Mathematically,↵
Let's consider $ \sum \frac{p_i}{i} \geq \log_2(n) + 1 $ (ans).↵
↵
Let $ 2^x \leq n \leq 2^{x+1} $,↵
$ m = 2^{x+1} $.↵
↵
Array $ b = p $.↵
$ \left\lfloor \frac{p_m}{m} \right\rfloor \geq \left\lfloor \frac{2^{x+1}}{m} \right\rfloor = \left\lfloor \frac{(2^x+2^x)}{m} \right\rfloor \geq \left\lfloor \frac{(b_m+m)}{m} \right\rfloor $.↵
↵
So $ \sum \frac{p_i}{i} \geq \sum \frac{(b_i+i)}{i} = \sum \frac{(p_i+i)}{i} = \sum \frac{p_i}{i} + 1 \geq \text{ans} + 1 $.↵
↵
Hence showed that lower bound will be limited to $ \log_2(n) + 1 $.↵
↵
So construct the permutation accordingly.↵
↵
Time Complexity: $ O(n+\log n) $.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
int n;↵
cin>>n;↵
vector<int> a(n+1);↵
for(int i=1;i<=n;i++) a[i]=i-1;↵
int p=n;↵
while(p!=0){↵
int x=p/2;↵
x++;↵
swap(a[x],p);↵
}↵
for(int i=1;i<=n;i++) cout<<a[i]<<" ";↵
cout<<endl;↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[D](https://mirror.codeforces.com/gym/105137/problem/D)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
↵
<spoiler summary="solution">↵
↵
From the given queries we only know the information about number of zeroes and ones in the hidden string but how we can get to know the positions of ‘01’ and ‘10’ (Binary Search it!)↵
↵
Just know the first character by asking queries like 000…n times and 1000…(n-1) times.↵
↵
Later do the binary search to know the first occurrence of the character other than first character, similarly, do the binary search for another substring position.↵
↵
Total queries used are $ 2\log(n) + 2 < 40 $.↵
↵
Time Complexity: $ O(n\log n) $.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
//t=1;↵
while(t--){↵
int n;↵
cin>>n;↵
string s="";↵
for(int i=0;i<n;i++) s+='0';↵
int cnt0,cnt1;↵
cout<<"? "<<s<<endl;↵
cin>>cnt0;↵
cnt1=n-cnt0;↵
if(cnt0==n || cnt0==0) cout<<"! -1 -1"<<endl;↵
else{↵
int pos1=-1,pos2=-1;↵
s[0]='1';↵
int x;↵
cout<<"? "<<s<<endl;↵
cin>>x;↵
if(x<cnt0){↵
pos1=0;↵
int l=pos1,r=n-1;↵
while(l<=r){↵
int m=(l+r)/2;↵
string s1="";↵
for(int i=0;i<=m;i++) s1+='1';↵
for(int i=m+1;i<n;i++) s1+='0';↵
cout<<"? "<<s1<<endl;↵
cin>>x;↵
if(x==(cnt0-(m+1))){↵
pos1=m;↵
l=m+1;↵
}↵
else r=m-1;↵
}↵
if((pos1+1)==cnt0) cout<<"! "<<pos1+1<<" "<<"-1"<<endl;↵
else{↵
pos2=pos1+1;↵
l=pos2,r=n-1;↵
while(l<=r){↵
int m=(l+r)/2;↵
string s1="";↵
for(int i=0;i<=m;i++) s1+='1';↵
for(int i=m+1;i<n;i++) s1+='0';↵
cout<<"? "<<s1<<endl;↵
cin>>x;↵
x+=pos1+1;↵
if(x==(cnt0+(m-pos1))){↵
pos2=m;↵
l=m+1;↵
}↵
else r=m-1;↵
}↵
cout<<"! "<<pos1+1<<" "<<pos2+1<<endl;↵
}↵
}↵
else{↵
pos2=0;↵
int l=pos2,r=n-1;↵
while(l<=r){↵
int m=(l+r)/2;↵
string s1="";↵
for(int i=0;i<=m;i++) s1+='1';↵
for(int i=m+1;i<n;i++) s1+='0';↵
cout<<"? "<<s1<<endl;↵
cin>>x;↵
if(x==(cnt0+(m+1))){↵
pos2=m;↵
l=m+1;↵
}↵
else r=m-1;↵
}↵
if((pos2+1)==cnt1) cout<<"! -1"<<" "<<pos2+1<<endl;↵
else{↵
pos1=pos2+1;↵
l=pos1,r=n-1;↵
while(l<=r){↵
int m=(l+r)/2;↵
string s1="";↵
for(int i=0;i<=m;i++) s1+='1';↵
for(int i=m+1;i<n;i++) s1+='0';↵
cout<<"? "<<s1<<endl;↵
cin>>x;↵
x-=(pos2+1);↵
if(x==(cnt0-(m-pos2))){↵
pos1=m;↵
l=m+1;↵
}↵
else r=m-1;↵
}↵
cout<<"! "<<pos1+1<<" "<<pos2+1<<endl;↵
}↵
}↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
[E](https://mirror.codeforces.com/gym/105137/problem/E)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
<spoiler summary="solution">↵
↵
In this problem we need to find the highest ancestor of the node which is empty.↵
↵
We can do Binary Lifting, HLD etc., Time limit given to get accept any solution.↵
↵
Time Complexity: $O(nlogn)$ (Binary Lifting)↵
↵
Time Complexity: $O(nlog^2 n)$ (HLD)↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
int n,m;↵
vector<vector<int>> adj;↵
vector<int> H,pH,tree,pos,horder,sz,par;↵
↵
int getsum(int qs, int qe, int ss, int se, int si){↵
if(se<qs || ss>qe) return 0;↵
if(qs<=ss && qe>=se) return tree[si];↵
int mid=(ss+se)/2;↵
int v1=getsum(qs,qe,ss,mid,2*si+1);↵
int v2=getsum(qs,qe,mid+1,se,2*si+2);↵
return v1+v2;↵
}↵
↵
void update(int ss, int se, int i, int si, int diff){↵
if(i<ss || i>se) return;↵
tree[si]=tree[si]+diff;↵
if(se>ss){↵
int mid=(ss+se)/2;↵
update(ss,mid,i,2*si+1,diff);↵
update(mid+1,se,i,2*si+2,diff);↵
}↵
}↵
↵
void dfs(int x, int p){↵
sz[x]=1;↵
par[x]=p;↵
int pp=-1,maxi=0;↵
for(auto i:adj[x]){↵
if(i!=p){↵
dfs(i,x);↵
sz[x]+=sz[i];↵
if(sz[i]>maxi){↵
maxi=sz[i];↵
pp=i;↵
}↵
}↵
}↵
if(pp!=-1){↵
H[pp]=x;↵
}↵
}↵
↵
void dfs1(int x, int p){↵
if(H[x]==p) pH[x]=pH[p];↵
for(auto i:adj[x]){↵
if(i!=p){↵
dfs1(i,x);↵
}↵
}↵
}↵
↵
void dfs2(int x, int p){↵
horder.push_back(x);↵
for(auto i:adj[x]){↵
if(i!=p){↵
if(H[i]==x) dfs2(i,x);↵
}↵
}↵
for(auto i:adj[x]){↵
if(i!=p){↵
if(H[i]!=x) dfs2(i,x);↵
}↵
}↵
}↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
cin>>n>>m;↵
adj.clear();↵
adj.resize(n);↵
for(int i=0;i<n-1;i++){↵
int u,v;↵
cin>>u>>v;↵
u--;↵
v--;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
H.clear();↵
H.resize(n);↵
for(int i=0;i<n;i++) H[i]=i;↵
pH.clear();↵
pH.resize(n);↵
for(int i=0;i<n;i++) pH[i]=i;↵
tree.clear();↵
tree.resize(4*n,0);↵
pos.clear();↵
pos.resize(n);↵
sz.clear();↵
sz.resize(n);↵
par.clear();↵
par.resize(n);↵
horder.clear();↵
dfs(0,-1);↵
dfs1(0,-1);↵
dfs2(0,-1);↵
for(int i=0;i<n;i++) pos[horder[i]]=i;↵
while(m--){↵
int x;↵
cin>>x;↵
x--;↵
if(getsum(pos[x],pos[x],0,n-1,0)==1) cout<<"-1 ";↵
else{↵
int prev=x;↵
while(pH[x]!=0 && getsum(pos[pH[x]],pos[x],0,n-1,0)==0){↵
prev=pH[x];↵
x=par[pH[x]];↵
}↵
int l=pos[pH[x]],r=pos[x],ans=prev;↵
while(l<=r){↵
int mid=(l+r)/2;↵
if(getsum(mid,pos[x],0,n-1,0)==0){↵
ans=horder[mid];↵
r=mid-1;↵
}↵
else l=mid+1;↵
}↵
cout<<ans+1<<" ";↵
update(0,n-1,pos[ans],0,1);↵
}↵
}↵
cout<<"\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
[F](https://mirror.codeforces.com/gym/105137/problem/F)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
<spoiler summary="solution">↵
↵
The Naveen’s array elements are the integers which has even number of set bits.↵
↵
The Pavan Kalyan’s array elements are the integers which has odd number of set bits.↵
↵
You can get it in OEIS but mentioned in statement for fun activity.↵
↵
Now you need to find the number of simple of paths whose Bitwise Xor has even set bits and odd set bits. For that, Fix a root of the tree and create an array whose elements indicates ‘1’ if there are odd set bits in the bitwise Xor of the path between the root and that particular node and ‘0’ for vice-versa.↵
↵
Let u→v path bitwise Xor has even set bits and v→w path bitwise Xor has even set bits the u→w path bitwise Xor has even set bits.↵
↵
Proof: u→w path bitwise Xor bits= number of bits in u→v + number of bits in v→w – 2*(number of common bits in u→v and v→w).↵
↵
it is even+even-even which is even.↵
↵
From the above fact we can find the answer to queries easily.↵
↵
Time Complexity: $O(n+q \cdot log(10^9))$.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
const ll N=2e6+10;↵
ll n;↵
vector<vector<pair<ll,ll>>> adj;↵
vector<ll> X;↵
vector<bool> vis;↵
↵
void bfs(ll s){↵
vis[s]=true;↵
X[s]=0;↵
queue<ll> q;↵
q.push(s);↵
while(q.size()>0){↵
ll u=q.front();↵
q.pop();↵
for(auto v:adj[u]){↵
if(!vis[v.first]){↵
vis[v.first]=true;↵
X[v.first]=v.second^X[u];↵
q.push(v.first);↵
}↵
}↵
}↵
}↵
↵
int main(){↵
fast;↵
ll t;↵
t=1;↵
while(t--){↵
ll q;↵
cin>>n>>q;↵
adj.clear();↵
adj.resize(n);↵
for(ll i=0;i<n-1;i++){↵
ll u,v,w;↵
cin>>u>>v>>w;↵
u--;↵
v--;↵
adj[u].push_back({v,w});↵
adj[v].push_back({u,w});↵
}↵
X.clear();↵
X.resize(N,0);↵
vis.clear();↵
vis.resize(N,false);↵
bfs(0);↵
ll cnt0=0,cnt1=0;↵
for(ll i=0;i<n;i++){↵
if((__builtin_popcount(X[i]))%2) cnt1++;↵
else cnt0++;↵
}↵
while(q--){↵
ll q1;↵
cin>>q1;↵
if(q1==1){↵
ll u,v,w;↵
cin>>u>>v>>w;↵
u--;↵
v--;↵
if(vis[v]) swap(u,v);↵
vis[v]=true;↵
X[v]=X[u]^w;↵
if((__builtin_popcount(X[v]))%2) cnt1++;↵
else cnt0++;↵
}↵
else{↵
ll c;↵
cin>>c;↵
if(c==0) cout<<(cnt1*(cnt1-1))+(cnt0*(cnt0-1))<<endl;↵
else cout<<(2*cnt0*cnt1)<<endl;↵
}↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[G](https://mirror.codeforces.com/gym/105137/problem/G)↵
↵
Idea:[user:yugandhar_master,2024-03-14]↵
↵
<spoiler summary="solution">↵
↵
Observe that the given tree is similar to undirected tree but instead of single edge there are two directed edges with facing opposite directions.↵
↵
First, let’s get the upper bound of the ans. For each tree edge let cnt be the number of times we pass through this edge. Since there are only two directions for this edge, ans will increase from this edge is at most min(cnt, 2). Thus, the upper bound of the ans is sum of min(cnt, 2) over all edges.↵
↵
For the constructive part, Take two paths that involve u. Suppose that they are (u,v) and (u,w). Let (u,in) be the intersection of these two paths. Now, we add a restriction: if we choose v → u we must choose u → w, and if we choose u→ v we must choose w → u. With this restriction, we can ensure that the edges between u and in are covered in both directions, and in the future we can ignore those edges. Thus, v→ u and u→w is equivalent to v→w, and u→v and w → u is equivalent to w→ v. Now we can remove two paths (u,v) and (u,w) and add (v,w) instead. Repeat this process for every edge to get the optimal selection.↵
↵
Time Complexity: $O(nm+n^2)$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define fast \↵
ios_base::sync_with_stdio(0); \↵
cin.tie(0); \↵
cout.tie(0);↵
↵
const int N=10010;↵
int n,m;↵
vector<vector<int>> adj;↵
vector<int> path,vec;↵
vector<vector<pair<int,int>>> adj1;↵
vector<pair<int,int>> res1;↵
vector<bool> vis;↵
↵
void dfs(int x, int p, int ff){↵
vec.push_back(x);↵
if(x==ff){↵
path=vec;↵
}↵
for(auto i:adj[x]){↵
if(i!=p){↵
dfs(i,x,ff);↵
}↵
}↵
vec.pop_back();↵
}↵
↵
void dfs1(int x){↵
while((int)adj1[x].size()>0){↵
auto it=adj1[x].back();↵
adj1[x].pop_back();↵
if(!vis[it.second]){↵
vis[it.second]=true;↵
dfs1(it.first);↵
res1[it.second]={it.first,x};↵
}↵
}↵
}↵
↵
int main(){↵
fast;↵
ll t;↵
cin>>t;↵
while(t--){↵
cin>>n>>m;↵
adj.clear();↵
adj.resize(n);↵
for(int i=0;i<n-1;i++){↵
int u,v;↵
cin>>u>>v;↵
u--;↵
v--;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
vector<pair<int,int>> res(m);↵
for(int i=0;i<m;i++){↵
cin>>res[i].first>>res[i].second;↵
}↵
adj1.clear();↵
adj1.resize(n+1);↵
int ans=0;↵
map<pair<int,int>,int> mp;↵
for(int i=0;i<m;i++){↵
adj1[res[i].first].push_back({res[i].second,i+1});↵
adj1[res[i].second].push_back({res[i].first,i+1});↵
vec.clear();↵
path.clear();↵
dfs(res[i].first-1,-1,res[i].second-1);↵
for(int j=0;j<(int)path.size()-1;j++){↵
int u=path[j],v=path[j+1];↵
if(u>v) swap(u,v);↵
mp[{u,v}]++;↵
}↵
}↵
int cnt=m+1;↵
for(int i=0;i<n;i++){↵
for(auto j:adj[i]){↵
if(j<i && mp[{j,i}]>0){↵
ans+=min(2,mp[{j,i}]);↵
if(mp[{j,i}]%2){↵
adj1[i+1].push_back({j+1,cnt});↵
adj1[j+1].push_back({i+1,cnt});↵
cnt++;↵
}↵
}↵
}↵
}↵
res1.clear();↵
res1.resize(N);↵
vis.clear();↵
vis.resize(N,false);↵
for(int i=1;i<=n;i++) dfs1(i);↵
cout<<ans<<"\n";↵
for(int i=1;i<=m;i++){↵
if(res1[i].first==res[i-1].first) cout<<"1 ";↵
else cout<<"2 ";↵
}↵
cout<<"\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
