lukasP's blog

NCPC 2015 online contest
By lukasP, history, 9 years ago, In English

NCPC (Nordic Collegiate Programming Contest) will be held on Saturday and you will be able to participate in an online contest with the same problem set. The online contest will start at 11:00 and end 16:00 CEST on Saturday, October 10.

The contest will be held at open.kattis.com and you can participate in the warm-up contest in the mean time.

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

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

is it possible that problem set be moved to gym codefoces?

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

    All the materials from the previous years of NCPC have been explicitly released under a permissive Creative Commons license, and I expect the same will be true this year. Hence, anyone can legally upload it to the gym afterwards, as long as proper attribution is included.

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

      Yes, we'll publish everything under Creative Commons again. Last year we've also uploaded the contest to the gym afterwards and we'll try to do the same this year.

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

    Contest in gym

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

      Thanks!

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

      This solution for B gets WA in the gym contest, but is accepted on Kattis. Also I think you set the timelimits too low, my solution for G passes on Kattis in 2.90/5.00 seconds, but TLE's here. For comparison, my solution for J runs in 0.25s on Kattis, and needs 187ms here, and my solution for F takes 0.04s on Kattis vs 46ms here.

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

        Feel free to make some changes. I just upload contest data from official site.

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

My previous years experiences are telling me that I can recommend this competiton :).

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

So is the online contest an individual contest or team contest?

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

    I think most people will compete individually but there will be some teams competing as a preparation for regionals. You're free form a team if you want.

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

This is a reminder that the contest starts in about 2 hours.

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

Any idea where I can ask for clarifications? It is unclear to me in the problem Floppy Music whether the motor can sit still for one second or not.

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

    Yes, it can stand as long as you like, it should be also clear from the first sample.

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

      Can it move without making noise? "as long as you like" means that it's my choice, or I'm forced to do this? :)

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

        No comment, read problem statement :)

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

      Another question about B, are the input intervals given in floppyseconds or microseconds?

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

        In problem F everything is given in floppyseconds.

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

Problem B. In the picture, there is a transition from 1 2 4 3 6 5 back to 1 2 3 4 5 6. Do we have to be able to go to the initial position like this? The statement doesn't have any information about that.

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

what is the right approach to solve E . end time sorting didn't pass :(

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

    A possible approach would actually use end time sorting, though you would have to be careful with how you handled the fact that there can be k recordings at the same time (which translates to k intervals at the same time).

    So one way to do so would be to use a set (or rather, a multiset) to hold the last k end times of the last recorded show in each slot (in the beginning initialize it by inserting k dummy values, like -1). Now whenever we are processing a new show/interval we need to select the slot which has the latest last recording, but that ended before the beginning of the current show/interval. This can be done using binary search (using the lower_bound method). Finally, if we find a suitable slot, we replace its last recording and update our counter of recorded shows, otherwise we discard this show/interval and move on to the next show/interval.

    This is simply an adaptation of the "classic" greedy method for interval scheduling with a twist.

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

I liked B, the problem sounds like there could be a multitude of solutions, how did you guys solve it? This was my solution: We store the solution as a sequence of permutations, each defined by a vector of disjunct transpositions. Hardcode the solution for n ≤ 3; if n ≥ 4, apply the following algorithm: enumerate all permutations on n - 1 items, and if at some point we have an item at position n - 1 that has not been the last element yet, and the next permutation won't move this element, then we combine this next permutation with the transposition (n - 1n), and then make a full cycle through the permutations on n - 1 items, swapping n - 1 and n again during the last permutation. So if the current permutation is Pi, we apply .

It's pretty fast, 0.03s on Kattis, here is the code: github.

EDIT: For this technique it's important that you store exactly n! collections of transpositions, i.e. if you apply them all, you end up with the identity permutation.

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

Can someone explain the solution of A? I've looked at the solution slide, but I didn't understand it (except the first insight; I've already found it).

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

Everything relevant is published at http://ncpc.idi.ntnu.no/ncpc2015/, even the wrong solutions, input generators and problem statement sources in TeX. Some inputs even have ".desc" files describing the input as well as PNG images illustrating the optimal solution. The PNG images are especially helpful for solving iCar.

The contest has been uploaded to the gym by Temirulan.

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

    The standings are missing, probably you can upload them, their format is quite simple.

    → Reply