Do we have an editorial for Chef and Meatballs question which was a part of Dec18b Long Contest?
Here’s the outline of my approach.
First of all, notice that in each query the problem set size can be reduced by 2 (as the answer returned by the grader can never be a part of the final answer).
So, suppose we fill up n elements in a set (numbered from 1 to n).
Now, we query first (or any 5) elements of the set and delete the 2 numbers returned by the grader (effectively reducing the set size by 2.) (Note that we do not lose any information as we stiil have the meatiest meatball in our set.
So, if n is even, we keep doing this till the set size becomes 6. ( This would take (n-6)/2 queries).
On the other hand, if n is odd, we reduce the set size to 7 (costing us (n-7)/2 queries) and then we query another block of 5 elements and delete only one of the answers.
Total queries consumed (n-7)/2 + 1.
So now the problem reduces to finding out the meatiest meatball among a group of 6 meatballs.
This can be done in at most 4 queries in the worst case (which comprises of replacing one meatball with the other unused one and checking as to which group they belong to , i.e, upper or lower).
So the total number of queries if n is even is n/2 + 1 (more tight than the given constraints.
And for odd n, it is n/2 + 2
1 Like