Another week, another round of a coding competition… or so it seems this time of year.
Top 1000 advancing to round 2. The cut-off was fully solving question 2 and the small input of question 1 in 2:20. All small inputs in a fast time came 1035th, which was interestingly close to advancing. The score to get by without having to worry about time was achieved by all small inputs and the large of the first question.
Q1) Given a game where characters can be duplicated and consecutive duplicate characters can be collapsed back to a single character, determine if a set of strings can be made equal, and if so, the minimum number of moves to achieve this goal.
A1) Determining whether the goal can be achieved is easy, just replace all sequences of consecutive repeats with a single character, and determine if all the input strings are equal. This produces a ‘canonical’ form that all must match. For the minimum number of moves it isn’t really that much harder. For the small input there are only 2 strings, so choose one of the strings and count how many moves it takes to make the other equal to it. There is no advantage to trying to meet in the middle, so on a per canonical string character basis just take the absolute difference of the counts in each of the strings and sum them all for the result.
For the large input there are up to 100 strings, but because each string is only at most 100 characters, no letter can be repeated more than 100 times. Therefore the ideal to converge upon will be no more than 100 repeats and no less than 1. Since each character of the canonical form can be considered independently, all possibilities can be easily tested within the time limit. Just try each value of 1 to 100 inclusive and calculate the sum of absolute differences, the smallest sum is the minimum number of moves for that canonical character. Then just sum all of those minimums for the final result.
The most challenging part of this question is probably that the large input is considerably more ‘different’ to the small input, so a bug in the code could easily get past the small input only to fail on the large input, even though it would easily run in time.
For interest, an extension of this question where the maximum length of a given string is unbounded by the maximum length of the canonical form is short, the problem is still easily solved so long as the counts are provided rather than having to parse the unbounded length string. The sum of a set of absolute difference functions all with equal slope has a minimum at the middle of the sorted list of 0 points of the individual functions. For an even number of functions, either of the middle 2 will work because the the sum is flat in between. Thus with a value selected the total of absolute differences can be calculated for a total run time proportional only to the number of strings and the number of characters in the canonical form.
Q2) How many pairs of 2 numbers selected from specific ranges when bitwise ‘and’d together have a result in a 3rd specific range. All ranges start from 0.
A2) Easiest small input ever? With range sizes of only at most 1000 each, nested loop over the input ranges and calculate the and and compare to the maximum value of the 3rd range. If less increase counter. Once loops are done, return counter. 6 trivial lines?
Large input however is much more challenging. With ranges of up to 1 billion, such brute force is out of the question. Given the bitwise and function and the large ranges, running time seems like it will need to be related to the logarithm of the input range maximums.
Determining whether 2 numbers ‘and’ to give a 3rd is trivial, which leads to the thought, is there some way to convert the ranges into batches which can be easily processed in parallel. Perhaps using a ternary notation of 0, 1 and ‘don’t care’?
All numbers less than n can be grouped in a ternary notation by having a prefix which is equal to the start of n, followed by a 0 where there is a 1 in n, followed by ‘don’t care’ for all subsequent bits. The number of such patterns needed is equal to the number of set bits in n, which is worst case proportional to the logarithm of n.
So the problem now boils down to, generate these ternary representations for the 2 input ranges and the output range, then for every way of selecting from those 3 lists, determine how many results it allows. Sum those all up, and return.
So the core part of that is ‘determine how many results it allows’. So inside the triple nested loop to select the 3 ternary representations being tested another loop over each bit is needed. Each bit is independent in the bitwise and, so the number of ways of doing each bit can be considered a multiplier. Multiplying them all together will give the number of solutions that are derived from this particular selection.
Handling each bit can be done with a large if statement selecting on the 3 different values which can be in each of the 2 inputs and the output. For example ‘don’t care’, ‘don’t care’, ‘don’t care’ has 4 possible scenarios and ‘don’t care’, ‘don’t care’, 0 has 3 possible scenarios. Such an if statement is quite large and convoluted, so some more nested loops might be simpler. Loop over each possibility for the 2 inputs, skipping if it doesn’t match the actual input values. Then calculate the and of the 2 input bits and compare it to the expected output value incrementing the counter if it matches. The simple match function for ‘bit vs ternary value’ is handled much more easily than the huge if statement.
One catch is that the 3 ranges originally specified 2 are exclusive and one is inclusive of the maximum, so applying the above approach the inclusive bound needs to be incremented to make it an exclusive bound first. Alternatively all numbers less or equal to n can be considered by using the same set of patterns above and adding the exact pattern of n as well. This is equivalent to setting the bit one past the end of the number to 0 and so can be treated as one extra loop, with appropriate special case handling.
Q3) Given a set of locations with distinct ‘values’ and a list of connections between locations (all locations are connected), determine a order of visiting which doesn’t arrive at any node more than once, but can backtrack as much as you like, which visits every node such that the sequence of first visits is ‘smallest’. Smallest is defined by comparing the first elements of two sequences, then the second elements, and so on until one is smaller than the other.
A3) The small input only had 8 nodes, so brute force was plausible. Just had to make sure you don’t infinite loop.
First thing to realise is that the values of the locations do not matter, so first step is to renumber the graph so that the smallest value is node 0, the second smallest is node 1, and so on. Then the walk of the graph desired is one which prefers smaller node indexes.
The solution seems to be a greedy approach. First thing to realise is that node 0 (in the renumbered scenario) is always the correct place to start – since you can start from anywhere, and it is always possible to walk to every node of a connected graph, starting from any given node even with the additional restrictions specified by the problem.
From that first location you will always walk to the smallest index connected to node 0. But after that it becomes slightly more tricky. More generally the problem becomes deciding what to do when you have visited a set of nodes V and have a current path from node 0 to current node N. For each of the nodes on the path, you can go to any of the nodes not in V that are connected to the node in the path. This leads to a set of scenarios which need to be prioritized for the greedy approach. The obvious priority is the index of the destination. It is always preferable to go to a smaller index if possible. However we need to break ties as the graph can be fully connected, in which case it is possible to reach every node from every node. Here the idea is that deeper in the path is better. Every time you backtrack you lose the possibility of going from that node in future, so it is kind of an opportunity cost.
So that seems pretty simple – but just choosing the best value from the set of scenarios, doesn’t always work. The problem is that it may cause you to back track to take a link to a low index node, but there might be nodes that can only be reached through the node you backtracked from, and there is no way to get back to that node any more. Therefore before taking any option in the priority order of options, you must perform a reachability check. A recursive walk from each node in the potential future path, out in to the world not visiting anywhere already visited, do you visit every node not already visited? If the reachability check fails, that option must be discarded and the next highest priority considered.
The running time of this algorithm is a bit complicated, but an easy upper bound can be found. There are O(N) steps. Worst of these steps has O(N) nodes on the current path. This results in O(N^2) possible scenarios to consider. Each of which could require a reachability analysis which takes O(E) or O(N^2). Thus an easy upper bound is O(N^5) which with 50 nodes is fine. In practice the cases with high number of scenarios at a given step also tend to pass reachability easily, so the code runs within time with ease.