Solution UVA: 12032 - The Monkey and the Oiled Bamboo

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss12032 - The Monkey and the Oiled Bamboo	Accepted	C++11	0.050	0.000	1352	3 mins ago

Suggest:

If you are stuck on this problem, it means you are not familiar with binary techniques. Please refer to my implementation in the code snippet below. This implementation requires an additional for loop to obtain the final result, but its advantage is that you don't need to modify the mid calculation (in some cases, if you don't change this calculation, you will loop infinitely).

Binary search is an efficient search algorithm used on a sorted array. Its strength lies in quickly identifying the desired value by dividing the array into smaller segments and eliminating the half of the array that does not contain the target value.

In the given source code, binary search is used to find an approximate value within the range from l to r. The goal is to find a value m for which the function f(m) returns true.

The function f(k) checks whether the value k satisfies a specific condition. In this case, we want to find a value k such that:

If a[i-1] + k < a[i], then k is invalid and the function returns false.

If a[i-1] + k == a[i], then k is decremented by 1 and the check continues with the next element.

In the main loop, the variable l is initialized as 1 and r as 1e7 (10^7). Binary search is employed to find the value m that satisfies f(m). The loop continues to halve the search range until the remaining range has only 3 elements (r-l+1>3).

In each binary search step, the average value m of l and r is computed, and it is checked whether f(m) returns true. If f(m) returns true, r is assigned as m to narrow down the search range to the first half. If f(m) returns false, l is assigned as m to narrow down the search range to the second half.

Finally, after finding a remaining range of length 3 (r-l+1=3), each value within that range is checked to determine the exact value. We search for value i within the range from l to r for which f(i) returns true. Once that value is found, we print the result.

#include<bits/stdc++.h>

#define N 1000111

using namespace std;

int n;

int a[N];

bool f(int k){

    for(int i=1; i<=n; i++){

        if (a[i-1] + k < a[i]) return false;

        if (a[i-1] + k == a[i]) k--;

    }

    return true;

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    int t; cin >> t;

    int kase= 0;

    while(t--){

        cin >> n;

        for(int i=1; i<=n; i++) cin >> a[i];

       

        int l=1, r=1e7;

        while(r-l+1>3){

            int m= (l+r)/2;

            if (f(m)) r=m;

                else l=m;

        }

       

        for(int i=l; i<=r; i++)

            if (f(i)){

                cout<<"Case "<<++kase<<": "<<i<<"\n";

                break;

            }

    }

}