jthread's blog

NWERC open contest — 29 november 2015
By jthread, history, 9 years ago, In English

You are hereby invited to participate in the open version of the ICPC NWERC regional. The contest is 5 hours long and starts on 29 november 2015 at 10:00 CET, which half an hour later than the onsite contest. The contest is a typical ICPC style contest and the jury (consisting of several high-rated coders) promises an interesting set of problems!

The contest is held on Kattis online judge.

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

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve problem D (Debugging)?

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

How to solve B, F, H?

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

    Ok, with some help from ngfam_kongu I finally found solution to B. I think it is very beautiful.

    • First, to avoid confusion of variable naming, let's restate the problem statement: We have N people, M machines. Person i comes at time Ai and leaves at time Bi. If a machine has set of people S, then its value is min(Bi for i in S) — max(Ai for i in S).
    • Consider the machine with the person with largest value of Ai (maxAi). If we also fix the value of minBi for this machine, then we can know who can be assigned to this machine (everyone with Bi >= minBi). Also note that the more people we can assign to a machine, the better, so we can greedily take all of them.
    • So now we can attempt the following DP:
      • Sort by increasing A
      • f(i, j) = maximum value if we assign people 1..i to j machines.
      • f(i, j) = max( f(i', j-1) + minBi — A(i) )

    • There is something wrong with the formula: B is not increasing, so we could not take everyone with Bi >= minBi (if we sort by B, then we could not select person with maxAi). To fix this, observe that if we ignore all people i such that there exists j where Ai <= Aj < Bj <= Bi (lets call them bad people), then when we sort in increasing order of A, it is already sorted in increasing order of B. And the bad people can always be assigned to the some group without affecting the answer. (there is some corner case here, but I left it as an exercise :))

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    There's actually Youtube videos with misof and Per describing the solutions for said problems. :)

    (I watched the ones for B and F. Quite nice. ^^)

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

      Do you know if there is code available online? For F, the particular part that I was looking for is not presented in the video: for the polygons, a segment AB can either be AB or (the circle — AB). This messed up all my calculations and I still don't understand how to implement this correctly.

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

        Here's my solution. You can either just try the "(B-A)+(C-B)==(C-A) check" mentioned in the slides for both, or pick the vector with the greatest dot-product with the two points it's supposed to be in between.

        I suppose the full set of judge solutions will be available later, as usual.

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        Apart from the great videos on youtube (thanks misof!), the jury will soon (probably within the next 24 hours) post the slides that were used during the presentation of solutions for the onsite participants, the jury solutions and all test data to the nwerc.eu website. I'll post the link here as soon as it's available, we first had to do some other post-contest stuff such as handing out prizes, travelling and sleeping :-)

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +30 Vote: I do not like it

          The solution slides, jury solutions, test data and test data visualizations are now available on the website.

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

Problem G is the same as 100247K - Three Contests. Please don't steal problems next time :)

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

    Problem J is an easy version of Задача 9. Хэш-функция

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      Problem J is an easy version of "write two simple for-cycles" :)

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Clearly none of the jury members had seen that problem before, otherwise we wouldn't have used it. It seems that two people came up with the same idea independently, I guess that great minds think alike :-)

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

    Also, G and this kattis problem are the same, and I guess we were lucky one of our team members (TimonKnigge) remembered the solution, using order statistics trees in the nodes of a segmenttree.

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

      Actually it was enough to solve it with a fenwick tree :)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        But that solution was quite hard to come up with I think, since most AC solutions used 2D segtrees to solve it.

        → Reply