NCPC (Nordic Collegiate Programming Contest) and UKIEPC (UK and Ireland 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 4.
The contest will be held at open.kattis.com and you can participate in the warm-up contest in the mean time.
Will it be possible to upsolve it? This weekend our team will be busy.
The problems will be available at Kattis also after the contest but there is no functionality there to replay the contest. We could upload it to CodeForces gym afterwards.
That would be great (especially with real standings)! Thank you!
We've added the contest to the gym now: 2014 Nordic Collegiate Programming Contest
No replay ghosts yet. Let us know if you have any problems.
Great! What about the ranklist?
The wizard failed to import a standings page, and for now I only have UKIEPC raw submit data (much smaller than NCPC).
If you have an automatic way of importing from KATTIS would you mind sending me a message about it? Otherwise I'll make some kind of hacky script in the morning.
I found that was because of empty team name in the standings. I think it is good idea to validate team names to be at least non-empty.
We've fixed wizard to handle empty names, I'm planning to upload parsed standings.
UPD: Done.
Thanks!
Are you sure it was empty? There was one team name which consisted only of white-space characters. The ICPC registration system allowed it, so it went through.
☺☻☺☻☺☻☺☻☺☻☺☻
Everything relevant is published at http://ncpc.idi.ntnu.no/ncpc2014/, even the wrong solutions, input generators and problem statement sources in TeX.
NCPC featured really nice problems! Today we had an individual contest based on those task in University of Warsaw, though we didn't have all of them (without few easier tasks). We had Ceremony, Outing, Clocks, Particles, Basin City, Road and Squares. I especially liked Particles and Basin City! (Though I didn't solve Basin City).
By the way I can't help myself from presenting a comparison.
[Task name] — [Teams of three which got that task accepted on NCPC out of >250 teams]:[People on UW which got it accepted out of 43 people]
Particles — 2:8
Basin City — 2:3
Roads — 7:12
Squares — 15:21
:))
That's impressive!
I am sure that lot of contestants from NCPC became much more motivated for trainings after reading your comment and especially the stats that you provided:)
Even more, when they will see yours performance in gym :D. Gratz :P.
Problem B, k-Independent Set one, seems we can get rid of the n term in the O(n × 3k) solution and speed up to O(kd × 3k):
While we do DFS searching, to find an uncovered and unused vertex we may loop from 1 to |V| to do so. However, say we found u in the current step, we can pass it to the next iteration which starts finding the vertex from u instead of 1. For each DFS tree leaf the total time in such loop is bounded by O(dk).
This can also be applied to the O(n × 2.31k) solution, yielding a O(dk × 2.31k) solution. Which may even be fast enough for k = 17, 18.
P.S. Anyway it seems you have already done that in your solution :p
The case when n>= kd is trivially always possible, so the only interesting cases are when n<kd. It was easier to put such expression on the slides.
Btw, I wrote a post about the contest and problem B: http://lukasov.blogspot.se/2014/10/nordic-championships-in-programming-2014.html
i am trying to solve problem A but fail to do so . i am trying both 2 sat 2SaT code and graph coloring bi_coloring code method . for idea one i got WA at test case 1 and for 2nd method got WA at test case 2 :( May be my idea was totally wrong . can anyone please describe the process how to solve problem A .
First — we exactly know about color of vertexes, connected with 0-edges or 2-edges. And we know about all vertexes, reachable from these colored vertexes.
We didn't color only vertexes, connected only by 1-edges. For each connected component of these vertexes, we can color or not color one vertex and check colors other vertexes by dfs/bfs.
If we have some color conflicts — answer is "-1"
thank you Slamur for your time . i am trying to follow your process , but wrong answer at test case 3 :( code link
if you have time please kindly check my code where i am missing something or doing something wrong .
When we colored all vertexes, connected with 0- and 2-edges, we had graph with only 1-edges in it.
So we have 2 types of connected components — which have some already colored vertexes — so we can get colors of all vertexes in it by dfs (or get color conflict) — and connected components, where all vertexes weren't colored.
For the second type of CC we must choose some vertex from it, color it by 0 and 1, and for each color use dfs to choose best variant.
By the way. Regarding problem J — Road works. My solution is essentialy O(n4) with tricky optimization. I used similar dp as in model solution dp[carswest][carseast][irritatednum] which was the smallest time (or INF) to achieve that state, but I propagate informations from those states in O(n) time (adding 1, 2, 3, ..., cars from west, and adding 1, 2, 3, ..., cars from east), so it resulted in O(n4) solution ("we have a state, let's see what we can achieve with it" approach, not "we need info about that state, let's search possible previous states") and it got TLE. But later I added an if that id dp[carswest][carseast][irritatednum] ≤ dp[carswest][carseast][irritatednum + 1] then I don't need processing possible outcomes of the second state. I got a feeling that constructing a testcase such that it won't help should be very hard and indeed, I got AC. Do you know why is it fast? I suspect that it might be O(n3) or O(n3·smallfunction).