April 3, 2018 NAIPC 2018

On March 24th, 2018, the North American Invitational Programming Contest (NAIPC) took place. This is the seventh installment of this contest. More details on what the contest is can be found on this site. If you already are familiar with ACM ICPC world finals, this is a pre-cursor to that contest for North American teams. This is the fourth year I’ve been helping out with writing problems for the contest. In this blog, I’ll be going over some of the problems that I set that I think may be interesting.
You can see the problems here, and final standings here.
Problem C is an example of a problem where re-stating the problem makes it much easier to solve. The problem is you’re given a row of n light bulbs, and their initial states (each bulb is on or off initially). In addition, there are n buttons, one below each of the light bulbs. In one timestep, you can press a button to change the state of a lightbulb, but this change may propagate further down in further time steps and change the state of other light bulbs down the line. See the problem for more details on how exactly this propagation is done. Your task is to find the smallest time for all light bulbs to be on.
The problem is stated in such a way to suggest a bitmask dp approach that stores both the state of the lights and the state of the propagation. Unfortunately, this requires 2 bits per bulb, and with at most 16 bulbs, this takes 2^32 time/space, which is too big.
Instead, we can approach this problem from a different angle. Let’s guess our answer, and see if it’s possible to achieve it. We can guess t = 0, 1, 2, … and so on (and we can show that this will be at most 2*n in the worst case).
Suppose we’ve already guessed the answer is t. Then, we can compute that pressing the i-th button at time (t-k) will toggle the states of the i-th through min(n, i+k)-th bulbs. This allows us to get rid of the propagation state, and this makes the bitmask dp tractable with only 2^n states rather than 2^(2n).
In short, working backwards makes the problem much easier, since we can note that (1) the answer is always relatively small, and (2) it is much easier to check a particular answer rather than to generate it directly.
Lastly, Problem G is a generalization of a previous problem I’ve written before in a previous contest. However, even though they seem similar, their difficulties are very different, and problem G remained as the only unsolved problem in this contest. The solution for G involves a technique known as “matroid intersection”, which I won’t go over in this blog. When I first proposed this problem, I was a bit unsure of whether or not it was appropriate for this contest since matroid intersection is a bit obscure.
It’s a bit unfortunate that nobody was able to get it, and it is due to matroid intersection being not too well known and also not being derivable easily from first principles. However, I think this problem is still not completely straightforward even with matroid intersection as a black box, which is why I thought it was an interesting problem to propose. Contestants may still have a big advantage for knowing what matroid intersection is, but that advantage is similar to knowing about something like what NTT, min cost flow, or suffix trees are for example. My main question is whether it is fair to give questions that rely on obscure algorithms like these, and what qualifies as an obscure algorithm.
Thanks for reading!