Hi everyone. Thanks for coming to AUCPL Round 2, we hoped you enjoyed it, and we hope these editorials are helpful! As always, feel free to reach out if you can’t understand the solutions or explanations, or if you have any other questions about any of the problems.
You can find me (Patrick) on Discord as _oree.
Created by Ray
This question is meant to test your knowledge of sorting by sorting the input according to a custom metric. This can either be done by using a custom comparator lambda, or by modifying the inputs before using the default sort.
We want to prioritise the last name over first name in the sorting process, so we could simply split by space, swap the names so last name is first, and then use default sort and it’ll give us the correct output.
All of these solutions have a time complexity of $O(n \log n)$, since we sort the input using the standard library sorting functions in both C++ and Python.
Created by Patrick (the original Div A problems were made by Tom)
The intended solution here is to do a brute-force search of every possible combination, comparing every location with every location in the other list, and storing the pair of locations with the maximum distance. This will give a solution with quadratic time complexity $O(nm)$ where $n$ and $m$ are the lengths of each coordinate list, which is generally pretty bad and won’t work with more than ten or a hundred thousand elements. In Div A, teams solved a very similar question but with a more optimal algorithm.
Created by Shahid
In this problem we are looking to merge two sorted lists into a single sorted list. I’m sure you could think of doing this easily by just concatenating the two lists and then sorting the resulting list, but this will have a higher time complexity than we are looking for at $O((m+n)\log(m+n))$, given the lengths of the first and second lists are $m$ and $n$ respectively.
There is a way to merge the two lists in linear time by maintaining two pointers at the start of each array and printing and advancing whichever one points to a smaller element, as well as some bounds checking. This will result in an algorithm that runs in $O(m + n)$.