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.
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.
Here is my code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#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";
}
}
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;
}
}
}
}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
This is a quadratic inequality, solving which we get the maximum integer value of x as
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
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 
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