## Friday, April 17, 2015

### 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() { }
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.