Challenge Question 2

[mrnutty]

This question is from code chef, named Odd. I believe this
is a good problem to play with for all levels. If I can solve it surely
anyone else can, cough * only if pi is fake* cough*.

Here is the question :

The captain of the ship TITANIC is a little .... off the track. He needs to select the crew for the ship. But everyone seems to be eligible. So to test their intelligence, he plays a game.  The contestants have to stand in a line. They are given the numbers  in the order in which they stand, starting from 1. The captain then removes all the contestants that are standing at an odd position.  Initially, standing people have numbers - 1,2,3,4,5... After first pass, people left are - 2,4,... 
After second pass - 4,....
And so on.
You want to board the ship as a crew member. Given the total number of applicants for a position, find the best place to stand in  the line so that you are selected.
[B]Input[/B]
First line contains the number of test cases t (t<=10^6). 
The next t lines contain integer n, the number of applicants for that case. (n<=10^9)

[B]Output[/B]
Display t lines, each containg a single integer, the place where you would stand to win a place at TITANIC.
Example

(Added) *Comments below not needed in the output;

Input:
2  //number of inputs 
5  //number of applicants
12  //number of applicants


Output:
4  //best position
8 //best position

Here are the specifications :

Time limit:	1s
Source limit:	50000
Language any for here.

I was analyzing it and found a pattern and solved the question.
Remember brute force wont work because of the TIME LIMIT for
one's application, although it might be helpful to get a program
first running.

Hope to see some solutions. Here is the page to the problem as well. Kudos, if someone does it faster than my time, 0.70 seconds.

If the instruction is not clear then ask.

Remember : Follow regular coding rules( neat, clean, readable ... ).

[DTV]

Cool. Thanks for telling me about this.

[Jiwe]

Working on it :) ! Thanks for the info.

[pspwxp fan]

YOU CONDEMN ME TO SINK!!

lol, jk. But how many applicants are there? and,

Time limit: 1s

Time limit for what? The program runtime? And i don't really understand the program I/O :(

[mrnutty]

Thats the slowest your program should run. I will test your code with codechef. It will advise me if your program runs slower than 1 second. There will be up to 10^6 test cases.

[VernonDozier]

I didn't see anywhere that specified the input filename, so I assume it is argv[1]? Here's my submission. I think it works if I understand the problem correctly.

#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;

unsigned int Log2 (unsigned int number)
// assumes number is greater than 0.  Log2 is negative infinity for 0.
// returns 0 for 1, 1 for 3, 2 for 6, 3 for 15, 4 for 17,  etc (logarithm base 2, truncated)
{
    assert (number > 0);
    
    unsigned int log2 = 0;
    
    while (number > 0)
    {
        number = number >> 1;
        log2++;
    }
    
    log2--;
    return log2;
}


unsigned int Power2 (unsigned int exponent)
// assumes exponent >= 0
// returns 1 for 0, 2 for 1, 4 for 2, 8 for 3, 16 for 4, etc.
{
    assert (exponent >= 0); // meaningless for unsigned int.
    
    unsigned int number = 1;
    return number << exponent;
}


int main (int argc, char* argv[])
{
    if (argc != 2)
    {
        cout << "Usage: ./execuatableName inputFileName\n";
        exit (1);
    }
    
    ifstream ins;
    ins.open (argv[1]);
    if (!ins.is_open ())
    {
        cout << "Can't open file.\n";
        exit (1);
    }
    
    unsigned int numTrials;
    unsigned int numPeople;
    ins >> numTrials;
    
    for (unsigned int i = 0; i < numTrials; i++)
    {
        ins >> numPeople;
        cout << Power2 (Log2 (numPeople)) << "\n";
    }
    
    ins.close ();
    return 0;
}

[mrnutty]

I didn't see anywhere that specified the input filename, so I assume it is argv[1]? Here's my submission. I think it works if I understand the problem correctly.

<snipped>

It should be right. There is no input file.
The codechef compiler compiles the code trying some input cases. The input should be
from the standard input, cin for C++.

Since people posted their solution. I figure i'll post mines. Its built
more for speed than safety, since the time limit is < 1 sec for about
10^6 test cases.

#include <stdio.h>
 
int main()
{
	size_t T = 0;
	
	scanf("%i",&T);

	size_t *ansArray = new size_t[T];
	
	unsigned long answer = 1;
	
	int currIndx = 0;
	
	while(T--)
	{		
		unsigned long maxApp = 0;
	
		scanf("%ul",&maxApp);
	
		while(answer <= maxApp){			
			answer <<= 1;
		}
		answer >>= 1;

		ansArray[currIndx++] = answer;

		answer = 2;
	}

	for(int i = 0; i < currIndx; i++){
		printf("%i\n",ansArray[i]);		
	}

	delete [] ansArray;
 
	return 0;
}

[ordeal1234]

could u please explain me logic of this solution... how was the inequality 2^log(ceil k) <=n derived?

[mike_2000_17]

The logic is that the preferred position is the highest power of 2 that fits entirely inside N. The process is like this, at every round, the first element will be taken out and the second element will be left along with every two element following it. After the last selection round, there will be only one number left (the preferred position if you want to be selected), which is also the first number in the set (a set of size 1). At the start, the first number is 1, then it is 2, then 4, then 8, then 16, and so on... until you hit a number whose double is too big for the original list, that means that that number is the one selected. So, you can skip all this brute force stuff and just compute the largest power of 2 that fits in N. And because integers are represented with bits, you can just find the highest bit that is set to 1 in the number N. So, the Power2(Log2(N)) essentially finds the position of the highest 1-bit and finds the number it corresponds to. FirstPerson's code does the same (albeit more tightly packed).

Neither firstPerson nor VernonDozier solve the problem in the fastest way, here is the fastest way:

#include <cstdio>

int main()
{
    std::size_t T = 0;

    std::scanf("%i",&T);
    std::size_t *ansArray = new std::size_t[T];

    for(int i = 0; i < T; ++i)
    {       
        unsigned long maxApp = 0;

        std::scanf("%ul",&maxApp);

        // Find the highest power-of-two number in maxApp,
        //  use binary search for the highest one-bit:
        std::size_t answer 1;
#define MASK_AND_SHIFT_ANSWER(MASK,POWER) if (maxApp & MASK) { answer <<= POWER; maxApp &= MASK; };
        MASK_AND_SHIFT_ANSWER(0xFFFF0000,16)
        MASK_AND_SHIFT_ANSWER(0xFF00FF00,8)
        MASK_AND_SHIFT_ANSWER(0xF0F0F0F0,4)
        MASK_AND_SHIFT_ANSWER(0xCCCCCCCC,2)
        MASK_AND_SHIFT_ANSWER(0xAAAAAAAA,1)
#undef MASK_AND_SHIFT_ANSWER

        ansArray[i] = answer >> 1;
    }
    for(int i = 0; i < T; i++)
        std::printf("%i\n",ansArray[i]);        

    delete [] ansArray;

    return 0;
}

[nezachem]

Objection! This solution presumes architectural details not mentioned in the problem statement (32-bit values).

Here's another log-time solution, which scales for any width:

    for (shift = 1; shift < sizeof(challenge); shift <<= 1)
        challenge |= challenge >> shift;
    answer = challenge & ~(challenge >> 1));

Of course in reality, such program spends most of cycles printing out 10^6 test cases.

[mike_2000_17]

Well, the problem statement specifies that n <= 10^9, which makes it fall in the 32bit range. So, my solution works for the problem that was given. However, your solution is really cool! But it has a few mistakes, this version is more accurate:

unsigned int get_highest_power_of_2(unsigned int N) {
  unsigned int bit_padding;
  for(unsigned int shift = 1; ((shift < 8 * sizeof(N)) && (bit_padding = N >> shift)); shift <<= 1)
    N |= bit_padding;
  return N & ~(N >> 1);
};

I fixed the 8 * sizeof(N) which I guess you simply forgot. And I made the loop stop as soon as there are no more bits to pad.

And of course, I agree, most of the execution time of the actual program is the capturing and printing of the 10^6 test cases.

[nezachem]

But it has a few mistakes

Granted. Never tested it.

PS: for a 100% architectural correctness, replace 8 with CHAR_BIT. Don't forget to #include <limits.h>