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.

## No comments :

Post a Comment