The onsite event of CODE FESTIVAL 2017 will start soon. There will be four contests during the event:
Final Round. This is the main contest.
All contests will have parallel rounds. Only Final will be rated (and corresponding parallel round will be rated too).
Check the schedule of the contests at https://atcoder.jp/.
UPD: Now the final standings is available at https://beta.atcoder.jp/contests/cf17-final/standings.
Congratulations to winners:
Will there be a grand final like last year?
No, this year there will be four contests listed above.
Who are the writers?
Schedule (Note that all time are in JST (GMT + 9)):
Saturday (25 November 2017)
CODE FESTIVAL 2017 Final (Parallel) (Rated)
Time : 12.30pm — 3.30pm (3 hours)
Scoring : 300-400-500-700-1000-1000-1000-1600-1600-1900
Link : https://cf17-final-open.contest.atcoder.jp/
CODE FESTIVAL 2017 Exhibition (Parallel)
Time : 7.40pm — 8.40pm (1 hour)
Scoring : 1000-1500
Link : https://cf17-exhibition-open.contest.atcoder.jp/
Sunday (26 November 2017)
CODE FESTIVAL 2017 Elimination Tournament Round 1 (Parallel)
Time : 10.00am — 10.30am (30 minutes)
Scoring : 700-800
Link : https://cf17-tournament-round1-open.contest.atcoder.jp/
CODE FESTIVAL 2017 Elimination Tournament Round 2 (Parallel)
Time : 10.45am — 11.15am (30 minutes)
Scoring : 700-900
Link : https://cf17-tournament-round2-open.contest.atcoder.jp/
CODE FESTIVAL 2017 Elimination Tournament Round 3 (Parallel)
Time : 11.30am — 12.10pm (40 minutes)
Scoring : 800-1000
Link : https://cf17-tournament-round3-open.contest.atcoder.jp/
Code Festival Team Relay (Parallel)
Time : 3:30pm — 5pm (1 hour 30 minutes)
Scoring : 100-100-100-100-100-100-100-100-100-100-100
Link : https://cf17-relay-open.contest.atcoder.jp/
Is there a list of official participants somewhere?
I'm confused, what are these contests about? Final is usually the last round (that's what "final" means), here it's first? If the rest happens after the final, what's the point?
To have fun in so many ways
Sorry the list of participants is not publicly available now, but you will be able to see the standings during the contest.
Will there be a broadcast like last year? My guess is not (because parallel round), but confirm it just for know.
No (last year broadcast was for grand final).
Onsite competition scoreboard ?
https://cf17-final.contest.atcoder.jp/standings#page_1
Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
Can someone explain the solution to Problem H? I don't really get what the editorial is trying to say.
Maybe the solution from ksun48 could help you. It implements the part of "Similar transition for four directions" from the editorial in an elegant way lol.
How to solve CODE FESTIVAL 2017 Exhibition — Increment and Swap ?
May i ask how to solve problem A-Awkward?
Use inclusion-exclusion principle: for each k — number of edges we add to the answer ( - 1)k times number of ways to choose k edges denoting prohibited neighbors in the final row. Each set of these k edges adds to the sum ( - 1)k·(n - k)!·2comps, where comps is the number of connected components these k edges form. These values can be calculated with dp(vertex v, number of edges taken in its subtree, number of taken edges incident to v).
We published editorial: https://cf17-exhibition-open.contest.atcoder.jp/editorial.
My solution of J (which turned out to be different from model solution and all other contestant's solution)
Use centroid decomposition. Our strategy is to extract O(n) important edge in each decomposition stage, resulting in O(nlgn) candidate edges that's sufficient to calculate MST.
Say that every path should pass the centroid c. Then the edge cost will be Xu + Xv + dist(c, u) + dist(c, v) (Maybe it have shorter edges, but such case is resolved in deeper recursion stage) Let Yi = Xi + dist(c, i). Then we should solve this problem : "For a complete graph with edge cost Ci + Cj when C1, ..., Cn is given, find it's MST". We can see that our MST will look like a star centering a vertex with minimum Ci.
This solution is quite easy to code (I spent about less than 10 minutes) https://cf17-final.contest.atcoder.jp/submissions/1804911
Cool solution:) I didn't come up with. (maroonrk's solution in the parallel contest was same.)
The intended solution was O(N log N) but there is an O(N) solution (wow) by yutaka1999 as below.
First, process just one step of Borůvka's algorithm as same as the intended solution.
Then the vertices are divided into some connected components. It can be proved from the property of f(u, v) that each component is also connected in the given tree.
Last, for each edge on the given tree connecting vertices from different components (let's call them A and B), choose the edge uv with the minimum value of f(u, v) such that u,v is from A,B respectively.
source code
Note that the intended solution and this solution is much slower than expected from the time complexity due to a heavy constant factor.
Finally, I got the 1st place in Code Festival 2017 Relay (Parallel). Thank you for all!!!
I can't read/submit any problems to "Code Festival Team Relay (Parallel)" after contest ends. (without registration in the real-time contest). Please fix this? (Or it is not a bug?)
Question irrelevant to this event, but does AtCoder plans on having virtual contests? Would be great to have them
AtCoder don’t support virtual contest, but we have two options to do virtual contest of AtCoder problems:
- Use vjudge (Link) To use this for hosting virtual contest, you have to input problem ID for choosing problems. For example, problems ID of Code Festival 2017 Final are 3602 — 3611, in order. You can know problem ID to jump the link of the submit page of desired problem, and look the link name for example of “https://cf17-final-open.contest.atcoder.jp/submit?task_id=3602#” (In this case problem ID is 3602) But in this way, it took long time for searching problem ID.
- Use AtCoder Virtual Contest (Link) though it is easy to prepare for a virtual contest, its language is Japanese, so it’s difficult to use for people who aren’t Japanese.
So, we can do virtual contest, but in both way it is difficult to use. Hope AtCoder will make a convenient system of virtual contest like Codeforces.But are these virtual contests with online standings as from actual competition? It is kinda essential to have them, otherwise I could just measure my time.
Yes, Virtual Judge supports it! Please refer to Introduction to Replay