pranshukas's blog

By pranshukas, 4 years ago, In English

Problem Link: 1301B - День рождения Мотарака

I am facing some difficulties while solving this problem. Can Anyone Help me?

Here's my Pseudo Code(Below): I have used Binary Search to approach the problem. I am applying Search over range 0-10^9 and inserting my mid-value at the position where arr[i]= -1 and taking the absolute differences if I find that the maximum absolute difference after replacing -1 with mid was less than my temporary answer, I just update my value. But It's giving Wrong answers. Please Someone explain Where I'm Getting Wrong. What changes Do I need to make...

#define ll long long 
#define rep(i,a,b) for(ll i=a; i<b; ++i)
ll check(ll mid, ll *arr, ll n)
{
    ll ans=0;
    rep(i,1,n)
    {
        if(arr[i]==-1 and arr[i-1]!=-1) ans=max(ans,abs(mid-arr[i-1]));
        if(arr[i]!=-1)
        {
            if(arr[i-1]==-1) ans=max(ans,abs(arr[i]-mid));
            else ans=max(ans,abs(arr[i]-arr[i-1]));
        }
    }return ans;

}
void solve()
{
    ll n;  cin>>n;
    ll arr[n];
    rep(i,0,n) cin>>arr[i];
    ll low=0,high=1000000000,ans=1e9+7,k;
    while(low<high)
    {
        ll mid=(low+high)/2;
        ll temp=check(mid, arr, n);
        if(temp<=ans)
        {
            ans=min(temp,ans);
            k=mid;
            high=mid;
        }
        else low=mid+1;
    }cout<<ans<<" "<<k<<"\n";

}

Thanks for Help !!!!

  • Vote: I like it
  • 0
  • Vote: I do not like it