PROBLEM LINKS
DIFFICULTY
EASY
PREREQUISITES
Binary Search
PROBLEM
We want to crack N servers. Each server is protected by a password. There are two types of passwords:
- Power password: numbers of the form AB with A, B ≥ 2.
- Non-power password: all other non-negative numbers.
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 Non-Power Server (server with non-power 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 Non-Power 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 EXPLANATION
Actually, it seems that the problem statement gives all knowledge required to solve this problem. However, there are still several important information that are missing:
- How to determine quickly whether a number is power password or not?
- How to determine the rank of a given (non-)power password?
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 non-power password by calculating the rank of the password, and then simulating the binary search mentioned in the problem statement.
EXPLANATION
All 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 built-in sqrt() function as follows:
#include
// 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 problem-setter’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 odd-power 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 odd-power 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 while-loop 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 (1-based) 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.
Non-Power Passwords
First, we have to determine the rank (1-based) of this password in non-power password list. But we don’t have the non-power password list! However, it is just complement of the power password list. Therefore, actually:
rank of X in non-power 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 non-power 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 problem-setter’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 SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.