Indian Computing Olympiad

Searching→Off with the Head (IOITC 2003)

The king has a large collection of ministers, all of whom he believes to be corrupt. To teach them a lesson, he decides to behead the most corrupt minister. To do this, he wants the prime minister to conduct raids on all the ministers' houses and identify the most wealthy one. The most wealthy minister will be declared the most corrupt and beheaded.

There are 1,000,000 ministers and the king want the most corrupt minister to be identified in 200 days. The prime minister cannot raid raid all the ministers' houses within this time because he has only three raiding teams at his disposal and each team takes a full day to complete a raid. Thus he can raid only three ministers' houses each day.

Instead, the prime minister decides to adopt a different strategy. When the king meets the ministers, they all sit around a big table. The prime minister decides that it is sufficient to find one minister whose wealth is larger than that of his neighbours. The king can then be convinced that this minister is the most corrupt.

Devise a strategy for the prime minister to identify a minister whose wealth is higher than that of his neighbours, raiding one minister at one time.

Probe three equally spaced points around the circle. Delete the arc between the two smallest values and focus on the rest of the circle which is a segment with three values that form a "tent".

                 v2
                  |
        v1        |        v3
         |        |         |
         |        |         |
         --------------------
      

Now probe the midpoints between (v1,v2) and (v2,v3), say v4 and v5, respectively. Depending on the values here, you will find a smaller tent.

Case 1: Shrink the tent to (v4,v2,v5)

                 v2
             v4   |   v5
        v1   |    |    |   v3
         |   |    |    |    |
         |   |    |    |    |
         --------------------
      

Case 2: Shrink the tent to (v1,v4,v2)

             v4
             |
             |   v2
             |    |   v5
        v1   |    |    |   v3
         |   |    |    |    |
         |   |    |    |    |
         --------------------
      

Case 3: Shrink the tent to (v2,v5,v3)

                      v5
                       |
                 v2    |
             v4   |    |
        v1   |    |    |   v3
         |   |    |    |    |
         |   |    |    |    |
         --------------------
      

Repeat this till the tent consists of three consective positions.

Note: When presented as a programming task, you are given a library funcion raid that is to be called in order to conduct a raid.

---