Editorial for IOI '17 P4 - The Big Prize
Submitting an official solution before solving the problem yourself is a bannable offence.
In this subtask, we can find the diamond with a simple binary search.
Subtask 2, Solution 1
First, we query the first prizes in the line. These queries are sufficient to find at least one box containing a lollipop. When we find it, we can binary search to find all prizes that are more expensive than lollipops. This approach needs less than queries. More specifically, it requires queries.
Subtask 2, Solution 2
If we query boxes and () and both of them contain lollipops, we can find the number of boxes having more expensive prizes (than lollipops) in the boxes between and : Suppose Rambod tells there are boxes to the left of box that contain more expensive prizes. He also tells there are boxes to the left of box that contain more expensive prizes. Then, there are exactly boxes between the boxes and that contain more expensive prizes.
We consider the whole sequence of boxes as one segment. With a query of box , we break the segment into two segments: the boxes before, and the ones after (the boxes that are already queried are not in any segments). While doing binary search, we can track the number of boxes in each segment. If among our previous queries there are two boxes and with the above conditions to the right and to the left of a segment, we can ignore that segment and do not query that.
Subtask 2, Solution 3
While the previous solution can get full score of this task, we can further optimize it. The idea is that it is sufficient for the boxes and to have the same prize values to identify the boxes containing more expensive prizes between them. Further, we can sum the pair of values answered by Rambod for each box. Two boxes and contain equal prizes if the sum of answered values for box is equal to the sum of answered values for box . Hence there is no need to look specifically for lollipops: we do a normal binary search, and we do not continue binary searching in a segment if we find such boxes and that show there is no more expensive prize in that segment. A further improvement is to see if is equal to the number of identified prizes between the boxes and that are more expensive than the prizes in the boxes and , we can ignore any segment between this pair of boxes. This method, if implemented efficiently, needs at most queries.