PROBLEM LINK:
Setter: Gaurish Baliga
Tester: Rohit Tawde
Editorialist: Gaurish Baliga
DIFFICULTY
Easy-Medium
PREREQUISITES:
Trees.
PROBLEM
Krakenmonstor decided to host a supertournament. 2^N people are playing the tournament. Each player has a strength S associated with them.
You are given the initial strength array S where S{_i} denotes the strength of the i^{th} and are required to process Q queries. The queries are of 3 types:
-
1 X : Print ‘YES’ if player X is the current winner of the tournament, otherwise print ‘NO’.
-
2 X W: Update the strength of the X^{th} player to W. Note that the results of the tournament might change after this update.
-
3 A B: If player A has won more matches than player B print ‘FIRST’, else if B has won more matches print ‘SECOND’, else print ‘DRAW’.
EXPLANATION
As the problem suggests, we need to maintain a Tree data structure to handle these queries. Since the Tree happens to be a perfect binary tree, we can handle each query in O(logn) for an overall time complexity of O(nlogn).
Now for implemention, we know that if a tree were to be flattened in an array, then
children of a[i] would be a[2i] and a[2i + 1]. We use exactly this to maintain our Tournament Tree
For Query 1, a[1] would hold the winner of the tournament
For Query 2, if we update a[i], then updating all other nodes could just be done by halfing i everytime
For Query 3, we can maintain another win array which denotes how many games a particular person has won
TIME COMPLEXITY:
O(N\log (N)).
SOLUTION
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, q; cin >> n >> q;
vector<pair<int,int> >arr((2<<n) + 1);
vector<int>win((1<<n) + 1);
for(int i = (1<<n) ; i < (2<<n); i++)
{
cin >> arr[i].first;
arr[i].second = (i - (1<<n) + 1);
}
for(int i = (1 << n) - 1; i >= 1; i--)
{
arr[i] = max(arr[2*i], arr[2*i + 1]);
win[arr[i].second]++;
}
for(int i = 0; i < q; i++)
{
int type; cin >> type;
if(type == 1)
{
int x; cin >> x;
cout << (x == arr[1].second ? "YES\n" : "NO\n");
}
if(type == 2)
{
int ind, val; cin >> ind >> val;
arr[(1<<n) + ind - 1] = make_pair(val, ind);
for(int i = ((1<<n) + ind - 1)/2; i >= 1; i /= 2)
{
if(arr[i].first != max(arr[2*i].first, arr[2*i + 1].first))
{
win[arr[i].second]--;
arr[i] = max(arr[2*i], arr[2*i + 1]);
win[arr[i].second]++;
}
}
}
if(type == 3)
{
int a, b; cin >> a >> b;
if(win[a] > win[b]) cout << "FIRST\n";
else if(win[b] > win[a]) cout << "SECOND\n";
else cout << "DRAW\n";
}
}
}
Tester's Solution
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
using namespace std;
int build(vector<int>&v, int i){
if(v[i]!=-1){
return v[i];
}
v[i]=max(build(v,(2*i)+1),build(v,(2*i)+2));
return v[i];
}
void check(vector<int>&v,int i, int k, int &c){
if(v[i]==k)
c++;
else
return;
if(i==0)
return;
else{
int ii=(i-1)/2;
check(v, ii, k, c);
}
}
void update(vector<int>&v,int i){
v[i]=max(v[(2*i)+1],v[(2*i)+2]);
if(i==0)
return;
else{
int ii=(i-1)/2;
update(v, ii);
}
}
int main() {
fast_io;
int t;
t=1;
while(t--){
ll n,q;
cin>>n>>q;
ll n1=pow(2,n);
vector<int>v;
while(n1){
for(int i =0;i<n1;i++){
v.pb(-1);
}
n1/=2;
}
n=pow(2,n);
vector<int>a(n);
for(int i =0; i <n;i++){
cin>>a[i];
}
reverse(a.begin(),a.end());
for(int i =0; i <n;i++){
v[i]=a[i];
}
map<ll,ll>pos;
reverse(v.begin(),v.end());
build(v,0);
for(int i =0;i<v.size();i++){
pos[v[i]]=i;
}
ll p=v.size()-n-1;
for(int i =0;i<q;i++){
ll k;
cin>>k;
ll x,y;
cin>>x;
if(k==3){
cin>>y;
ll k1=v[p+x];
ll k2=v[p+y];
int c1=0,c2=0;
check(v, p+x, k1, c1);
check(v, p+y, k2, c2);
if(c1>c2){
cout<<"FIRST\n";
}
else if(c2>c1){
cout<<"SECOND\n";
}
else{
cout<<"DRAW\n";
}
}
else if(k==2){
cin>>y;
pos[v[p+x]]=0;
v[p+x]=y;
pos[y]=p+x;
ll ii=(p+x-1)/2;
if(ii)
update(v, ii);
}
else{
if(v[0]==v[p+x]){
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
}
}
return 0;
}
[/details]