TOURQUE - EDITORIAL

PROBLEM LINK:

Contest

Practice

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]