PROBLEM LINKSDIFFICULTYEASY PREREQUISITESBinary Search PROBLEMWe want to crack N servers. Each server is protected by a password. There are two types of passwords:
To crack a Power Server (server with power password), we have no choice but trying all power passwords sequentially until we find out the correct password. On the other hand, a NonPower Server (server with nonpower password) has an friendly indicator. The indicator will become green if we enter a number that is smaller than the actual password, and red if we enter a number that is greater than the actual password. To crack a NonPower server, we will try the 2nd, 4th, 8th, 16th, ..., until we are correct or the indicator becomes red. After that, we will use the usual binary search to find out the correct password. We spend one second to enter each password. Determine how long we need to crack all servers. QUICK EXPLANATIONActually, it seems that the problem statement gives all knowledge required to solve this problem. However, there are still several important information that are missing:
Both above queries can be solved by binary search on a sorted list of all power passwords (this must be done efficiently). After that, we can calculate the time spent on a power password as the rank of the password. We can calculate the time spent on a nonpower password by calculating the rank of the password, and then simulating the binary search mentioned in the problem statement. EXPLANATIONAll queries in the Quick Explanation section could be answered by storing all power password in a sorted list and then performing binary search on it. The first query can be answered by checking whether the given number is present in the list. The second query can be answered by counting the number of power passwords that are less than or equal to the given number. The problem is that there are too many possible power password under the given constraints. We need several optimizations. Optimization 1: Ignoring square numbers Under the constraints, there are floor(3141^(5/2)) = 552,929,601 square numbers, which is obviously too many to store. We can overcome this by not storing square numbers at all. Instead, we can determine whether a number is square, or counting the number of square numbers below a given number, by using a separate binary search or using builtin sqrt() function as follows: #include <cmath> // this also counts number of squares ≤ x int my_sqrt(long long x) { return sqrt(x + 0.5); } bool is_square(long long x) { long long sq_x = sqrt(x); return sq_x * sq_x == x; } Note that this only works correctly on GNU C++ Compiler. Since CodeChef uses this compiler, the above code is safe. This may not accurate on other system because double data type cannot represent all integers between 1 and 3141^5 correctly due to lack of precision. The correct and fast way is contained is problemsetter's solution. With the above optimization, we can now iterate over all power passwords other than square numbers and store them in a list. In this way, we also get a bonus efficiency gain: we only need to iterate over all oddpower passwords because all passwords of the form A^B where B is an even number are square numbers. Therefore, we only need to iterate and store M^1/3 + M^1/5 + M^1/7 + ... numbers where M = 3141^5, which is less than 700,000. powpwd = [] // list of all oddpower passwords for a := 1; a := 3141^(5/3); a++: if a is square then skip it x := a * a * a // a^3 powpwd.append(x) while x * a * a ≤ 3141^5: x := x * a * a // the next odd power of a powpwd.append(x) sort powpwd remove duplicate numbers in powpwd We should be careful of the potential overflow in the whileloop above. For example, in C++ we can rewrite the condition safely as while (x <= M / a / a), where M = 3141^5. Optimization 2: Separating a^3 from other power passwords There are 3141^(5/3) = 673668 numbers of the form a^3 not greater than 3141^5. These numbers form most of the power passwords! So, instead of storing all power passwords and then sort them, it is better to first iterate passwords of the form a^3 separately and store them in increasing order (which is trivial to do). Then, use the pseudocode above to store all remaining power passwords of the form a^5, a^7, a^9, ... and then sort them. Now, the number of passwords we sort is very small without the cubes and the log factor in sorting is negligible. We can then merge the sorted list a^3 passwords and the sorted list remaining passwords in linear time. This is clearly a much faster way.  Now that we have a sorted list of power passwords, we can calculate the time spent in both types of password in the following ways. Note that before that, we have to determine whether a password is power or not  just simply check whether it is a square number or it is present it the password list using binary search. Power Passwords We try the password sequentially. Therefore, the time spent to crack power password is just equal to the rank (1based) of the password in the power password list. We can calculate this as follows: rank of X in power password list = (number of squares less than or equal to X) + (number of power password other than squares less than or equal to X). The last term of the equation can be calculated by using binary search on out power password list. NonPower Passwords First, we have to determine the rank (1based) of this password in nonpower password list. But we don't have the nonpower password list! However, it is just complement of the power password list. Therefore, actually: rank of X in nonpower password list = (X + 1)  (number of squares less than X)  (number of power password other than squares less than X). Let P be the rank of the nonpower password. We can then calculate the time spent to crack this password by simulating the binary search mentioned in the problem statement: function non_power_password_time(P): ans := 0 R := 1 while R ≤ P: ans++ if R == P: return ans R := R * 2 L := R / 2 while L < R: ans++ M := (L + R) div 2 if M == P: return ans else if M < P L := M else R := M return ans Also note that number of iterations in this binary search depends only the highest and lowest bit of the rank in binary. So we can calculate it in O(1) time. Refer to the problemsetter's solution. In conclusion, we have a solution that runs in O(K) (time spent on creating the power password list) + O(N log K) (time spent on answering all passwords), where K is the number of elements in our password list = 3141^(5/3). SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 18 Feb '13, 00:08

Reply to @vaibhavatul47 about the inequality M^1/3 + M^1/5 + M^1/7 + ... <= 700,000 We actually need the sum:
where The reason to consider this sum is that there are exactly For So this sum is finite and you could simply calculate it in a loop using function answered 19 Feb '13, 03:01

How to find approx value of : M^1/3 + M^1/5 + M^1/7 + ... (M = 3141^5); i.e. M^1/3 + M^1/5 + M^1/7 + ... <= 700,000