Problem - Click Here
I am not able to get AC in this. I am getting WA on 3 test cases.
So i landed on a github solution in which i can’t understand why that solution works.
A Github Solution - Click Here
I didn’t understood when (m <= (s - m) ) print s , i understood the rest of code but not getting why this line gets to AC.
Can anyone explain it or if you have your own approach you are most welcome.
Thanks in Advance!
Anybody Please help!
Can Anyone Help Please.I am Stuck!
Come up with an “optimal strategy” for them to read books to minimize the time
Well, you submitted something and got a wrong answer, what is your solution?
I assume by “elaborate” you mean “spoonfeed”
Bro i have already done much thinking and paperwork thats why i asked.
If you insist. The optimal strategy is to have the first person start from the shortest book and read in ascending order and have the second person start from the longest book, then go to the shortest book and read in ascending order.
this is what i am doing i think
this should be descending order.Right?
No
I will see to it Thanks
Can anybody prove that why is “max(2*tn, sum)” the answer to this problem? [Where sum=t1+t2+…tn and tn is the largest of all t’s]
There are two cases in this problem:
(Sort the input in increasing order)
(Considering 1-Based indexing)
Case 1:
If Sum of elements till [n-1]th element is less than the nth element then the most optimal answer=2*(nth element).
Why?
Consider the array 1 2 3 4 11
Not Optimal Approach:
Suppose Two Guys are A and B
1.A will read 1 and at the same time B will read 2 (B will not waste time waiting for A to Finish 1 so he is reading 2 to save time).
A 1
B 2
2.As A will finish 1 then he will not wait for 2 because B is still reading it.So A will read 3.
A 1 3
B 2
3.When B finishes 2 then he will not wait for 3 because A is reading it so B will read 4.
A 1 3
B 2 4
4.As A Finishes 3, he will not wait for 4 as B is reading it, So A will Read 11.
A 1 3 11
B 2 4
5.Meanwhile,B Finishes 4 , Now instead of waiting for 11 he will read his pending books (1 and 3) .
A 1 3 11
B 2 4 1 3
6.As B finishes reading 1 and 3 then he is left with only one book i.e 11 which A is reading,So he Waits for A to finish 11 .
A 1 3 11 [A will finish reading 11 at 15th time]
B 2 4 1 3 [B will wait for 11 for 5 minutes because he completed remaining
books at 10th time ]
7.When A finishes 11 , B will read 11 with a delay of 5 minutes.Meanwhile A will finish his Pending Books (2 and 4 ) as B is not reading these books right now.
A 1 3 11 2 4
B 2 4 1 3 11 [So B's time of reading all books is 2+4+1+3+11+delay=26 (delay-
5 Minutes) ]
So Total Time taken to read books by both A and B is 26 Minutes.
Optimal Approach:
1.A will read 11,At the same time B will read 1 2 3 4.
Because 1+2+3+4=10 and 10<11
A 11
B 1 2 3 4
2.Now B will read 11 and A will read 1 2 3 4
A 11 1 2 3 4
B 1 2 3 4 11
No delay - So total Time taken is 22 => (11*2) => (maximum time *2)
Case 2:
If Sum of elements till [n-1]th element is greater than the nth element then the most optimal answer=Sum of all elements.
Consider Case - 1 2 3 5 10
Non Optimal Approach is same as Case 1
Optimal Approach:
1.A will read 10, at the same time B will read 1 2 3.
A 10 [10 Minutes]
B 1 2 3 [6 Minutes]
2.When B finishes 1 2 3 he reads 5 and A is still reading 10.
A 10 [10 minutes]
B 1 2 3 5 [11 Minutes]
3.When A finishes 10 He reads 1 2 3 as B as already read these books and B is not reading these books right now so A can read 1 2 3.
A 10 1 2 3 [16 Minutes]
B 1 2 3 5 [11 Minutes]
4.When B finish 5 He will read his last pending book 10 , He can read it now because A is not reading 10 right now and A is busy reading 1 2 3.
A 10 1 2 3 [16 Minutes]
B 1 2 3 5 10 [21 Minutes]
5.When A finish reading 1 2 3 He will read his last pending book 5 , He can read it now because B is not reading 5 right now and B is busy reading 10.
A 10 1 2 3 5 Both 21 Minutes
B 1 2 3 5 10
No delay- So total Time taken is 21 => (Sum of all times).
General Strategy for Case 2:
A should read like this:
n 1 2 3 - - - n-1
B should read like this:
1 2 3- - - - - n
I Hope You got the difference between Optimal approach and Non Optimal Approach.
My AC Code - Click Here
i don’t think this was intended soution, if it was it shouldn’t have been sorting and searching?
can anyone explain how to solve this problem with sorting and searching?
I Approached This Problem in many ways but i failed.In My Opinion This Is the Only optimal Way To approach this problem.
yes i also think so, but i am very poor at solution building 