Answers to: BITMASK3 - Editorialhttps://discuss.codechef.com/questions/97868/bitmask3-editorial<h1>Problem Link:</h1>
<p><a href="https://www.codechef.com/problems/BITMASK3/">Practice</a><br>
<a href="https://www.codechef.com/BITM2017/problems/BITMASK3/">Contest</a>
</p><h1>Difficulty:</h1>
Easy-Medium
<h1>Prerequisites:</h1>
Binary Search
<h1>Problem:</h1>
Find the maximum number <b>x</b> for which the sum of <b>x</b> natural numbers don't exceeds the litres of water available.
<h1>Explanation:</h1>
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 <b>x</b> so that $1+2+3+....+x <=n$, where <b>n</b> is the litres of the water available. Thus, problem is a searching problem, we are just searching for the required <b>x</b>.<p></p>
<p>First approach is we can use linear search to find the value of <b>x</b> but it will exceed the time limit. So, we have to think of a more efficient searching approach. </p>
<p>Next approach is to use the binary search as it is very efficient and very well within the time limit of the problem.</p>
<h1>Solution:</h1>
<p>Author's solution can be found <a href="https://www.codechef.com/viewsolution/13438106">here</a>.</p>enSat, 03 Mar 2018 11:53:52 +0530Answer by rishabh1322https://discuss.codechef.com/questions/97868/bitmask3-editorial/123926<p>You can use the formula <strong>(n*(n+1))/2=N</strong> and convert them into a quadratic equation to solve the problem. You can check my solution for this problem <a href="https://www.codechef.com/viewsolution/17601462">link text</a>
Here i use sheree dharacharya formula to find the solution. And it accepted in one go.</p>rishabh1322Sat, 03 Mar 2018 11:53:52 +0530https://discuss.codechef.com/questions/97868/bitmask3-editorial/123926Answer by james_jhon2https://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial/123864<p>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.<a href="https://fullessayhelp.co.uk/">Essay Writing Service</a> very thankful to you for this post.</p>james_jhon2Fri, 02 Mar 2018 11:33:39 +0530https://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial/123864Answer by piyush4342https://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial/123786<p>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.</p>piyush4342Wed, 28 Feb 2018 19:18:53 +0530https://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial/123786Answer by sandeepg97https://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial/99435<p><a href="/users/33904/goof_expert">@goof_expert</a></p>
<p>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).</p>
<p>Hope it helps.</p>sandeepg97Mon, 29 May 2017 01:34:38 +0530https://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial/99435Answer by goof_experthttps://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial/98436<p>I based my solution on this editorial but I got a WA response.<br>
Can someone point out the mistake in <a href="https://www.codechef.com/viewsolution/13638918">my code</a>. </p>
<p>And I am trying to understand the approach used in the following solutions...
<a href="https://www.codechef.com/viewsolution/13638461">singh_8</a> and <a href="https://www.codechef.com/viewsolution/13569287">sayan009</a> but cant get it... </p>goof_expertSat, 20 May 2017 09:15:21 +0530https://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial/98436Comment by hsagarthegr8 on arvindpunk's answerhttps://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial#97889<p>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.</p>hsagarthegr8Fri, 12 May 2017 14:35:35 +0530https://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial#97889Answer by srvshrmhttps://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial/97877<p>import math
for t in range(input()):
s=int(raw_input())
a=1
b=1
c=-2<em>s
d=b</em><em>2-4</em>a<em>c
if d>0:
x1=-b+math.sqrt(d)
x1=x1/2</em>a
print int(math.ceil(x1))</p>srvshrmThu, 11 May 2017 15:40:32 +0530https://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial/97877Answer by arvindpunkhttps://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial/97871<p>Why can't we just use the formula for Sum of first n natural numbers? (n*(n+1))/2 = N</p>
<p><a href="https://www.codechef.com/viewsolution/13439765">This</a> was mine, I don't know why I was getting TLE.</p>
<p>I mean, I'm okay with getting a wrong answer (I just re-read the question and saw the line, <em>"The bucket will be considered filled if it has atleast 1 litre in it."</em>) But why am I getting a TLE? Is the sqrt() function <strong>that</strong> heavy/slow?</p>arvindpunkThu, 11 May 2017 11:27:14 +0530https://ipc.discuss.codechef.com/questions/97868/bitmask3-editorial/97871