PROBLEM LINK:
Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
Chef has N (6 \leq N \leq 100) distinct numbers. You may ask at most Q=4+N/2 queries, each giving Chef indices i_1,\dots,i_5 and Chef will give you 3-rd and 4-th largest numbers among these 5. You have to find the largest number.
QUICK EXPLANATION:
Solve N=6 and N=7 manually in at most 7 queries. While N>7, strike out results of queries until you have N \leq 7.
EXPLANATION:
Let’s start with solving N=6. Under these constraints we may ask any possible subset of 5 elements. Assume that elements are sorted. Let’s see what elements we’ll be returned in case if we ask all elements but:
- 1-st: 4 th and 5 th
- 2-nd: 4 th and 5 th
- 3-rd: 4 th and 5 th
- 4-th: 3 rd and 5 th
- 5-th: 3 rd and 4 th
- 6-th: 3 rd and 4 th
Thus you have three possible options: (4,5) occuring thrice, (3,5) occuring once and (3,4) occuring twice. This allow you to determine 5-th element (it occurs total of 4 times while 3-rd occurs 3 times and 4-th occurs 5 times) and output the other element which gave you answer (3,4).
Now what to do if N>6? Well, if you ask elements 1,2,\dots,5 and obtain some answer you may just strike out of consideration the resulting numbers. You’ll have to do it at most (N-6)/2 times which will leave you with either N=6 or N=7 and 7 queries. As we already know it’s enough to resolve case N=6. What about case N=7? While solving N=6 we happened to efficiently find out places of 5-th and 6-th elements. Now for N=7 we may do the same for first 6 elements in 6 queries and with the last query to ask about any quintuple containing these elements and the one remaining element. If the result will be these 5-th and 6-th elements then the answer is last element, otherwise it’s 6-th element.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.