×

# Help in: Hackerearth November Circuits: Fredo is in Hurry

 0 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 115●1●8 accept rate: 0%

 5 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 $f-1$. Thus, to reach floor number $f$ total time taken is $1+2+3+...+f = \frac{f(f+1)}{2}$. Elevator takes 1 unit time to go from any floor to it's neighbouring floors. Thus, time taken by the elevator to reach a certain floor while descending is $N-f$. 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 N-x$$ 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(N-x)$. A corner case arises when $N=1$, as not taking the elevator is quicker than taking it. Just climbing one floor is 1 unit whereas waiting for the elevator would take 2 units of time. Solution in Python: here answered 28 Nov '16, 01:59 6★meooow ♦ 6.9k●7●17 accept rate: 48% 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) meooow ♦6★
 0 your code runs in O(n) and n is very large.So it won't pass. Here you can use binary search to determine the solution. answered 27 Nov '16, 21:03 4★lakh 139●5 accept rate: 23%

Here is my code:

# include<bits stdc++.h="">

using namespace std;

# define mo 1000000007

int 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(n-q>=p) { lo=p+1; ans=p; } else { hi=p-1; } } ll r1=n-ans; ll p5=(ans(ans+1))/2; r1+=p5; ll f1=n-p5; r1+=f1-ans; cout<<r1<<"\n"; } }

4★lakh
1395
accept rate: 23%

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=n-mid; if(temp<=el && (temp+mid+1)>=el) { long long int ans=(temp+el-temp+el); printf("%lld\n",ans); break; } else { if(temp>el) h=mid-1; else l=mid+1; }

}
}
}

311
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×921
×763
×382
×12

question asked: 27 Nov '16, 20:39

question was seen: 1,318 times

last updated: 14 Apr '17, 18:30