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

×

BITMASK3 - Editorial

Problem Link:

Practice
Contest

Difficulty:

Easy-Medium

Prerequisites:

Binary Search

Problem:

Find the maximum number x for which the sum of x natural numbers don't exceeds the litres of water available.

Explanation:

Given that the first bucket has a capacity of 1 litre, second bucket has capacity of 2 litres and so on. So we just need the maximum number x so that $1+2+3+....+x <=n$, where n is the litres of the water available. Thus, problem is a searching problem, we are just searching for the required x.

First approach is we can use linear search to find the value of x but it will exceed the time limit. So, we have to think of a more efficient searching approach.

Next approach is to use the binary search as it is very efficient and very well within the time limit of the problem.

Solution:

Author's solution can be found here.

asked 11 May '17, 08:24

hsagarthegr8's gravatar image

2★hsagarthegr8
162
accept rate: 0%

edited 29 May '17, 14:15

admin's gravatar image

0★admin ♦♦
19.6k349497539


Why can't we just use the formula for Sum of first n natural numbers? (n*(n+1))/2 = N

This was mine, I don't know why I was getting TLE.

I mean, I'm okay with getting a wrong answer (I just re-read the question and saw the line, "The bucket will be considered filled if it has atleast 1 litre in it.") But why am I getting a TLE? Is the sqrt() function that heavy/slow?

link

answered 11 May '17, 11:27

arvindpunk's gravatar image

2★arvindpunk
422
accept rate: 0%

It is because the problem is not that easy. The time limit of the problem is very less. So you can't use the linear approach. The problem was designed that way.

(12 May '17, 14:35) hsagarthegr82★

import math for t in range(input()): s=int(raw_input()) a=1 b=1 c=-2s d=b2-4ac if d>0: x1=-b+math.sqrt(d) x1=x1/2a print int(math.ceil(x1))

link

answered 11 May '17, 15:40

srvshrm's gravatar image

2★srvshrm
1
accept rate: 0%

I based my solution on this editorial but I got a WA response.
Can someone point out the mistake in my code.

And I am trying to understand the approach used in the following solutions... singh_8 and sayan009 but cant get it...

link

answered 20 May '17, 09:15

goof_expert's gravatar image

2★goof_expert
312
accept rate: 0%

@goof_expert

Hi. See in line 22, you should be checking for <=N (you did <N instead). + in line 22's "if" satisfies, i.e mid * (mid-1) / 2 <= N, then the result var should be set to mid-1 (you did mid instead).

Hope it helps.

link

answered 29 May '17, 01:34

sandeepg97's gravatar image

5★sandeepg97
1011
accept rate: 0%

I used the formula for sum of first n natural numbers and got a WA, but a simple linear approach for summing up the first n natural numbers gave AC, instead of TLE.

link

answered 28 Feb, 19:18

piyush4342's gravatar image

4★piyush4342
1
accept rate: 0%

I m very pleased to discover this page. I want to thank you for your time just for this wonderful read !! I definitely loved every little bit of it and I have you bookmarked to check out new things on your blog.And new code on programming that you shared with us in future.Essay Writing Service very thankful to you for this post.

link

answered 02 Mar, 11:33

james_jhon2's gravatar image

0★james_jhon2
1
accept rate: 0%

You can use the formula (n*(n+1))/2=N and convert them into a quadratic equation to solve the problem. You can check my solution for this problem link text Here i use sheree dharacharya formula to find the solution. And it accepted in one go.

link

answered 03 Mar, 11:53

rishabh1322's gravatar image

1★rishabh1322
252
accept rate: 0%

edited 03 Mar, 11:54

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:

×15,119
×978
×24
×1

question asked: 11 May '17, 08:24

question was seen: 1,119 times

last updated: 09 Mar, 12:34