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;

    vector<long long> p = {1};

        i = 2*i+2;

        cin >> n;

        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