Simulate the game to find pattern: F(1) = 1 F(2) = 1 F(3) = 2 F(4) = 1 F(5) = 4 F(6) = 3 F(7) = 2 F(8) = 1 F(9) = 8 F(10) = 7 F(11) = 6 . . . F(15) = 2 F(16) = 1 Clearly, F(X) = (1 << ceil(log2(X))) — X + 1.

It's a special case of Josephus Problem (k = 2), you can read more about it on internet.

was problem 6 incorrect?

there is a pattern try dry running for n=9 to n=16 you will get the pattern.If you are lazy to do that than i am leaving the main logic here but i would recommend dry running to get intution yourself.

ans=(smallest power of two greater than n)-n+1

what was the condition for the binary search I did it but it was giving WA on samples and do we have to iterate over the given array in the same order as given or in any order, can we use elements for increasing the speed multiple times? The problem statement was very unclear.

I have not participated in this contest. But you can code it recursively which works in O(logN). First, observe that alternate positioned elements are deleted, now I will solve for even and odd cases separately.

Even Case:
Observe that after deleting the elements at alternate positions, we are left with a subproblem having n/2 numbers, if we know the answer of n/2 (say it is x), then the only task remaining is to find the original index of x when n numbers are there. It's easy to calculate/observe that it will 2*x-1.

Odd Case:
We will proceed in the similar way mentioned above, the only difference is that the last element will be at 1st position after one cycle of deletion. So instead of doing 2*x-1, the original index will be n-1 (for x=1) and 2*(x-1)-1 (for x>1).

Recursion:
ans(n) = 2*ans(n/2)-1 [For n = even]
ans(n) = 2*ans(n/2)-3 [For n = odd and ans(n/2)>1]
ans(n) = n-1 [For n = odd and ans(n/2)=1]

Correct me, if anything is wrong :)

puzzle-100-people-in-a-circle-with-gun-puzzle This is a puzzle. Almost same as this one.

Here is my recursive solution!

#include <bits/stdc++.h>
using namespace std;

int f(int x) {
    if(x == 1) return 0;

    if(x & 1) {
        return (2*f((x + 1)/2) + 1) % x;
    }
    else {
        return 2*f(x/2);
    }
}

int ans(int x) {
    return f(x) + 1;
}

int main() {
    for(int i = 1; i < 10; ++i) {
        int result = ans(i);
        cout << i << ":\t" << result << endl;
    }
    return 0;
}

PS: Lemme know, if there is any error :)

If you have some time, do watch this video by numberphile : https://www.youtube.com/watch?v=uCsD3ZGzMgE

Just find the greatest power of 2 greater than or equal to N. If N equals to a power of 2 then the answer will be one, else the answer will be the next greatest power-N+1. For eg. if N=9, greatest power of 2 equals 16. The answer here will be 16-9+1 = 8.

Link

I wasn't able to submit the solution on time but here's the idea I came up with I won't go into too much details. There we be at max log(n) operations so at each operation you just have to determine what is the maximum greatest number that is alive and also at each number the difference between two adjacent numbers will increase by power of two. And also look out for the case when length of the numbers alive is even and odd.

#include<bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << setprecision(15) << fixed;

    int tc=1;
    cin>>tc;
    while ( tc-- ) {
        int n;
        cin>>n;

        int curr = n;
        int len = n;
        int cnt = 0;
        int tmp = 0;
        while( len > 1 ){
            if( len % 2 ){
                ++tmp;
                len /= 2;
                ++len;
            }
            else{
                curr -= ( 1<<cnt );
                cnt += tmp + 1;
                tmp = 0;
                len /= 2;
            }
        }

        cout<<curr<<endl;
    }
    return 0;
}

Have anyone solved question 1? I found some mistakes in the sample test cases, in the first sample test case, for the node with number 2, the answer was given 5 but actually it was coming out to be 4 according to me.

Number of tasks solved —

[1].

[2].

[3].

[4].

[5].

[6].

Solved — task1 , task2 , task3 , task4 , task5 , task6