It’s been three months since I last solved a programming challenge from the book. I took some time to do some Project Euler problems, but there’s no real excuse why I’ve sucked at this. In any event, did another one:
10128 – “Queue”
So, I brute-forced this (and then cached the problem space, since it’s small), and my solution didn’t work. Long story short, I should have known better than to trust the judge by now, but I didn’t (my emphasis added):
Each test case consists of a line containing three integer numbers: N that indicates the number of people in a queue (1 <= N <= 13), and then two more integers. The first corresponds to the number of people, that we can see looking from the beginning, and the second corresponding to the number of people, that we can see looking from the end.
There’s no reason to believe that the second a third integers are bounded in a rational range. Anyhow, not a clever solution at all, but it works.
10160 – “Servicing Stations”
I admit defeat on this one, after blowing a few hours a week on it for about a month. I’m not sure what to prune on. I’ve tried eliminating redundant subset edges, without any real performance improvements on my generated test cases. I break graphs into pieces, which is a big win, but not enough. I built up a fast way of checking membership, tried sorting by incidence, tried resorting by incidence, tried sorting actively by uncover rates, and none beat the judge’s 10-second limit.
I can only conclude from this that I’m missing something blindingly obvious, and that the problem is not, in fact, an NP set covering problem. But, try as I might, I can’t spot the shortcut.
My solution is, therefore, a brute-force worthless that doesn’t solve the puzzle in the required time limit. But it’s time to move on until something better occurs to me.