You are not logged in. Please login at www.codechef.com to post your questions!

×

Codeforces Books Problem

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

Please explain the output.

asked 13 Jul '17, 09:19

osama_binladen's gravatar image

3★osama_binladen
35
accept rate: 0%


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

link

answered 13 Jul '17, 12:23

dishant_18's gravatar image

4★dishant_18
61419
accept rate: 12%

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

link

answered 13 Jul '17, 13:12

c_utkarsh's gravatar image

5★c_utkarsh
1.1k5
accept rate: 17%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,056
×688

question asked: 13 Jul '17, 09:19

question was seen: 1,207 times

last updated: 13 Jul '17, 13:12