Блог пользователя Sumanto

CSES PROBLEM:Reading Books...Need Help
Автор Sumanto, 4 года назад, По-английски

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);

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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)

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thanks for wonderful explanation!

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить