BINFUN - Binary concatenation - Submission
Finding the maximum difference between a pair of elements from an array is a classical problem. It comes down to finding the maximum value and the minimum value and taking the difference between the two.
But we need to adapt that approach to this problem; just finding the maximum and minimum doesn’t work, the other item of the pair influences the contribution made by the first item.
Suppose (A_i,A_j) is the optimal pair. let A_i have n bits and A_j have m bits. Then the BinaryConcatenation of them will be A_i(2^m-1)-A_j(2^n-1). The contribution of each element depends only on the number of bits in the others representation. Instead of looping over each pair of elements we can instead loop over each element and the number of bits in the other.
I used two arrays maxValues[60][60] and minValues[60][60] that in each cell at index [i][j] contains the maximum and minimum contribution for values with i bits and we assume the other value has j bits. Then I loop over all possible pairs (i,j) and find the maximum value of maxValues[i][j] - minValues[j][i].
GOLOMB - Golomb Sequence - Submission
I precalculate three arrays:
- The golomb sequence
GB - The cumulative golomb sequence
GC. Due to how the golomb sequence is define GC[i] will be the index of the last occurance of i in the golomb sequnce - The sum of squares of the golomb sequence for each range
1...GC[i]. I give a better definition of this array in a comment below
This can be done quite trivially. For (1) use the recursive definition from the statement. For (2) the standard approach for calculating the cumulative array. For (3) add golomb[i] * i * i to the previous value
Then answering queries becomes rather simple. For the range L...R calculate the answer for 1...R and 1...L-1, their difference is the answer. Now if we want to find the answer for 1...R we first use binary search on GC to find the value v at index R. We then observe that the difference for 1...R and 1...GC[v-1] is a sequence of only v's, of which it is trivial to calculate their sum of squares. The answer for 1...GC[v-1] was already calculated in (3)
PRT2 - Profitable Paths 2 - Submission
The main observation is that we want to find the shortest path between two leaf nodes. By doing so we can visit the large values as often as possible. We find the shortest leaf-leaf distance by running a BFS starting at all leafs. Whenever we encounter a node that was already visited we have our shortest path of length l.
Now we can think of the graph as a line graph with l nodes. On this graph we can only walk back and forward. We first calculate how often we can walk from the start to the end and back (\lfloor K/2l\rfloor). We also calculate twice the sum of the l largest values. The product of those gets us most of the way to finding the answer. We only need to figure out how to use the remaining K\mod 2l steps.
This is done by walking from a node somewhere in the middle, to an end and then back to the node we started (or one further). This way we can visit the largest values twice. Note that if the remaining K is greater than 2 we can visit the largest value twice, but if it is exactly 2 we can’t. Make sure to consider that edge case.
POPF - Pairs of Pairs
Not attempted
COPAIR - Coloured Pairs
Not attempted
