PROBLEM LINK:
Author: shay_gan
Tester: shay_gan
Editorialist: shay_gan
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Modular arithmetic
EXPLANATION:
The question is actually deceptively easy. If we have M lanes and M^K horses,
finding the top two requires the following steps.
- Finding the fastest horse.
- Finding the 2^{nd} fastest.
Since unless we know the fastest, we cannot find the 2^{nd} fastest, it is seen that the 2^{nd} step must necessarily complete after the first. Among M^K horses, finding the fastest is easy - race them M at a time, and the winners move on. Since M^K horses are there and each race eliminates M-1 horses (since only one horse moves on), the required number of races for this part is (M^K-1)/(M-1). No race will have less than M horses, so the solution must be optimal.
Now for the 2^{nd} fastest, we need to compare every horse that came 2^{nd} in a race the fastest won. Clearly there will be K such horses. To find the fastest of these we just need ceiling((K-1)/(M-1)) races.
So the answer is (M^K-1)/(M-1) + ceiling((K-1)/(M-1)).
Note: In general, to implement the ceiling function easily while coding, you can use the fact that ceiling(x/y) = floor((x-1)/y)+1.
Code in Python: Due to no limit on integer length, we can directly find the answer and apply modulo 10^9+7
Code in C++: Must do it stepwise due to storage constraints, but it is faster.
Also, as illustrated in this C++ code, without running the loop to calculate 1+M+M^2+...+M^(k-1), you can directly calculate (M^K-1)/(M-1) by calculating the modular inverse of M-1 under modulo 10^9+7 using Fermat’s Little Theorem. Both solutions would pass though.