Sumanto's blog

By Sumanto, 8 months 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

»
8 months ago, # |
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)

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wonderful Explaination!

  • »
    »
    6 weeks ago, # ^ |
      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?

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      The reason is $$$x_n+x_1+..+x_{k-1}>=x_1+x_2+...+x_k$$$; and $$$x_1+..+x_{n-1} >= 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$$$.