Codeforces Books Problem

binary-search
codeforces

#1

http://codeforces.com/contest/279/problem/B

Please explain the output.


#2

The output is the maximum no. of books the person can read!
Consider case 1:
You have t=5. Now if u start reading from book 1(i.e. one with t=3), you can only read 2 books(t=3,t=1) as total time for reading the books will be 4 units and then you can’t read next book as it costs 2 units of time and 4+2>5!!
So, you start with the second book and go till the end. This will make it possible to read 3 books(i.e. one with t=1,t=2 and t=1). This is the maximum no. of books the person can read provided the constraints.

Hope this helps :slight_smile:


#3

The question asks you to find the maximum number of consecutive books that Valera can read within the given time, t.

Formally, you have to find the length of longest subarray such that the sum of its elements <= t

This problem can be easily solved by using:

  1. Two - Pointer approach in O(N).
  2. Binary Search over the cumulative sum in O(N log N).

You can refer to my solutions if get stuck.

Two Pointer: http://codeforces.com/contest/279/submission/28493897

Binary Search: http://codeforces.com/contest/279/submission/28493182