×

# Editorial for Chef and Meatballs?

 0 Do we have an editorial for Chef and Meatballs question which was a part of Dec18b Long Contest? asked 22 Dec '18, 20:38 0●1 accept rate: 0%

 1 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 answered 22 Dec '18, 20:58 106●3 accept rate: 13%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×11

question asked: 22 Dec '18, 20:38

question was seen: 173 times

last updated: 22 Dec '18, 21:02