Testers: Multiple, see announcement
You have to find the minimum length possible of the segments that can be used to cover all the days given.
Buggy code plain text
There is an error in the binary search, since the while loop’s condition should be
low <= high, therefore the while loop won’t check if the answer is possible on the last iteration.
There is a minor mistake in the binary search.
The condition of the binary search is
low < high instead of
low <= high, therefore the buggy code will give an incorrect output when the answer is at
mid = low = high, which is the last iteration of a correctly written binary search.
To find a simple hack case, you can try to find the minimum answer which this binary search would fail to check. You can either try calculating it manually on paper, or just write a simple script.
Values of high, mid through the iterations, when the answer is minimal:
high = 300,000,000, mid = 150,000,000
high = 149,999,999, mid = 75,000,000
high = 16, mid = 8
high = 7, mid = 4
high = 3, mid = 2
high = 1, mid = 1
(You cannot simply hack the buggy code by making a test case with the actual answer as 1, since the number of projects have to be less than the number of vacation days)
We can see that in the second last iteration, high = 3.
If there is a testcase in which the answer is 3, and we get low to be 3 in the last iteration, the answer wouldn’t be updated to 3 since
low = high , and the incorrect binary search would terminate an iteration too early.
At high = 7, mid = 4, the variable
ans is updated to 4. In the next iteration high = 3, mid = 2, the
verify function would return false, hence we’d update the value to
low = mid + 1 which would give low a value of 3.
low = high, the binary search terminates, hence we aren’t able to verify if projects of length 3 would work. Hence, the answer we output is 4, which is incorrect.
Hack Case Example:
4 2 1 2 3 6
Here, we can clearly see that the answer is 3, but the buggy code will output 4, since the binary search will terminate before it verifies that 3 is a better answer.