Codeforces Round #294 Div. 2 Problem C - A and B and Team Training

Problem Statement:
519C - A and B Team Training

Solution:
Nice problem, in fact the problems for this round are good stuff.

Let's express the groups as tuples (1, 2) and (2, 1), in the form of (number_of_experts, number_of_newbies). We have the following constraints :
\( a (1, 2) + b (2, 1) \leq (n, m) \)
where a and b denotes the number of groups of the respective arrangements. We want to maximize \(X = a+b \), and we can search for the maximum possible X using binary search. Rewrite the constraints in term of X and a, we have \( 2X - a \leq n\) and \( a + X \leq m \). Additionally, a must be non negative and cannot be bigger than X.

Hence for a given X, if there exist \(a\) such that \(a\) fulfils the above inequalities. If there is such \(a\), we can try bigger X. This is because for a given X, if there exists \(a\) that satisfies the inequalities, automatically all X smaller than the current X will also have that property. Very nice.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    int N, M;
    scanf("%d%d",&N,&M);
    int lo = 0, hi = (N+M), mid;
    while(lo <= hi){
        mid = (lo+hi)/2;
        int lower = max(0, 2*mid - N);
        int upper = min(mid, M-mid);
        if(lower <= upper) {
            lo = mid+1;
        } else {
            hi = mid-1;
        }
    }
    printf("%d\n",hi);
    return 0;
}