The 2018 South Central USA (SCUSA) ACM-ICPC Regional Contest is tomorrow, Saturday November 10rd, 6pm UTC. There is an open division for anyone interested in competing at: https://open.kattis.com/contests/scusa18open. The official scoreboard will be at https://scusa18.kattis.com/. Good luck to all competitors!
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, Greg Hamerly, Etienne Vouga, and Rob Hochberg. Thanks to xiaowuc1 for inspiration.
Also thanks to brycesandlund because I copied his NCNA announcement.
EDIT: Contest delayed by 15 minutes. Will start in 10 minutes. Good luck!
Auto comment: topic has been updated by arknave (previous revision, new revision, compare).
Will there be solution slides/editorial?
Slides will be posted to the SCUSA web site in the next day or two. You can also read them from my personal Dropbox here: https://www.dropbox.com/s/ta7x5f9t6i4w228/scusa-2018-slides.pdf?dl=0
Thanks. I enjoyed the contest. Some interesting time limits you guys had there...
Glad you enjoyed it! The time limits in some cases were 2x our python 3 solutions, so a few ended up pretty large. When I was looking over the submissions from our site I didn't see anything egregiously inefficient passing. Did you squeeze anything unintended / have different solutions?
I think my team did everything pretty much the same as explained in the slides. It is just always interesting to get TL's of 10 seconds+ instead of the normal 1/2/3, in my opinion.
I participated in the open division. My team didn't solve C, but another team from my school did by hashing the histograms of the substrings of length k and comparing hashes. Your solution seems more simpler than that.
We were wondering how the described solution to C works in n^2 time. Going from a set of histograms of length k to a set of histograms of length (k-1) would take linear time (modifying all n-k+1 histograms already in the set in constant time each, and then adding a new histogram of length k). Then for each histogram of substrings of length k in A, you would compare to each histogram of substrings of the same length in B to look for a match. That would be n^2 time, and you'd do that for k from 1 to n, taking n^3 time.
Another question we had (and this maybe just be based on our inexperience) was how does min cost flow run under the time limits in J? We felt like 1000 nodes and 1000 edges would be too large to be solved with flow (although we did try it anyway and it passed). Do you have any feedback on this topic?
C — Instead of pairwise comparing against all histograms in B, throw them into a set and check for existence.
J — Ford Fulkerson is O(mF) where m is the number of edges and F is the maximum flow through the graph. Even if we only push one unit of flow through per iteration, the max flow in the graph is at most 10.
Is there judge data available anywhere?