The Benelux Algorithm Programming Contest 2018 takes place October 27th. This is a subregional contest for teams from **Be**lgium, the **Ne**therlands and **Lux**embourg, which feeds into NWERC.

The contest starts at 13:00 local time (GMT+2) and there is a semi-live contest starting half an hour later for which you can register here. For comparison, you can find last years problems in the gym here.

This is tomorrow. Looking at the schedule it seems the contest was moved to 13:30 so the live contest should then start 14:00 (GMT+2). There'll also be a livestream with solutions afterwards (see the main site).

Very nice problemset! The intended solution for problem I was binary search + flow?

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 andO(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.

Any ideas for D? I had the following observations:

dis small, then we can usedphases of rolling hashes to compute it inO(n·d).Then I tried to combine this with a heuristic solution where we run the state-graph BFS and keep the first

`50`

states we get for every vertex for both A and B. (But I was coding in the train and made too many stupid bugs, so I didn't debug it in time.) It would be nice if I could submit this somewhere.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:

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).

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.

Yeah, I've figured that out. The main (stupid) issue was that I was locally compiling and testing a different source file than the one I was editing and submitting, so I never noticed the mistake in my output. (And it was quite confusing as changing the paramters didn't influence the local runtime.) I'll try to squeeze my solution once the testdata is online.

If you can't wait you can just grab the data from the pull request ;-)

Thanks, it passed quite easily with 10 or 20 states per vertex, 50 or 100 iterations of hashes and the quadratic solution for

n< 3000.Ah that's unfortunate. Can we have your solution? We did some pruning of testcases because we were worried there were too much. Maybe my current set of generators can still break your solution. Would be nice before we put it on an online judge.

What is the preliminaries contest? Does it also contain good and original problems?

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.

For those interested, the contest is available on Kattis now.