rahimuj570's blog

By rahimuj570, history, 19 months ago, In English

NEED_HELP

problem link: https://www.spoj.com/problems/PIE/

code screenshot: https://vjudge.net/solution/snapshot/41982578

Today I try to solve the PIE-pie problem. But at first I don’t understand how to approach the solution. So I get some idea from other’s solution. Now I understand all the solution and the approach except the base condition of the binary search. Why the base condition was 1e-6 instead of 1?

Please help me…

my code:

#include<bits/stdc++.h>
using namespace std;
        #define ll long long int
        #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        #define pb push_back
ll n,f,input;
std::vector<ll> v;


bool possible(double size){
        ll totalCake=0;
        for(ll i=0; i<n; i++){
                totalCake+=((v[i]*v[i])*M_PI)/size;
        }
        return totalCake>=f;
}

int main(){
fast;
        #ifndef ONLINE_JUDGE
        freopen("inputf.in","r",stdin);
        freopen("outputf.out","w",stdout);
        #endif
        ////////////////////////////////

int t;
cin>>t;
while(t--){
        v.empty();
        cin>>n>>f;
        f++;
        int temp=n;
        while(temp--){
                cin>>input;
                v.pb(input);
        }
        sort(v.rbegin(), v.rend());
        double maxV=(v[0]*v[0])*M_PI;
        double low=0, high=maxV, mid;

//======>> HERE'S THE CONFUSION ↓
//=====↓↓↓
        while(high-low>=1e-6){
                mid=(high+low)/2;
                if(possible(mid))low=mid;
                else high=mid;
        }
        if(possible(high))cout<<high<<endl;
        else cout<<low<<endl;
}

return 0;}
  • Vote: I like it
  • -14
  • Vote: I do not like it

| Write comment?
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Okay, suppose this. For some test case the correct answer is 10.577215 (approximately). Now, let's say your binary search has determined with a few iterations that low = 10.2 and high = 11.1. If the breaking condition was while (high - low >= 1) the binary search would quit here because 11.1 - 10.2 = 0.9 < 1. Now, the code would determine that the value high is bad and it would output low.

Notice that the difference between the correct answer ans = 10.577215 and your answer low = 10.2 is 10.577215 - 10.2 = 0.377215. According to the problem statement, your answer will be regarded correct if and only if the difference between your answer and the correct answer is at most 10^-3 = 0.001. It should be quite clear that the answer 10.2 is not close enough to the correct one and you would get WA.

You might think why isn't the condition then just while (high - low >= 1e-3)? This can sometimes still round incorrectly and you should always play it safe by doing while (high - low >= 1e-4) at least (i.e. make it at least 1 digit more precise than what was asked). It doesn't really hurt the performance of the code even if the condition is more strict than required but most importantly, you will definitely not get WA due to precision errors.