TimonKnigge's blog

BAPC 2018 Semi-Live Contest for Oct 27th
By TimonKnigge, history, 6 years ago, In English

The Benelux Algorithm Programming Contest 2018 takes place October 27th. This is a subregional contest for teams from Belgium, the Netherlands and Luxembourg, 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.

  • Vote: I like it
  • +43
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +23 Vote: I do not like it

    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(2s) vertices and O(s2s) edges.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any ideas for D? I had the following observations:

  • There's any easy quadratic solution by BFS on state graph.
  • If the answer d is small, then we can use d phases of rolling hashes to compute it in O(n·d).
  • We could use Hopcroft DFA-minimization over the binary alphabet in to check if the answer is "indistinguishable".

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +15 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply