COMAS - Editorial

PROBLEM LINK:

Div 1
Div 2
Practice

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.

RELATED PROBLEMS:

Author’s & Tester’s solutions aren’t having working(clickable) links

1 Like