Solution explanations and implementations (in C++) for problems S1-S4 on the 2010 Canadian Computing Competition.
Will be updated to include S5 once I manage to AC it.*
S1
This problem is quite straightforward. The goal is to find and output the names of the two most preferred computers, sorted lexicographically in the case of a tie. The solution I went with is to simply keep an array of pair<int, string>s, sort it with a custom function, and output the first two elements.
S2
The idea for this problem is to keep greedily taking in input until we match a character, then output that character. I kept an unordered_map<string, char> for this.
S3
This problem requires binary search. Start by sorting the positions. Then, write a function which checks if it is possible to cover all houses with a given max hose length. I did this by starting at house[0] and checking if the next closest house is reachable within the remaining hose length. If not, place a fire hydrant at the next house and start checking from there (with the host length restored).
Make sure to check going both directions in the circle. I did this by keeping another array of positions where houses2[i] = (1000000 - houses[i]) % 1000000, then calling the check function twice for each iteration of binary search (once for each array).
S4
(Disclaimer: this solution passes on the CCC grader but not on DMOJ. Will be updated soon.)
Parsing the input is the more difficult part of this question. Essentially, you want to compute the weight sum of the minimum spanning tree of the dual graph. Any MST algorithm will work; I used Kruskal's algorithm.
To parse the input into the dual graph, keep a map<array<int, 3>, int> which maps an edge on the original graph to the index of one of the pens. When parsing, if an entry already exists for the edge in the map, add an edge of the dual graph to an edge list (vector<array<int, 3>>) and erase that entry from the map. In the end, whatever is left in the map is supposed to be connected to the outside, so add edges to the edge list for that as well. Refer to the implementation above if this is confusing.
When computing the MST, keep track of the degree of the outside node and keep a sum of the weights of edges added to the MST which connect to the outside node. Once the MST is found, if the degree of the outside node is less than 2, subtract the sum from the total answer (this essentially ignores the outside node).