Solution UVA: 11413 - Fill the Containers

 

Last Submissions
Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11413 - Fill the Containers	Accepted	C++11	0.000	0.000	1972	5 mins ago

Suggest:

- Use binary search to determine the capacity (Once the capacity is determined, simulate and calculate the number of containers)

Note: I use a binary search algorithm along with a while + a for.

#include<bits/stdc++.h>

using namespace std;

int n, m;

int a[1000111];

int main(){

    while(cin >> n >> m){

       

        m = min(n, m);

       

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

            cin >> a[i];

       

        int r = 0;

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

            r += a[i];  

       

       

        int l= 1;

       

        while(r-l+1 >= 3){

           

            int mid = (r + l) / 2;

            int s = 0;

            int container= 0;

            bool bl = false;

           

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

            if (a[i] + s <=  mid){

                s += a[i];  

                bl = true;

            }

            else{

                if (not bl) {

                    container = m + 1;

                    break;  

                }

                if (bl) container++;

                bl = false;

                s = 0;

                i--;

            }

           

            if (bl) container++;

           

        //  cout<<"mid container: "<<mid<<" "<<container<<"\n";

           

            if (container > m) l = mid;

            else

                r = mid;

        }

       

        for(int mid=l; mid<=r; mid++){

           

            int s = 0;

            int container= 0;

            bool bl = false;

           

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

            if (a[i] + s <=  mid){

                s += a[i];  

                bl = true;

            }

            else{

                if (not bl) {

                    container = m + 1;

                    break;  

                }

                if (bl) container++;

                bl = false;

                s = 0;

                i--;

            }

           

            if (bl) container++;

           

            if (container <= m){

                cout << mid <<"\n";

                break;

            }          

           

        }

       

       

    }

   

       

}

Solution UVA: 10539 - Almost Prime Numbers

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10539 - Almost Prime Numbers	Accepted	C++11	0.000	0.000	183	1 mins ago

Suggest:

- Almost prime is the exponential of a prime number

- To find all the multipliers of prime numbers in the given time, we use the sieve prime

- After getting all the almost primes, to find out how many numbers are in a segment we use sort + binary search

#include<bits/stdc++.h>

#define int long long

using namespace std;

vector<int> a;

void sieve(int N) {

    int NN = N*N;

    bool isPrime[N+1];

    for(int i = 0; i <= N;++i) {

        isPrime[i] = true;

    }

    isPrime[0] = false;

    isPrime[1] = false;

    for(int i = 2; i * i <= N; ++i) {

         if(isPrime[i] == true) {

             // Mark all the multiples of i as composite numbers

             for(int j = i * i; j <= N; j += i)

                 isPrime[j] = false;            

        }

    }

     for(int i = 2; i <= N; ++i)

        if (isPrime[i])

            for(int j= i*i; j <= NN; j *= i) a.push_back(j);

}

int32_t main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    sieve(1000000);

    sort(a.begin(), a.end());

   

    int t;  cin >> t;

    while(t--){

        int l, r;   cin >> l >> r;  

        int L = lower_bound(a.begin(), a.end(), l) - a.begin();

        int R = lower_bound(a.begin(), a.end(), r) - a.begin();

        if (a[R] > r) R--;

        cout << R - L + 1 <<"\n";

    }

}

Solution UVA: 714 - Copying Books

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss714 - Copying Books	Accepted	C++11	0.000	0.000	1359	3 mins ago
| discuss714 - Copying Books	Wrong answer	C++11	-	0.000	-	26 mins ago
| discuss714 - Copying Books	Wrong answer	C++11	-	0.000	-	45 mins ago
| discuss714 - Copying Books	Wrong answer	C++11	-	0.000	-	54 mins ago
| discuss714 - Copying Books	Wrong answer	C++11	-	0.000	-	1 hours ago
| discuss714 - Copying Books	Wrong answer	C++11	-	0.000	-	1 hours ago

Suggest:

- max_page is mid of binary_search

- Binary search to find max_page of scribers, when you have max_page you should greedy from right to left (book n -> 1) to get /

- Greedy right to left because they said: "If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book."

#include<bits/stdc++.h>

#define int long long

using namespace std;

int a[1000111];

int b[1000111];

int R, L;

vector<int> q, res;

   

void f(int n, int k){

    k -= 1;

    res.clear();

    int l = L, r = R;

   

    while(r - l + 1 >= 3){

       

        int m = (r+l) / 2;

       

        q.clear();

        int s = 0;

        int i = n;

        for(i; i>=1; i--){

            if (s + a[i] <= m){

                s += a[i];

            }  

            else{

                q.push_back(i);    

                s = a[i];

                if (s > m || q.size()==k) break;

            }

                int remain = k - q.size(); //for output 2

                if (remain == i - 1){

                    for(int j= i-1; j>0; j--)

                        q.push_back(j);

                   

                    i = 0;

                    break;

                }

            }

           

        s = 0;

        for(int j=1; j<=i; j++)

            s += a[j];

           

        if (s > m || q.size() > k){

            l = m;

        }

        else if(q.size() < k){

            r = m;

        }  

        else if (q.size() == k){

            r = m;

            res = q;

        }

    }

    int page=-1;

    for(int m= r; m>= l; m--){

        q.clear();

        int s = 0;

        int i = n;

        for(i; i>=1; i--){

            if (s + a[i] <= m){

                s += a[i];

            }  

            else{

                if (i != n) q.push_back(i);    

                s = a[i];

                if (s > m || q.size()==k) break;

            }

           

       

            int remain = k - q.size(); //for output 2

               

                if (remain == i - 1){

                    for(int j= i-1; j>0; j--)

                        q.push_back(j);

                   

                    i = 0;

                    break;

                }

        }

           

        s = 0;

        for(int j=1; j<=i; j++)

            s += a[j];

           

    if (s <= m && q.size() == k){

            page = m;

            res = q;

        }

    }

    for(auto x:res) b[x]= true;

   

}

int32_t main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    int t;  cin >> t;

    while(t--){

        R = 1e18, L= -1e18;

        int n, k; cin >> n >> k;

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

            cin >> a[i], b[i]=false, L=max(L, a[i]);

       

        f(n, k);

       

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

            cout<<a[i]<<(i==n? "" : (b[i] ? " / " : " "));

        cout<<"\n";

    }

} 

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;

            }

    }

}