sahal's blog

Help Needed : CSES PROBLEMSET — Reading Books
By sahal, history, 5 years ago, In English

Can anyone help me solving this problem? CSES PROBLEMSET — Reading Books

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

Comments Comments (30)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

One hint: Look at the last book. If the last book is greater than the sum of all other books, what does this mean?

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

    If the last book is greater that means the total time is the time of last book*2

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

    But I couldn't figure out how to solve the rest of the part of the problem.

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

    i don't understand

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

      First sort the based on the time it takes to read that book. Suppose that Kotivalo starts reading the books which takes minimum time, and Justiina starts reading books that takes maximum time. If Kotivalo completes reading n-1 books and Justiina has not yet finished the nth book finished, then Kotivalo has to wait till Justiina finishes that.

      So, after Justiina finishes the book Kotivalo starts reading it and will take the same time again (time to read the last book) and in lesser or equal time Justiina would have finished the rest n-1 books. Hence, the total time would be twice of reading the last book when time of reading the last book is greater than or equal to total time of reading the n-1 books.

      In rest of the cases total time would be summation of reading all the books.

      This is my submission.

      Hope this helps.

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

        Why is the total time in other cases summation of reading all the books?

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

          In all the other cases, none of them will have to wait for a book to read (there will always be atleast one unread book that no one is reading at that time).

          Thus, there will be no waiting time and hence time required will be equal to the summation of time of every single book.

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was also solving this Problem.I am Getting WA in 3 test cases.

one of the test case is:

5
1000 1000 1000 1000 1000

In my opinion answer should be 6000 but correct output given in the website is 5000.

Can anyone clarify why the answer is 5000 for this test case and not 6000

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    First person can read in order 1,2,3,4,5 and second in 2,3,4,5,1.

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

      But this approach is not giving correct answer on each test case. Can you tell the correct approach for this

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

        Here k will start reading book of 8 minutes while reading this j will read book of 2 and 3 minutes . So it will take 8 minutes as both are reading at the same time then this process will reversed . So it takes totak 8+8 = 16 minutes. Here largest number is greater than the summation of all other numbers so it takes largest number + largest number time.

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

          Bro this much i know.But i am not able to solve ahead of it

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

            Ok let's take a look at this 2 2 3 here k will start reading book of 2 minutes that time j will reading book of 3 minutes now after 2 minutes k will start reading another book of 2 minutes it will take him 4 minutes to read this 2 books now look at j it will take him 3 minutes to read that book then he will start reading book no 1 which have been finished by k .It will take j 5 minutes complete that.Now again look at k after 4 minutes k will start reading book of 3 minutes and he will complete all in 7 minutes at the same time j will also complete reading the book no 2 in 7 minutes.So actually it will take just 7 minutes in total.Sorry for my poor english ang long explanation.

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

              Thanks for the explaination.

              Can you make me understand a part of this 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.

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

                There are 2 cases 1.If summation of all other values is lesser than the max value then the total time is 2*max value 2.If max value is not greater than summation of all other values then the total time is summation of all values. So here this line just checking the 2nd condition and printing s.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
                  If max value is not greater than summation of all other values then the total time is summation of all values. So here this line just checking the 2nd condition and printing s.

                  My Question was why that line works?Whats the reason for this.I know the meaning but don't know the reason behind it.

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

                  Actually i have taken this as an observation because we can see that for any case it works like my example 2 2 3. I didn't try to find any mathematical proof.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  Can you explain in this test case how reading is taking place by both:

                  10
1 2 3 4 5 6 9 8 7 16
                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Order for k 1 2 3 4 5 6 9 8 7 10 and at the same time order for j 10 1 2 3 4 5 6 9 8 7

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

                  Bro According to your approach answer is 78 but the correct answer is 61. So,this is not the right way, i think

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

                  According to my approach the result is 61 because the answer is summation of all values.

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

                  According to your approach its coming to be- 16+2+3+4+5+6+9+9+8+16=78 Right?

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

                  No man there's may be some misunderstanding.I have explained that for 2 2 3 the answer is 7.It comes with summation of all the values , here it goes same for your last example i have said the index number of the books for both k and j.After sorting k will read from 1 to n and j will read n , 1 to n-1.Both will read simultaneously.So it takes the summation.

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

deleted

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

    Yeah, I struggled t00 . If n=3 and values are 2 2 3 think what will be total time? Btw , I have seen the solution , then got the point .

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

      Is solution available before solving?

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

The min time is the maximum of reading alls books (sum of all books), and two times the longest book. Since the two children must read that longest book one after the other.

A visualization of the problem can be the books sorted by length. So one kid starts with the smallest, one with the longest. If there is no overlap of any book, then they can simply read all books. If there is overlap, then it is because the longest book is longer than the half of all books. And then ans is obviously the longest book times two.

→ Reply