E - Logs (Atcoder ABC 174)

i am not able to understand what the problem wants?
can anyone explain it to me?
Link: https://atcoder.jp/contests/abc174/tasks/abc174_e

you need to cut the given logs upto k times. When you cut the logs their new size become L - t & t where t is the length of cut you made … and then you cut them in such a way that
maximum length of a log after cutting them upto k times (probably 0 times ) is minimum…
for exam … if a log of length 5 is given and you can cut it 1 times…
then for example
if you don’t cut max length is 5 …
if you make cut at length 1 the new sizes will be 1 and 4 and the max length of new logs is 4 …
while if you make cut at 2 the new sizes will be 2 and 3 and the max length is 3 here …
clearly third option will give minimum of all maximum length possible …

Solution hint
    • The solution is preety simple and is similar to standard binary search application

The problem wants you to cut the logs optimally, so that after u use all the k cuts, U have many logs of different sizes.Among all such possibilities ,they want the minimum size of longest log among all logs you have in each possibility,

take this example where you have 3 logs of size 1,1,9 and k=2;
so ,after 2 cuts u can have many possibilities like cut both the 1 size log once
so u have 0.5,0.5,0.5,0.5,9
the longest here is 9,
but if u cut optimally using 2 on the log of length 9, u get 1,1,3,3,3
the longest here is 3,which is the minimum possible value.
And they want this minimum,hope you understand this now.

Solution

For solving this ,you do a binary search on values of minimum, until you get the minimum value possible. O(n *log(n) ) solution.

1 Like

Can you wrap your solutions suggestions with Hide Details? He’d probably want to attempt it later. He just wanted a clarification on the questions.

3 Likes

I didn’t knew that feature existed, done now.

thank you everyone