So round 1 looks like it is going to be a bit silly this year, 750 to advance per round, 3 rounds, 250 byes, but only 1371 people registered for R1A. Unless a bunch of people forgot about R1A, everyone with a positive score in R1B will advance, let alone R1C…
I had a poorly written solution to Q1 and a decent solution to Q2, but ran out of time to really think through Q3. Both my submitted solutions passed, regardless of how wrong my solution to Q1 was in theory…
In the end the positive score criterion came in to play, only 700 people advanced, the rest got 0 points or lower. I was in 221st, not an amazing effort considering the 250 byes, but not bad. My rating even went up a tiny bit, 1805.
Q1) Given an inclusive range, determine the greatest number of distinct common digits between any pair of numbers.
A1) I wrote a brute force solution, which I limited to running if the range was 200 in length or less, then for the rest I checked each number against single pair digit switches, if the resulting number was in the range that was a pair to consider, if not I presumed that it could be paired with one of its neighbours, to give distinct count of digits in itself – 1. There are numerous flaws in this approach, but I couldn’t work out how to actually exploit any of them, as they only overestimated in scenarios where another valid option was better anyway, and seemingly never underestimated.
The better approach (far better) is to create a 10 bit mask out of each input, for the distinct digits present. Then tabulate the masks. Result is then the best bit count out of any mask with a count > 1, or of the ‘&’ of any two bit masks both with counts > 0.
Q2) Given a directed graph with exactly one edge leaving each node (which can return to self) determine the number of subsets of the graph which can follow there edges for up to K times without the new subset being any smaller.
A2) Two tricks here. 1) K can be huge, but the graph only has at most 50 nodes. So it is fairly obvious that K > 2500 can just be considered as K = 2500 as any pair of nodes which might eventually map together will have a cycle length each of at most 50, and hence will either never meet, or meet in under 2500 steps. Indeed this seems like a very conservative analysis, I think they either never meet or since they end up in the same cycle its at most 50 ‘pre-cycle’ links before they meet. 2) We just need to consider whether any pair of nodes eventually maps to the same place. Once these pairs are found, they transitively form in to groups in which every pair collapses.
Together this means there are at most 2500 scenarios needing at most 2500 (or 50) steps of simulation, which will run quickly.
Once the groups are identified by simulation the the result is the product of the values of size of each group + 1. This is because for each group either nothing is selected, or at most one element is selected. Any node which doesn’t find a pair with any other node is in a group by itself, causing a multiple of 2, which leads to the worst case value of 2^50 as expected in the case where every node is independent.
Q3) Given a weighted bipartite graph, determine the minimum edge removal cost to ensure there is no perfect matching.
A3) So I’m still trying to understand the solutions I’ve read here, but basically it considers every non-empty subset of the one side of the graph, determines the cost to disconnect each node in the other side of the graph from that subset, and considers a possible minimum as disconnecting the cheapest x nodes, where x is the number of nodes in one side of the graph – the size of the subset + 1. For the case of subset is everything, this corresponds to disconnecting one node entirely. In the case the subset is a single node, it corresponds to disconnecting everything from that node. In between it covers the other cases like if 2 nodes are disconnected from everything except 1, they can’t be perfectly matched due to pigeon hole principle.
Only thing I’m not clear on is the proof that every non-perfect matching scenario can be reduced to x nodes disconnected from n-x+1 nodes. The reverse is obvious every such scenario is non-perfect matching, but the equivalence is not so much…