Since the contest is over, I am asking it now. Here's the link to the question: Fredo is in a Hurry And here's my implementation: link The above code gets successfully compiled and passes the custom test cases on the compiler provided by hackerearth but when I submit the same, not a single test case is passed. I want to know the logic behind this problem. asked 27 Nov '16, 20:39

Although binary search can solve this problem, there is an $O(1)$ solution if you think about this mathematically. If he uses staircase, he takes $f$ amount of time to reach floor $f$ from floor $f1$. Elevator takes 1 unit time to go from any floor to it's neighbouring floors. Now, from the problem it is clear that catching the elevator on its way down and then riding it to the top is the quicker than climbing to the top. However waiting too long at some floor $x$ is also not a good idea if it is possible to reach floor $x+1$ by the time the elevator reaches floor $x+1$, as it wastes 2 units of time. So our aim is to climb the stairs to the maximum floor possible without missing the elevator. Which amounts to finding the largest $x$ for which $$ \frac{x(x+1)}{2} \le Nx$$ This is a quadratic inequality, solving which we get the maximum integer value of $x$ as $$ x = \bigg\lfloor\frac{3 + \sqrt{9+8N}}{2}\bigg\rfloor $$ The total time taken is the time taken for the elevator to come to this floor $x$ and go up again, which is $2(Nx)$. Solution in Python: here answered 28 Nov '16, 01:59
Very well explained! 1 thing I would like to ask is how to come up with such mathematical proof like answers? I know practice is the key but still I would like to know :)
(28 Nov '16, 17:10)
2
There is no particular way I have, although I generally read a problem and try to simplify it as much as I can, usually sitting with a pen and scribbling what goes through my mind. Maybe you can try that :)
(29 Nov '16, 07:26)

Here is my code: include<bits stdc++.h="">using namespace std; define ll long long intdefine mo 1000000007int main() { ll t,i,j,k,n; cin>>t; while(t) { cin>>n; if(n==1) { cout<<1<<"\n"; continue; } ll lo=0,hi=n; ll ans; while(lo<=hi) { ll mid=(lo+hi)>>1; ll p=mid; ll q=(p(p+1))/2; if(nq>=p) { lo=p+1; ans=p; } else { hi=p1; } } ll r1=nans; ll p5=(ans(ans+1))/2; r1+=p5; ll f1=np5; r1+=f1ans; cout<<r1<<"\n"; } } answered 27 Nov '16, 21:06

Here's my solution for Fredo is in Hurry!(using Binary Search) include <stdio.h>int main(void) { // your code goes here int t;scanf("%d",&t); while(t) { long long int n;scanf("%lld",&n); long long int l=0,h=n,mid; if (n==1) printf("1\n"); else{ while(l<=h) { mid=(h+l)/2; long long int temp=(mid*(mid+1))/2; long long int el=nmid; if(temp<=el && (temp+mid+1)>=el) { long long int ans=(temp+eltemp+el); printf("%lld\n",ans); break; } else { if(temp>el) h=mid1; else l=mid+1; }
answered 28 Nov '16, 00:10
