CHOOSEURFATE - Editorial

editorial
, ,
1

Problem Link: Choose your Fate - Problems - Codechef
Author: harshith_4

Observation and Approach:
Case(i): For every number with all bits set, i.e., for all n, say {2^k} - 1 after every round, the knife will be back at 1 with n>>1 person left till there are 3 people left. And when there are 3 persons left, 1, p, q now 1 kills q and gives the knife to p, p should kill himself => 1 wins.

Case(ii): For all 2 powers, after the first round, the knife gets to 2, and now the situation is similar to case(i) with life at 2. So, similarly, 2 wins.

Case(iii): And for every other number, after the first round, it reduces to either case(i) or case(ii), which reduces to 2*(n-p+1) for every n, with p the nearest power of 2 less than n.

Implementation: Implementing the above three cases for each number using pre-computed values of complete set bit numbers, i.e., {2^k} - 1 stored in an array.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;
const long long MAX = 1e18;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    long long T, n, k, i=2;
    cin >> T;
    
    assert(T<=1000);

    vector<long long> p = {1};

    while(i<=MAX){
        p.push_back(i);
        i = 2*i+2;
    }

    while(T--){
        cin >> n;

        assert(n<=1000);
        for(i=0; i<n; i++){
            cin >> k;
            assert(k<=(long long)1e18);

            auto it = upper_bound(p.begin(), p.end(), k) - 1;
            if(*it==k-1) cout << 1 << " ";
            else if(*it==k) cout << k << " ";
            else cout << 2*(k-1-(*it)) << " ";
        }
        cout << endl;
    }

    return 0;
}

Submission: Explanation - Solution - Choose your Fate

1 Like