| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | maroonrk | 133 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
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.
is it possible that problem set be moved to gym codefoces?
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.
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.
Contest in gym
Thanks!
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.
Feel free to make some changes. I just upload contest data from official site.
My previous years experiences are telling me that I can recommend this competiton :).
So is the online contest an individual contest or team contest?
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.
This is a reminder that the contest starts in about 2 hours.
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.
Yes, it can stand as long as you like, it should be also clear from the first sample.
Can it move without making noise? "as long as you like" means that it's my choice, or I'm forced to do this? :)
No comment, read problem statement :)
Another question about B, are the input intervals given in floppyseconds or microseconds?
In problem F everything is given in floppyseconds.
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.
No comment, read problem statement.
what is the right approach to solve E . end time sorting didn't pass :(
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.
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.
Don't have to read your description right now, but one solution is described in the slides: https://ncpc.idi.ntnu.no/ncpc2015/ncpc2015slides.pdf
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).
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.
The standings are missing, probably you can upload them, their format is quite simple.