Subtask 1:
Always $ Q> = T $ here. So by asking $ T $ questions, it can be found out which hours are classes and which hours are not. Then the result can be found by running a linear loop.

Subtask 2:
Free time, like class time, can be considered to have a range of $ [t_1, t_2]$ where free time starts at $ t_1$- hour and ends at $ t_2 $ - hour. If we can find out the range of all such free time, then the maximum length of the ranges is our result.

Property 1: If there are no classes in the $ [l, r] $range, then free time in this range will be $ = (r-l + 1) $ hours.
Property 2:
If there are only classes in range $ [l, r] $, then the free time in this range will be $ = 0$ hours.

Now if we are in the $ t_i $-th hour and that is class time, then it is very easy to find out in which hour this class ends by conducting a binary search using property 2. As long as the class time is over, the next hour will be free time.
What you need to do if $ t_i $ -th hour is free time is home task ;).

In this way, we can easily find out all the ranges of class time, free time from the $1^{st}$ hours to $T$ hour through binary search. Since it takes a binary search to find out the beginning and ending hours of each class, the total number of questions required will be $\leq 2 \times N \times log_2(T) $, which is within the query range of $5 \times 10^4$.

Subtask 3:
The solution of Subtask 3 is basically the optimization of the solution of Subtask 2. When we were conducting the binary search in subtask 2, we did not use the information obtained from one binary search in any other binary search. Now we will use it. In this subtask, we will ask all the questions in this format $ [1, t]$, that is to say, we'll ask from $1^{st} $ hour to $t$ - th hour - what is the total free time. We will understand the reason after a while.

Property 3: If Total free time in the range $ [1, t_1-1] $ is $ T_1 $ hours and total free time in the range $ [1, t_2] $ is $T_2 $ hours, total free time in the range $[t_1, t_2]$ will be $ (T_2-T_1) $ hours, where $1 < t_1 \leq t_2 \leq T$.

Suppose, by calculating the class time, free time from $ 1^{st} $ hours, we are now in the $ t_i $ - th hour. This means that we also know the total free time in the range $[1, t_i-1]$.

Suppose, $ t_i $ - th hour is free time, and the total free time in the range $ [1, t_j] $ has already been found from one of the previous binary searches, where $ t_j> t_i $. Then we can find out the free time in the range $ [t_i, t_j]$ without asking any extra questions using property 3.

If this free time is $ (t_j-t_i + 1)$, then it means $ [t_i, t_j] $ range is completely free time and we can find where the free time ends after $t_j$ hour. And if the free time is not $ (t_j-t_i + 1) $ hours, it means there is class time somewhere in the range of $ [t_i, t_j] $. That is to say, the free time in the $t_i $- th hour will end within the $ [t_i, t_j]$ range. So we will look for that end hour within this range.
What to do if hour $ t_i $ is class time is homework: D.

In this way, by using the information obtained from the previous binary searches, we can shorten the ranges to run the next binary searches. Now the question is, how much will the total number of questions be reduced in this way?

It will take $ \log_2 (T) $ questions to find out in which hour the first class starts from. After minimizing the range in the above rule, the length of the largest range to run the next binary search will be $ \frac {T}{2} $. The number of such lengths can be maximum $2$ (because $2 \times \frac{T}{2} = T$). Then,$2\times \log_2(\frac{T}{2})$ more questions are needed. As we proceed, it is observed that, the total number of questions needed is = $\log_2(T)+2\times \log_2(\frac{T}{2})+4\times \log_2(\frac{T}{4})+.....+k\times \log_2(\frac{T}{k})$, where $k = ceil(\log_2(2\times N))$ .

The number of questions required is less than $4.3\times 10^4$. A more accurate calculation shows that the number of questions will never be more than $41843$, but less if you are careful.

[P.S: Modified sparse segment tree can also be used to solve this problem.]

Statistics

50% Solution Ratio
ShadowMeEarliest, Mar '21
nusuBotFastest, 0.1s
Yasir_ArafatLightest, 3.2 MB
pathanShortest, 1573B
Toph uses cookies. By continuing you agree to our Cookie Policy.