## Sunday, March 1, 2015

### 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;
}