Codeforces Round #202 (Div. 1), problem: (A) Mafia solution

Codeforces Round #202 (Div. 1), problem: (A) Mafia: http://codeforces.com/problemset/problem/348/A

Codeforces Round #202 (Div. 1), problem: (A) Mafia editorial: http://codeforces.com/blog/entry/9031

Codeforces Round #202 (Div. 1), problem: (A) Mafia solution: http://ideone.com/JEoXON

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

int main() {
    long long int n, a, ma=0, cnt=0;
    scanf("%I64d", &n);
    for(int i=0; i<n; i++) {
        scanf("%I64d", &a);
        if(a>ma) ma=a;
        cnt+=a;
    }
    a=ceil((double)cnt/(n-1)), a=max(a, ma);
    printf("%I64d", a);
    return 0;
}

note, courtesy of baklazan: http://codeforces.com/blog/entry/9031#comment-147355

Let's say you're going to play x games. If someone wanted to play more than x games, he wouldn't be able to do so, so he would be unhappy. Therefore, if everyone is happy, x ≥ ai must hold for each i, so

x ≥ max(a1, a2, ..., an)

Let $b_i$ be number of games, where i-th player is supervisor and let ci be number of games, where he plays. In each game i-th player is playing, XOR supervising, so ci + bi = x. Also, he wants to play at least ai games, soai ≤ ci, thus bi ≤ ci + bi - ai, so bi ≤ x - ai.

Each game is supervised by one player, so x = b1 + b2 + ... + bn. Giving it all together:

x = b1 + b2 + ... + bn ≤ (x - a1) + (x - a2) + ... + (x - an)

Now we have two lower bounds for $x$ . Smallest x satisfying both of them is

This number of games is enough, because if first $x - a_1$ games are supervised by first player, next x - a2games are supervised by second player etc., until the x-th game, then everyone plays enough games and each game is supervised by someone.