I used binary search + flow for I and got OK, but I guess binary search + Hall's mariage theorem might work too.

Edit: You have to be a bit smart with your flow graph so you only get O(2^s) vertices and O(s2^s) edges.

Depends a bit on what you mean by 'flow' :-) Our intention was that doing flow with shelters on the left and locations on the right would get TLE, since your flow graph might have size O(sn). I don't think anyone got through with that approach but I didn't check the online mirror very carefully.

The livestream with solutions is here. I present I (and then D) around -31:00. But it's not very coherent, I was really tired and there was a loudspeaker next to me with about a 0.5s delay. Try pronouncing `indistinguishability' then :-)

We'll try to put everything online in the next few days, including solution slides.

EDIT: Here are the slides with solutions we used. There's some minor errors but they're mostly complete.

I loved problem D. I would like to submit it somewhere too.

Here is my solution (not 100% sure about correctness).

Let t[i] be 1 if we can see the tower and 0 otherwise. Let l[i] and r[i] denote where we go if we turn left and right.

The idea is to execute quickly the following procedure:

• Initially we can say that it must hold t[A] = t[B] (otherwise we have already finished).
• At step 1 we can say that t[l[A]] = t[l[B]] and the same for r.
• And so on.

Here is the real solution:

We keep a disjoint union data structure on the vertices (ancestor(i) denotes the root of the component to which i belongs). Two vertices i and j will be in the same component iff (at the current step) we know that t[i] = t[j] (we will always keep track of the current step, this way as soon as we find a contradiction we know the answer).

• Initially we join A and B. And we insert in a queue the pair {A, B}.
• We start popping pairs from the queue.
• When we pop a pair i, j we join {ancestor(l[i]), ancestor(l[j])} and we insert such pair in the queue. If ancestor(l[i]) and ancestor(l[j]) are already equal we do nothing. We do the same with r[i] and r[j].
• We keep doing the previous steps until the queue is empty or we find a contradiction. If we cannot find a contradiction then the answer is 'indistinguishable'.

The overall complexity is pseudo-linear.

FYI I think most your tests gave WA because you printed -1 instead of indistinguishable. Other than that I think you were only getting a proper WA on two cases or so. So you were close :-)

Slides are here if you're interested, I won't be putting any spoilers in the comments here.

The preliminaries set is distributed to all universities to use for local qualifiers. They're a bit easier/more standard than the main contest, but other than that it's a proper problem set.