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

×

How to solve toffee boxes problem ?

0
2

I have seen this problem recently and it was asked in directi hiring challenge.

You have N toffee packets, each containing different number of toffees. The number of toffees contained in the ith packet is denoted by ci. You need to put these toffee packets in M boxes such that each box contains at least one toffee packet, and the maximum number of toffees in a box is minimum.

You can only choose consecutive toffee packets to put in a box.

Input

The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains two space separated integers N, M denoting the number of toffee packets and the number of boxes respectively. The second line of each test case contains N space separated integers c1, c2, ..., cN where ci denotes the number of the toffees in the ith toffee packet.

Output

For each test case, output a single line containing the maximum number of toffees in a box. Also, output -1 if such an assignment of toffee packets to boxes is not possible.

Constraints

1 ≤ T ≤ 20 1 ≤ N,K ≤ 100000 1 ≤ ci ≤ 1000

Example

Input: 1 4 2 10 3 5 7

Output: 13

Explanation

Below are the possible assignments of toffee packets to boxes.

10 [3 5 7] 10 3 [5 7] 10 3 5 [7] For minimizing the maximum number of toffees in a box, we choose the second assignment, and hence the output should be 13

I am not able to get any idea how to solve this.Please suggest a solution so that i can understand.

asked 28 Jul '16, 11:50

anu1234's gravatar image

1★anu1234
11431018
accept rate: 0%


Apply binary search over the search space. Here Ci <= 10^3, so the highest value which can be the answer is high = (10^5 * 10^3 = 10^8)..Similarilly, lower bound can be 0..Now apply binary search over this space and each time go to left or right of mid depending upoun if a combination is possible with the given constraints. Each possibility can be verified in o(n) time and binary search will not ask for answers for > log(10^8) possibilites..thus the complexity becomes O(n*logn) per test case

link

answered 28 Jul '16, 12:28

sandeep9's gravatar image

3★sandeep9
4782827
accept rate: 4%

edited 28 Jul '16, 12:29

As you said "Each possibility can be verified in o(n) time". How this is the problem? I got stuck here.

(28 Jul '16, 15:47) anu12341★

Say for your test case we need to pack(10,3,5,7) in 2 boxes..for any possibility say k = 10, we will start picking toffees from left and fill each box(in this case 2) until it can be filled with <= 10 toffee,after processing all toffees,if a box remained empty or there are toffees left but our bags are already full then it implies that we cannot have 10 as our answer..so we will then check for values > 10..and so on..similarilly, if at sometime the configuration is possible we will search for lower values than our current value..

(28 Jul '16, 16:34) sandeep93★

ok i got your idea , do you think this solution will pass in 1 second time limit ?

(29 Jul '16, 09:48) anu12341★

yes,much less than that

(29 Jul '16, 21:31) sandeep93★

ok thank you

(30 Jul '16, 09:33) anu12341★
-3

10 3 5 7 [57]

link

answered 28 Jul '16, 12:16

balaji_goud's gravatar image

0★balaji_goud
6
accept rate: 0%

-3

Thanks sandeep bro, for reply. +1.. its what exactly I applied for hotstar too. It works. Thanks again for the reply.

link

answered 28 Jul '16, 15:00

noor7300's gravatar image

0★noor7300
6
accept rate: 0%

please do not spam

(28 Jul '16, 16:06) anu12341★
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:

×2,718
×61

question asked: 28 Jul '16, 11:50

question was seen: 4,535 times

last updated: 30 Jul '16, 09:33