NailingABanner
After we finished the setup by placing the first two nails, the banner is one large interval of length 2^60.
Then:
In the first round we place one nail (i.e., 2^0 nails) and divide the interval into two, each of length 2^59.
In the second round we place 2^1 nails and divide those intervals into halves, producing four intervals of length 2^58.
In the third round we place 2^2 nails to split those intervals into 2^3 intervals of length 2^57 each.
And so on.
We can simulate the process one round at a time, until we get to the round in which we place nail number N.
For example, suppose N = 20. In the setup and first four rounds we place 2 + 1 + 2 + 4 + 8 = 17 nails. Then, in round five we place the next 16 nails, i.e., nails with numbers 18, …, 33. Nail 20 is the nail that’s third among these, so it is used to split the third of the 16 intervals we currently have.
public long coordinate(long N) {
if (N == 1) return 0;
if (N == 2) return 1L << 60;
N -= 2;
for (int round=1; ; ++round) {
long placed_this_round = 1L << (round-1);
if (placed_this_round < N) {
N -= placed_this_round;
continue;
}
long first_index = 1L << (60-round);
return (2*N - 1) * first_index;
}
}
BannerWithNails
Now we are asked to do the same thing in reverse: given the coordinate of a nail, determine its number. We can split this into two steps: from the coordinate we will first determine the round in which the nail was placed, and then from that we will determine its exact number.
The two initial nails are placed at multiples of 2^60. After the first round we have nails at all multiples of 2^59. After the second round we have nails precisely at all multiples of 2^58. And so on.
Once we observe this, we should be able to tell that the round in which a nail is placed is determined by the highest power of 2 that divides its coordinate. In round x we place nails precisely at all odd multiples of 2^(60-x).
More precisely, the nail with number (2a-1)*2^(60-b) is the a-th nail placed during round b.
We can now count all nails placed before round b (either by using a formula for a geometric series, or by summing it up in a cycle) and then add a to get the number of our nail.
public long number(long X) {
if (X == 0) return 1;
if (X == (1L << 60)) return 2;
int round = 1;
while (X % (1L << (60-round)) != 0) ++round;
long in_previous_rounds = 1 + (1L << (round-1));
long odd_number = X / (1L << (60-round));
long in_this_round = (odd_number + 1) / 2;
return in_previous_rounds + in_this_round;
}
SelectFromArrays
There are multiple approaches that work. The shortest code is produced by using dynamic programming: for each n and each triple (a,b,c) we compute the maximum sum we can get by taking the first n elements of each array and among them selecting a from array A, b from array B, and c from array C. Each time we process a new index, we have four options: either we do nothing at this index, or we color an element green in exactly one of the three arrays. Thus, the best solution for any state (n,a,b,c) can be computed by considering these four options for the last index and picking the best one among them.
public int maxSum(int[] A, int[] B, int[] C, int NA, int NB, int NC) {
int N = A.length;
int[][][] dp = new int[NA+1][NB+1][NC+1];
for (int n=0; n<N; ++n) {
for (int a=NA; a=0; --a) for (int b=NB; b=0; --b) for (int c=NC; c=0; --c) {
if (a 0) dp[a][b][c] = Math.max( dp[a][b][c], A[n] + dp[a-1][b][c] );
if (b 0) dp[a][b][c] = Math.max( dp[a][b][c], B[n] + dp[a][b-1][c] );
if (c 0) dp[a][b][c] = Math.max( dp[a][b][c], C[n] + dp[a][b][c-1] );
}
}
return dp[NA][NB][NC];
}
Another approach that is fast enough is based on the observation that we can be mostly greedy with our selection. Let’s look at any one of our three arrays. Suppose we already chose which elements will be green in the other two arrays. What is the optimal way of finishing our solution? Easy: we look at the indices that are still available and we take the largest values we can see.
Hence, in the optimal solution in each array the elements we’ll actually select are among the NA+NB+NC <= 15 largest in that array. (For example, look at the NA+NB+NC largest values in the array C. Regardless of which NA+NB elements we take from arrays A and B, at least NC of these values will still be available, and thus the NC values we’ll actually take in the optimal solution are surely among them.)
This allows us to reduce the search space enough to be able to simply try (almost) all possible answers: there are at most {15 choose 5} = 3003 ways to select the elements from any one individual array, so we can for example try all such ways of selecting elements from A and B and then greedily selecting from C.
Another, somewhat faster implementation that also allows us to reuse code is to implement a function that filters an array. This function is given a bitset with already banned indices and a number x, and it returns x unbanned indices of the largest elements in the array. We can then do the following:
take the indices of NA+NB+NC largest elements of A
iterate over all ways of taking NA from those, and for each of them:
take the indices of NB+NC largest still available elements of B
iterate over all ways of taking NB from those, and for each of them:
take the indices of NC largest still available elements of C
process these as the optimal selection from C that goes with the current selection from A and B
take the best among all solutions constructed by following the steps given above
LogarithmCircuit
The first useful observation is that the floor of the binary logarithm of N has another, more useful definition: it is simply the index of the largest 1 bit in the input. (E.g., all numbers x in the half-open interval [2^10, 2^11) have floor(log2(x)) = 10 and in all of them 2^10 is the highest set bit.)
We will show one possible way of constructing a circuit that locates the highest set bit among n input bits with time complexity O(log n).
Our solution will consist of three phases:
First we propagate each 1 bit downwards. For example, we will turn 0010100100 into 0011111111.
Then we isolate only the highest set bit. For example, we will turn 0011111111 into 0010000000.
Finally we will calculate the binary representation of the number of the only set bit.
The final circuit will be a composition of three separate circuits, one for each phase. The circuits for the first two phases will have n inputs and n outputs, the circuit for the last phase will have n inputs and log(n) outputs. Below we’ll construct each of these circuits separately, and during its construction we’ll assume that its inputs are numbered from 0 to n-1.
The first phase can be done in O(log n) layers of OR gates. This part of the circuit will have n inputs and n outputs, and output x is the OR of all inputs with numbers x or greater. (If the current bit and all higher bits in the output are zeros, it remains zero, if any of them is a 1, it becomes 1.)
The second phase will consist of a single layer of XOR gates. All we need to do is to XOR each wire with the immediately more significant one. (“If the next higher bit is the same as me, I should become 0.”)
For the final phase, let’s look at one specific bit of the result. When should the output bit that represents 2^x be set? If and only if the input wire that has the value 1 is among the wires whose numbers in binary contain the bit x. Thus, we can simply set the x-th bit of the output number to the OR of all those wires. (For example, the output bit 0 will be the OR of wires 1, 3, 5, 7, 9, … and the output bit 1 will be the OR of wires 2, 3, 6, 7, 10, 11, …) As there are at most n wires, we can compute the OR of any subset of wires using O(log n) layers of binary OR gates.
The image below shows a sample circuit for 8 inputs (most significant one is on the top). Multi-input OR gates are used in the third phase to keep the image simpler.
DistanceSumTree
Consider any edge in the tree. Removing this edge will split the tree into two parts. Let X be the number of vertices in one of them. Then, this edge is contained precisely in X*(N-X) distances - it lies on each path that have one endpoint in each part of the tree. The value X*(N-X) will be called the weight of the edge.
Below, we will use the phrase “the value of the tree” as shorthand for the sum of all distances between the unordered pairs of its vertices. From the above observation it follows that the value of the tree can be computed by summing up length*weight over all edges.
This gives us a quick way of computing all possible values for a tree of a given shape: we just do a knapsack-style dynamic programming where we process the edges one at a time and for each edge we try all possibilities for its length.
One observation we can make at this moment is that for most trees (notably including paths) the weights of different edges will often be coprime, which leads to the situation that in the above knapsack we should expect that there will be a large range of consecutive values that are all reachable. This will be useful later.
Let’s now consider the question of the largest possible value of the tree. This is clearly obtained by taking the tree with unit length edges and largest possible value among those, and setting all edge lengths to their maximum value. So, let’s look at those.
Consider any path between two leaves of the tree. Let x be an inner vertex on that path and let xy be an edge of the tree such that y does not lie on the path. Removal of the edge xy would split the tree into two parts (one containing the vertex y, the other containing the whole path, both may contain extra vertices). Now consider connecting y to another vertex on the path instead - imagine taking the endpoint of the edge xy that is currently at x and moving it along the path in either direction. As we start moving x in one direction, we are moving everything in the other part of the tree closer to some vertices and away from some other vertices. If we instead move x in the opposite direction, we are moving the other part of the tree closer to some other set of vertices, and this set is disjoint with the previous one. Thus, at least one direction of moving must be such that it increases the sum of distances (possibly keeping it constant for one step, then it has to strictly increase) because we are moving x away from at least one half of all vertices in the part with the path.
By repeatedly using the above operation we can easily show that among unit length trees of a fixed size N the one with the largest value is the path, and the second best tree is a path of length N-1 with one extra vertex attached to a neighbor of one of the path’s endpoints.
We can now use the knapsack algorithm described above to determine the following:
If we only use paths with 2-50 vertices, we can get all possible values in [1,415846] and a few larger values. (The absolutely largest reachable value is 416500 for a path of edges of length 20 each.)
All of those larger values are obtained by assigning large lengths to edges of the path with 50 vertices.
In particular, a path with 50 vertices can have all values in [21479,415846], we only need the shorter paths if we need to produce some of the very small values.
The largest possible value of a tree with 49 vertices is 392000, so trees smaller than 50 won’t produce any new values.
The largest possible value of a tree with 50 vertices that is not a path is 415560, so these trees won’t produce any new values either.
Hence, the above set of possible values is complete. Moreover, we now know that each reachable value can be reached as the value of some path, which makes the construction easy.