Sumanto's blog

CSES PROBLEM:Reading Books...Need Help
By Sumanto, 6 years ago, In English

I was following the 12hr stream of tmwilliamlin168 solving 150 problems from CSES. In the problem https://cses.fi/problemset/task/1631/ , I did'nt understood why answer is max(sum of elements, 2*last element); (He doing the same problem at https://youtu.be/dZ_6MS14Mg4?t=5237 with Timestamp);

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it +6 Vote: I do not like it

First let's sort the array such as x1 <= x2 <=x_3......<=x_n First Case: 2*x_n>=sum x_n>= sum-x_n =(x_1+x_2+x_3...+x_(n-1)) , it is optimal that the first person will read the first n-1 books , he will finish first and wait until the second person read the last book , then the first person will read the last book and the other will read the remaining books , this will take in total 2*x_n . Second case: sum>=2*x_n x_n<=sum-x_n the first person will read the books in this order n 1 2 3 4 5 .... n-1 the second person will read the books in this order 1 2 ........ n we can easily prove that no book will be read in this time. this will take in total the sum of all elements so the answer=max(sum,2*x_n)

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I didn't understand second case. If first person reads in this order: "n 1 2 3 .... n-1" and second person reads in this order "1 2 3 ...n". How the times don't overlap?

    → Reply
    • »
      »
      »
      5 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      The reason is $$$x_n+x_1+..+x_{k-1} \gt =x_1+x_2+...+x_k$$$; and $$$x_1+..+x_{n-1} \gt = x_n.$$$ It means that the first person always can read the book $$$k$$$ after finishing the book $$$k-1$$$, since the second person already finished reading it. Also, the second inequality shows that when the second person wants to read the last book, this book is already available. So the minimum reading time in this case is $$$x_1+...+x_n$$$.

      → Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    thanks for wonderful explanation!

    how would it affect the solution if in place of 2 persons, there were k persons?

    → Reply
    • »
      »
      »
      5 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      sort the reading times ,WLOG Let x1<=x2<=...<=xn. If inequality x1+x2+...xn-1<(k-1)*xn holds then solution is k*xn else x1+x2+...+xn, Observe, this inequality is valid when k=2 as well.

      → Reply