Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972. ×

one_piece_22's blog

Binary Search giving wrong answer , why ?
By one_piece_22, history, 10 days ago, In English

The question was : Counting Game https://practice.geeksforgeeks.org/contest/gfg-weekly-167-rated-contest/problems

Can you Please help to find out why the binary search is giving wrong answer !

In this question all the elements are positive !

NOTE: single element should always be counted whether it lies or not in [a,b] range

long long fun( int n, int a , int b , vector&arr ){

vector<ll> pre(n+1);

    for(int i = 1; i <= n; i++) pre[i] = pre[i-1]+arr[i-1];

    ll ans = n; 
    for(int i = 1; i <= n; i++ ){
        ll low = i; ll high = n; ll lb= -1;

        while(low <= high){
            int mid = (low+high)/2;
            if( pre[mid]-pre[i-1] >= a ){
                if(pre[mid]-pre[i-1] <= b) lb = mid;
                high = mid-1;
            }
            else low = mid+1;
        }

        low = i; high = n; ll rb = -1;
        while( low <= high ){
            int mid = (low+high)/2;
            if( pre[mid]-pre[i-1] <= b ){
                if( pre[mid]-pre[i-1] >= a ) rb = mid;
                low = mid+1;
            }
            else high = mid-1;
        }

        if( rb != -1 && lb != -1 ) {
            ans += rb-lb+1;
            if( lb == i && rb != -1 )ans--;
        }

    }

    return ans;

}

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
10 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

use multiset to find 2 max and 2 min elements in a sliding window.

→ Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok , Thanks !

    → Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sir, can you please help to find error in this code of above question

    ~~~~~~~~~~~~~~~~~~~ //this is the code

    multisetmst; int i = 0; int j = 0; int ans = 0;

    while( j < n ){
    mst.insert(arr[j]);
    if(mst.size()==1){
        ans += j-i+1;
        j++;
        continue;
    }
    auto it = --mst.end();
    int max1 = *(it); int max2 = *(--it);
    int min1 = *(mst.begin()); int min2 = *(++mst.begin());

    while( max1+max2 > b || min2+min1 < a ){
        mst.erase(mst.find(arr[i]));
        i++;
        if(mst.size()==1)break;
        auto it = --mst.end();
        int max1 = *(it); int max2 = *(--it);
        int min1 = *(mst.begin()); int min2 = *(++mst.begin());
    }

    ans += j-i+1;
    j++;
}
return ans;

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    → Reply
    • »
      »
      »
      8 days ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it
      CODE
      → Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Check that lb and rb are accurately calculated and lb is always less than or equal to rb. Make sure you're not double-counting or missing valid subarrays.

→ Reply