PROJOVER - Editorial

PROJOVER

Contest
Practice

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

Difficulty

Medium

Prerequisites

Binary Search

Problem

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

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.