hex539's blog

NWERC 2017 open contest — 26 November 2017
By hex539, 7 years ago, In English

On 26 November 2017 at 10:30 GMT, we'll run the online contest for the 2017-2018 North-Western Europe Regional Contest (NWERC). This year the live contest is held overlooking the idyllic city of Bath, United Kingdom.

The competition is 5 hours long. You can register for the online contest here:

  https://open.kattis.com/contests/nwerc17open

After the online contest, solution sketches and the problem archives will become available for download on the official website. A couple of days later all of the problems will appear in the Codeforces Gym.

Update: contest now available in the Gym at http://mirror.codeforces.com/gym/101623. Strong teams should find it sufficiently challenging.

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

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

How was Problem A — Ascending Photo supposed to be solved?

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

    There are slides here: http://www.nwerc.eu/news/nwerc2017slides.pdf

    Summary: you can make an O(N^2) DP with O(N) items based on who with height H you put first in the final list. Each has O(N) transitions. Then you can optimise it by batching all the transitions for people with the same height together, since they're all very similar.

    For the moment all the contest data seems to be hosted in the "news" section http://www.nwerc.eu/news

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

How to solve problem I — Installing Apps?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    Hint
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain that observation? Why it must be sorted by the difference? It does not seem that intuitive to me :'(

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

        There are many such problems that can be solved by two steps:

        1) Assume we know the optimal subset S of items (apps) that we should take (install). In what order is it always possible to take (install) those items (apps) without violating any constraints?

        2) Sort all items in the found order and then apply knapsack DP.

        Step 2) is usually trivial. The hard part is to come up with a correct order in step 1) and can usually be proven with an exchange argument:

        Let us consider any valid order and consider any two adjacent apps (da, sa) and (db, sb) with da - sa ≤ db - sb. We will prove that after swapping those two apps the order will still be valid (b will be installed before a after swapping). Let X be the free space of the cell phone before installing app number a. Since the order is valid, we know that da ≤ X and sa + db ≤ X. After swapping a and b (elements before a and elements after b aren't affected by this swapping) we must only show that: db ≤ X and sb + da ≤ X.

        • db ≤ X is obviously true (since sa + db ≤ X and sa > 0).
        • sb + da ≤ X also holds: da - sa ≤ db - sb implies sb + da ≤ sa + db and therefore we know that sb + da ≤ sa + db ≤ X.

        So for any subset of apps for which we know that there exists an ordering to install them, we can always apply the ordering di - si (descending).

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

          Still not sure how this db - sb ≥ da - sa came out of a sudden.

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

            Essentially if you are going to install two apps with pre-install sizes A1 and B1, and post-install sizes A2 and B2, the total amount of space consumed by them afterwards will always be A2+B2.

            However, they will have intermediate steps during installation where app A takes up A1 space, and then app B takes up A2+B1 space to (since A is already installed by this point).

            We want to make sure that A and B are chosen so as to make sure the maximum intermediate size, which will be A2+B1 assuming that A1>=A2 and B1>=B2 (if not, you should adjust the inputs so that A1=max(A1,A2) and B1=max(B1,B2)), is decreasing as space becomes tighter.

            So, we want to choose an assignment/ordering of A and B such that A1+B2 > B1+A2. You can rearrange this to get A1-A2 > B1-B2, which is why we sort by that.

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

              Great, thanks!

              However, they will have intermediate steps during installation where app A takes up A1 space, and then app B takes up A2+B1 space to (since A is already installed by this point).

              This part was crucial.

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

            Usually this kind of problem is easily approachable when we think it as a "scheduling" instance : Suppose I have a list of homework with deadline di and time ti. Like most problems in this kind, it's optimal to do in the ascending order of deadline (earliest deadline first).

            Now, when we let deadline C - di + si and time si, then we can see that this is a scheduling problem.

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

              Spent couple of hours reading the proof (in Russian) of this "scheduling" problem on and understood why it is so. Quite intuitive now! Thanks for such observation.

              → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Why I see the length is 4 hours in Gym instead of 5?

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

    Somebody with edit rights vandalised the contest: they changed the length from 300 to 240, set a start time where I hadn't set one, and removed 3 of the problems. This is not intentional and I did not do this.

    Messaged MikeMirzayanov about it just under an hour ago about rolling back. No response yet.

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

      I've removed the contest from the public list until there's a response from MikeMirzayanov about fixing the vandalism.

      Some access controls to stop people doing this would be really nice -- I thought Coach mode was supposed to be some elite thing that was only given to trustworthy users.

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

        I also encountered vandals but they just changed the name and start time, so that was not harmful.

        I think contests should not be editable by anyone except author, and maybe except users with such privileges granted by the author. Coach rights should allow creating new contests and viewing solutions and tests in others' contests.

        If you still want to modify a contest as these vandals did, you can create a mashup with your own set of problems and your own contest duration.

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

Any updates on the contest's status?

→ Reply