The 2018 North Central North America ACM-ICPC Regional Programming Contest is tomorrow, Saturday November 3rd, 4pm UTC. There is an open division for anyone interested in competing at: https://open.kattis.com/contests/ncna18open. The official scoreboard will be at https://ncna18.kattis.com/.
As there is no way to request or issue clarifications in the open division of Kattis, please comment here if any questions arise.
The problem set was created by myself, Alexander Scheel, xennygrimmato, NibNalin, vlyubin, Joshua Guerin, Kathleen Ericson, David Poplawski, and erena. Additional thanks to asdoc, xiaowuc1, and y0105w49 for problem solutions.
EDIT: This is happening in about three hours.
Auto comment: topic has been updated by brycesandlund (previous revision, new revision, compare).
This year’s problem set is nice! Though I got no idea for the two hardest problems.
Was there a solution for D not based on max flow? Also ideas for the two hardest ones?
You can actually observe that from a day to the next day, if for any airport i, the number of people currently at airport i is larger than or equal to the sum of the number of people that the flights leaving airport i requires, then that day is optimal. So you can just do simulation for each day in this way.
Pokegene: Sort the genome strings and create a tree. Reduce the problem to a series of LCA queries.
New Salaries: Come up with a general formula for [Li, Ri], [Lj, Rj] where Li ≤ Lj ≤ Ri ≤ Rj (the case where Ri ≤ Lj instead is easy). For a fixed i, you can compute the sum of expected damages over all relevant j with prefix sum queries.
More details about Pokegene:
If you sort the set of strings in a query, the possible answer ancestors are a prefix of L consecutive strings from this set.
With this observation, you can see that the solution is the sum of the length of the LCPs(longest common prefix) of L sized windows of the sorted set. Now, there are multiple ways to calculate the LCP length for each window, using LCA in trie, hashing+binary search, auxiliary tree etc.
For the LCA in trie approach, notice that the LCP of strings indexed (x, ... x + L - 1) can be found from the LCA of the x th and x + L - 1 th string end nodes in the trie.
There are a couple of edge cases to figure out about strings that are proper prefixes of other strings in the set, but they are relatively trivial.
brycesandlund and I expected this to get more ACs, but I hope everyone still enjoyed the problem. :)
EDIT: This was my first time problem-setting, so let me know if you have any comments or feedback about the problem.
How to solve Problem G Tima goes to Xentopia?
Dijkstra! Make a graph with k1*k2 layers. Add an edge from one layer to another to take a red or blue edge. White edges keep you in the same layer.
Alternatively, dijkstra with state[i][j][k] = t being the min time it takes to arrive at i after using j red and k blue edges.
Yes, this is the same as what I was describing :)
When will the solution slides be posted?
You know, I wasn’t sure people really looked at them last year so I wasn’t sure I was going to make them at all this year. You’re not the first person to ask, though, so I am going to put some solution sketches online. I think I’m going to make them more like what’s been done for the world finals. I can get get them up tomorrow.
Sweet thanks, btw (random digression) I looked the solution slides for last year's contest a while ago, and they were helpful.
Good to hear. I put a decent amount of time into them, actually.
Is there any update on solution sketches? Will they be put on this site?
I just put up a draft of solution sketches on my webpage: http://pages.cs.wisc.edu/~sandlund/NCNA18sketches.pdf. I also uploaded the judging data: http://pages.cs.wisc.edu/~sandlund/NCNA2018Contest.zip.
We will finalize and move them to the Nebraska site shortly.
Actually students from UW-Madison are using the slides last year. I am one of the coach this year and I think some solution sketches will be really helpful, so I am glad to hear you are making it. Thank you!
P.S. Is there another way to solve "New Salaries" without coming up a general formula for the intersecting intervals?
See above. You do need to come up with a formula for two intersecting intervals. This formula can be made to work for all pairs in linear time by maintaining appropriate running sums.
Ok. Thank you! I see the sketches and they are really helpful!
Okay great! I’m glad.