Блог пользователя hex539

Автор hex539, 7 лет назад, По-английски

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://codeforces.net/gym/101623. Strong teams should find it sufficiently challenging.

  • Проголосовать: нравится
  • +42
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

    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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem I — Installing Apps?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    Hint
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +15 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится

        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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any updates on the contest's status?