You are not logged in. Please login at www.codechef.com to post your questions!

×

Editorial for Chef and Meatballs?

Do we have an editorial for Chef and Meatballs question which was a part of Dec18b Long Contest?

asked 22 Dec '18, 20:38

dipanshu_10297's gravatar image

4★dipanshu_10297
01
accept rate: 0%


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

link

answered 22 Dec '18, 20:58

masood786's gravatar image

4★masood786
1063
accept rate: 13%

edited 22 Dec '18, 21:02

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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