# CHOOSEURFATE - Editorial

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