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

×

Help in: Hackerearth November Circuits: Fredo is in Hurry

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

aniketsanadhya's gravatar image

1★aniketsanadhya
11518
accept rate: 0%


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

link

answered 28 Nov '16, 01:59

meooow's gravatar image

6★meooow ♦
6.9k717
accept rate: 48%

edited 30 Nov '16, 12:07

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) aniketsanadhya1★
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★

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.

link

answered 27 Nov '16, 21:03

lakh's gravatar image

4★lakh
1395
accept rate: 23%

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"; } }

link

answered 27 Nov '16, 21:06

lakh's gravatar image

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; }

        }
    }
}
link

answered 28 Nov '16, 00:10

harshit19's gravatar image

2★harshit19
311
accept rate: 0%

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:

×921
×763
×382
×12

question asked: 27 Nov '16, 20:39

question was seen: 1,318 times

last updated: 14 Apr '17, 18:30