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

×

MINEAT - Editorial

2
2

PROBLEM LINK:

Div1, Div2
Practice

Author: Praveen Dhinwa
Tester: Triveni Mahatha
Editorialist: Adarsh Kumar

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Binary search

PROBLEM:

You are given an array $A$ of $N$ integers. You need to find the smallest $K$ that satisfies this inequality; $\sum \limits_{i=1}^N \left \lceil \frac{A[i]}{K} \right \rceil \le H$, where $\left \lceil \right \rceil$ indicates the ceil function.

EXPLANATION:

According to the problem statement, Chef will need $\left \lceil \frac{A[i]}{K} \right \rceil$ hours to finish the $i^{th}$ pile. Hence, we need to find the smallest $K$ that satisfies this inequality; $\sum \limits_{i=1}^N \left \lceil \frac{A[i]}{K} \right \rceil \le H$.

subtask #1

Iterate over values of $K$ from $1$ to $MAX$ and break whenever you find the solution. Time complexity for the same will be $O(N.MAX)$, where $MAX$ is maximum element that can be present in the array.

subtask #2

For this subtask we need something better than brute-force. Hence, we will try to make some-observations first. Lets name the left side of our function as cost function. Observe that, our cost function is inversely proportional to $K$. Our cost function will decrease while $K$ increases. At some point it will become smaller than $H$. We need to find this point. Observe that, this problem has reduced to standard formulation of binary search problem. We just need to binary search on values of $K$ now and change the limits of $K$ according to the difference between our cost function and $H$. For more implementation details, you can have a look at attached solutions.

Time Complexity:

$O(N.log(MAX))$

AUTHOR'S AND TESTER'S SOLUTIONS

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 10 Mar, 07:31

adkroxx's gravatar image

7★adkroxx
306718
accept rate: 7%

edited 13 Mar, 15:05

admin's gravatar image

0★admin ♦♦
19.0k348495531


12next »

why can't I see the solution?? the links don't work

link

answered 12 Mar, 17:26

imsandy26's gravatar image

2★imsandy26
1
accept rate: 0%

Author's and Tester's solutions not opening!

link

answered 12 Mar, 18:20

vikram91's gravatar image

1★vikram91
185
accept rate: 0%

unable to see the solutions , bucket policy needs to be updated .

link

answered 12 Mar, 21:47

acodebreaker2's gravatar image

1★acodebreaker2
1.2k11
accept rate: 19%

I have a doubt. For the following test case:

5 7 9 3 8 10 5

The answer should be 6. So taking k=6, the above inequality will be calculated as following:

9/6 + 3/6 + 8/6 + 10/6 + 5/6 (Ceil of all the terms are added) 2 + 1 + 2 + 2 + 1 =8

Hour available is 7, so am I doing something. If there's any problem in logic, please point out the correct solution to above test case and logic.

Thanks

link

answered 12 Mar, 23:53

philomath_mht's gravatar image

2★philomath_mht
1
accept rate: 0%

@philomath_mht the ans. will be 8 as you can only divide maximum (7-5)=2 bunch of bananas and the minimum required bananas that should be eaten is 8. 9/8 + 3/8 + 8/8 + 10/8 + 5/8 = 2 + 1 + 1 + 2 + 1 = 7

link

answered 13 Mar, 02:06

mittal_ash7's gravatar image

2★mittal_ash7
01
accept rate: 0%

edited 13 Mar, 02:12

Simple binary search : Link to solution https://www.codechef.com/viewsolution/17582805

link

answered 13 Mar, 03:23

beginner_1111's gravatar image

3★beginner_1111
1618
accept rate: 15%

Can anyone tell last test case? My solution is https://www.codechef.com/viewsolution/17773507 Can anyone please point out the mistake in my code.

Edit: Saw the tester's solution. So basically my calculateHour function was a little different. Tester solution has something like this: for (i = 0; i <len;i++) { total+=(arr[i]+k-1)/k; } I tried it and my code got accepted now.

Whereas in my solution i had this: for (i = 0; i <len;i++) { if(arr[i]<=k) { total++; } else { total+=(arr[i]/k)+1; } }

What was the last test case that gave wrong answer verdict on my solution? Can anyone provide some help?

link

answered 13 Mar, 08:57

vbt_95's gravatar image

3★vbt_95
3285
accept rate: 22%

edited 13 Mar, 22:55

can anyone tell me what is the mistake?
https://www.codechef.com/viewsolution/17824477

link

answered 13 Mar, 20:22

dharmick's gravatar image

2★dharmick
1
accept rate: 0%

Change int to long long && float to double. Here's your modified solution :

https://www.codechef.com/viewsolution/17827412

@dharmick

link

answered 14 Mar, 03:13

i_love_nidhi_j's gravatar image

1★i_love_nidhi_j
11
accept rate: 0%

edited 14 Mar, 03:15

! Should have tried this. Was just too lazy to do it :p

link

answered 14 Mar, 09:08

harendrasingh's gravatar image

3★harendrasingh
381
accept rate: 10%

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:

×14,366
×1,398
×810
×264
×5

question asked: 10 Mar, 07:31

question was seen: 4,543 times

last updated: 21 Apr, 18:12