The University of Alberta would like to invite you to participate in the open division of the University of Alberta Programming Contest 2023.
(This image is more relevant for in-person participants, but it's all I have c:)
The contest starts on March 11 at 11am Mountain Time.
The open division will be held on Kattis at uapc23open.kattis.com. Closer to the start of the contest, a button will appear on that site allowing you to join the contest — there is no need to register ahead of time.
The format for teams competing in person is a team-of-<=3 four-hour contest with one computer. While we encourage those participating in the open division to replicate these conditions as closely as possible (since this is what the contest was designed for), we recognize this may not be possible or wanted for some. Teams/individuals competing in the open division are not bound by the same rules as those competing in-person. Note that there are no prizes for the open division.
The difficulty of the contest will be comparable to some of the easier NA ICPC regionals such as rocky mountain regional. To get a better idea of the expected difficulty, you can view the problems from last year.
We hope you participate in and enjoy the contest :)
Where can we upsolve problems?
It should be possible on the same website by removing "contests/stuff" from the URL. Eventually, the problems will be available on open kattis.
How to solve K? It's easy to shrink $$$l$$$ to $$$nd$$$ but it's still unclear what to do next.
We can start with any of the input strings. If it has distance at most D from all other strings then we are done. Otherwise, there is a string it is at least D+1 away from, so we certainly have to change one of those positions. Try all D+1 options. For each of these repeat with a new candidate string. We should never recurse past D levels or else we will end up too far from our starting string, so we have depth D and branching factor D+1. Total runtime O(N*D*(D+1)^D).
Why is the branching factor D+1?
Try all D+1 options.Couldn't it be the case there are more than D+1 options? (Up to 2*D I think?)If there are more, it doesn't matter. Among the first D+1 differences, you certainly need to change at least one position.
Ah yes, that makes sense, thank you!