Codejam round 1A, problem B : Hair Cut

Okay, I participated in round 1A and utterly failed. A ton of factors got involved that made me waste time.

• I thought of the solution for problem A, but when I started to code it I figured out I didn't actually set up my codejam test environment. I had a ton of setup to do to make my (worthless) solution multithreading support to work AND for it to work in gcc 4.8.2 with c++11 support.
• I got really confused by problem A, apparently eating 1.5 (or any other fraction) mushrooms per second is valid... but I don't think that was really well explained... Also what's up with "constant ratio" when the ratio is definitely not constant? It becomes 0 at some times? Huh? And how about giving you an input example before describing what the input is?
• I tried to solve B, my first solution was too slow, then I tried to find cycles in the simulation and it worked but I kept failing the small solution. There was a small bug - After doing the cycle stuff I forgot to return 1-indexed results... Overall what happened in problem B is I completely missed there's a very simple (but with caveats) solution until the last 2 minutes of the match, it was too late.
• C small is just bruteforce and convex hull. Thanks to allowing colinear points (artificial difficulty at its finest :/) I actually had to do a ton of fixes to my convex hull algorithm which I haven't really used in years. My code was pretty awful and there were a couple of bugs in that old code that I had to fix.

Anyway, since B-small / B-large are the only problems I solved that are actually interesting. Here is an explanation for problem B large:

The time

I think the most important thing is to notice the problem is much easier when we know the time `t ` at which customer `N` will be served. Imagine we knew this time in advance. Then we would only need a single loop to find all the barbers that finish serving a customer at time `t`. Each barber `i` is a cycle, every `M_i` the barber serves a new customer. So barbers with `M_i` such that: `(t mod M_i = 0)` will serve a new customer at time `t`.

You might be thinking that the solution is the barber that serves a new customer at time `t` and has the smallest index. This is not entirely true. Multiple customers may be served at time `t`, and `N` is not necessarily the first customer to be served at that time. How can we approach this?

Imagine a function `b(t)` that told you how many customers are served with starting time less than or equal than `t`. Then `b(t-1)` will be the amount of customers that were served right until time `t`. And `b(t) - b(t-1)` is the amount of customers that start getting served exactly at time `t`. Now `N - b(t-1) - 1` customers will be served at time `t` before `N`. Which means that we are looking for the barber with the (N - b(t-1))-th smallest index among those barbers with `(t % M_i = 0)`.

The last piece of the puzzle is how to find `t`. It all comes down to `b(t)`, with this function we can do a binary search for the smallest `t` such that `b(t) >= N`, this is the time you want.

// Library code
// takes lo, hi, P() such that:
// P(lo) is true
// P(hi) is false
// If P(x) is true and (x > y) then P(y) is true
// If P(x) is false and (x < y) then P(y) is false
// returns the minimum x such that P(x) is true
template<class D> D BinarySearch(D lo, D hi, std::function<bool(D)> P) {
    while (lo + 1 < hi) {
        D ha = lo + (hi - lo) / 2;
        if (P(ha)) {
            hi = ha;
        } else {
            lo = ha;
        }
    }
    return hi;
}

struct solver
{
    int N, B;
    vector<int> M;
    
    int solve()
    {
                
        auto begunByTime = [&](long t) -> long {
            if (t < 0) {
                return 0;
            }
            long begun = 0;
            for (int i = 0; i < B; i++) {
                // how many times did it start?
                begun += t / M[i] + 1;
            }
            return begun;
        };
        
        // Is the start time for at least N users <= t ?
        auto enoughBegun = [&](long t) -> bool {
            return (begunByTime(t) >= N);
        };
        
        long t = BinarySearch<long>(-1, 10000000000000LL, enoughBegun);
        long old = begunByTime(t-1);
        long rem = N - old;
        
        
        //cout << "time = "<<t<<endl;
        // find smallest index of a server that starts at time t:
        for (int i = 0; i < B; i++) {
            if (t % M[i] == 0) {
                if (rem == 1) {
                    return i + 1;
                } else {
                    rem--;
                }
            }
        }
        assert(false);
        return -1;
        
    }
    void init() { }
    void read() {
        cin >> B >> N;
        //N = 1000000000;
        //B = 1000;
        M.resize(B);
        for (int & x : M) {
            cin >> x;
            //x = 1 + rand() % 100000;
        }
        
    }

Edit: Fixed bugs, oh and also `b(t)` is just the sum of a bunch of divisions. For each barber, you can find the number of times the barber has started serving customers before or during `t` by just doing a division, because for every `M_i` seconds, the barber tries a new user.