Sumanto's blog

CSES PROBLEM:Reading Books...Need Help
By Sumanto, 4 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 (4)
| Write comment?
»
4 years 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)

→ Reply
  • »
    »
    4 years 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?

    → Reply
  • »
    »
    4 years ago, # ^ |
      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
    • »
      »
      »
      4 years ago, # ^ |
        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