# PROJOVER

Author : `fangahawk`, `akcube`
Testers: Multiple, see announcement
Editorialist: `fangahawk`

Medium

Binary Search

# Problem

You have to find the minimum length possible of the segments that can be used to cover all the days given.

Pastebin

# Quick Explanation

Spoiler

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.

# Explanation

Step 1

There is a minor mistake in the binary search.

Step 2

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.

Step 3

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

\dots

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.

Since `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.