December 28, 2020 Single Round Match 796 Editorials

Thanks to misof for writing the editorial.

ChristmasCrackerHappiness

Currently, the number of happy people is equal to the number of distinct numbers in the array winner. There are many different ways how to count them: for example, you can throw all of them into a set (which discards duplicates) and then look at the set’s size. You can also sort the array and traverse it, you can use an array of booleans to store who’s happy, and you can even afford to traverse the entire array of winners N times, each time checking for a different guest.

If you have at most one unhappy guest, you are done. Otherwise you need to make some guests happy. Here you only need two more observations:

• Each cracker only has one winner, so if you currently have U unhappy people, you need at least U-1 additional crackers.
• If you give a cracker to two unhappy people, it will certainly make one of them happy. So U-1 additional crackers is sufficient. (As long as you have at least two unhappy people, pick any two and give them a cracker.)

Sample implementation:

	public int solve(int N, int[] winner, int[] loser) {
    	    boolean[] happy = new boolean[N]; // initialized to false
    	    for (int w : winner) happy[w] = true;
    	    int unhappyCount = 0;
    	    for (boolean h : happy) if (!h) ++unhappyCount;
    	    return Math.max(0, unhappyCount-1);
	}

ChristmasLightsFixing

Example annotations were trying to guide you along the right way: we need to skip large batches of steps to get to the correct one quickly.

The tool we’ll need are binomial coefficients: the values choose[n][k] that tell us in how many ways we can choose a k-element subset of an n-element set. We can compute these into a 2D array using a simple formula:

• choose[n][0] = 1 (there is exactly one way to select nothing) and choose[n][n] = 1 (exactly one way to select everything)
• for 0<k<n we have choose[n][k] = choose[n-1][k-1] + choose[n-1][k].

For the proof of the last formula, suppose we take one of the n items in our set and paint it red. In how many ways can we select k out of these n items? Either we include the red item in our selection, or we don’t. If we do, we need to select k-1 additional items out of the n-1 remaining ones. If we don’t, all k items must be selected from the n-1 remaining ones.

For a fixed n, the sum of all choose[n][k] is 2^n: the number of all possible subsets of an n-element set. Thus, we know that these values won’t overflow a 64-bit integer for our constraints.

Now that we have these values, we can easily find the correct size of the subset that corresponds to the given step. For example, if we have N=7 and step=47 as in the last example, we can count as follows:

• There are choose[7][1] = 7 one-element sets. These correspond to steps 1-7.
• There are choose[7][2] = 21 two-element sets. These correspond to steps 8-28.
• There are choose[7][3] = 35 three-element sets. These correspond to steps 29-63, which includes step #47. Thus, step #47 is some three-element set.

And we can now construct the specific set by going through the values it may contain and counting in the exact same way.

• The list of three-element sets starts with sets that contain 0. How many of these are there? We need to select two more values out of six available ones (1-6), so there are choose[6][2] = 15 such sets. These correspond to steps 29-43. As we want step 47, we know that our set does not contain 0.
• Now come three-element sets where the smallest element is 1. How many of these are there? This time it’s choose[5][2] = 10. These sets correspond to steps 44-53. As 47 is among these steps, our set does contain 1.
• Now we are looking for the rest of our set. Steps 44-53 are all possible sets of the form {1, x, y}. We can now go through all possibilities for x, and once we know x, find the right y.

During implementation a nice trick is that whenever you find that you can skip an entire group of steps, subtract its size from the step you are looking for. Another nice trick is to use numbering starting from zero, it usually has fewer special cases. In this problem, we can directly assume that we are numbering the steps from zero if we include the empty set as step 0. The above solution then looks as follows:

• We are looking for step 47.
• There is one empty set. Thus, we are looking for set number 46 in the rest of the sequence.
• There are 7 one-element sets. Thus, we are looking for set number 46-7 = 39 in the rest of the sequence.
• There are 21 two-element sets. Thus, we are looking for set number 39-21 = 18 in the rest of the sequence.
• There are 35 three-element sets. As 35 > 18, our set is among them.
• There are 15 three-element sets that start with a zero. Thus, we are looking for set number 3 in the rest of the sequence.
• There are 10 three-element sets that starts with a one. As 10 > 3, ours is among them.
• We are now looking for set number 3 in the sequence of all two-element subsets of {2,…,6}.
• There are choose[4][1] = 4 such sets that begin with a 2. As 4 > 3, ours is among them. Thus, our set is {1,2,?}.
• We are now looking for set number 3 in the sequence of all one-element subsets of {3,…,6}.
• There are choose[3][0] = 1 such sets that begin with a 3. We want set 2 in the rest of the sequence.
• There are choose[2][0] = 1 such sets that begin with a 4. We want set 1 in the rest of the sequence.
• There are choose[1][0] = 1 such sets that begin with a 5. We want set 0 in the rest of the sequence.
• There are choose[0][0] = 1 such sets that begin with a 6. As 1 > 0, our set does contain the 6 and we are done.

Sample implementation:

public int[] fixingTime(int N, long step) {
    	long[][] binomial = new long[N+1][];
    	binomial[0] = new long[1];
    	binomial[0][0] = 1;
    	for (int n=1; n<=N; ++n) {
        	binomial[n] = new long[n+1];
        	binomial[n][0] = binomial[n][n] = 1;
        	for (int k=1; k<n; ++k) {
binomial[n][k] = binomial[n-1][k-1] + binomial[n-1][k];
}
    	}

    	int[] answer = new int[0];
    	for (int len=0; len<=N; ++len) {
        	if (step < binomial[N][len]) {
            	// we have the correct length 
// and step is now the correct 0-based index within that list
            	answer = new int[len];
            	int cur = 0;
            	for (int n=0; n<N && cur<len; ++n) {
                	// do we use n or do we skip it?
                	if (step < binomial[N-n-1][len-cur-1]) {
          		          	answer[cur++] = n;
                	} else {
                	    	step -= binomial[N-n-1][len-cur-1];
                	}
            	}
            	break;
        	} else {
            	step -= binomial[N][len];
        	}
    	}

    	return answer;
}

ChristmasBatteries

There are two easy ways to solve this problem.

One is to use dynamic programming. Let dp[i][j] be the most fun we can have if we select things that require a total of j batteries from among things with the i smallest numbers. The answer we seek is then the maximum of all dp[N][j] where j is at most B.

The values dp[i][j] can be computed as follows:

• As the base case, dp[0][j] = 0 because no things = no fun.
• If thing x requires b batteries and gives f fun:
  • We cannot use it in solutions to subproblems that use fewer than b batteries: for j < b we have dp[x+1][j] = dp[x][j].
  • In subproblems where we have j >= b batteries, we have two options: either we take thing x or we don’t. If we do, the best solution we can get consists of thing x + the best solution we can get from previous things using j-b batteries. If we don’t, the best solution we can get is the best solution we can get from previous things using all j batteries. Thus:
    dp[x+1][j] = max( dp[x][j-b] + f, dp[x][j] )

If you aren’t experienced in dynamic programming and coming up with the above solution feels like black magic, there is also a completely different solution that only uses greedy and brute force. We will make the following observations:

• We can always take all things that don’t require any batteries.
• Let’s divide the other things into piles based on how many batteries they need. Look at the pile of things that need x batteries each. How many things from this pile can we give our niece? Clearly, at most (B div x).
• And if we decide how many things from a specific pile we want to give our niece, which ones should it be? Clearly, the ones that are the most fun.

Thus, each optimal solution will contain:

• From the most fun one-battery things, at most 7/1 = 7.
• From the most fun two-battery things, at most 7/2 = 3.
• From the most fun three-battery things, at most 7/3 = 2.
• Maybe the most fun four-battery thing.
• Maybe the most fun five-battery thing.

We can now sort each pile and discard the things that certainly won’t be used in the optimal solution. We will be left with at most 7+3+2+1+1 = 14 candidates. And we can iterate over all 2^14 subsets of these candidates, check which ones use at most B batteries in total, and pick the most fun out of those.

ChristmasSnake

Let’s divide the game world into three zones as follows:

11111111
12222221
12333321
12333321
12333321
12333321
12222221
11111111

Here are some observations we can make:

• The empty zone 1 consists of 28 cells. The other two zones together contain 36 cells.
• If the snake has at most 8 cells, it is so short that all empty cells are clearly reachable from its head.
• If the snake has at least 9 cells, zones 2+3 contain at most 27 empty cells.
• Thus, the condition that a majority of empty cells is clearly reachable tells us that some cell on the boundary of the square (in zone 1) is clearly reachable.
• Zone 1 is longer than the snake.
• Thus, there is a valid way to turn the snake around that looks as follows: the head goes to zone 1, then makes a full circle around zone 1 (so that the entire snake is now in zone 1) and then it is free to retrace its path back to its original location (using cells that were initially free, thus leaving the original location of its body untouched) and finally the head walk along the original body of the snake.

Suppose we take the shortest path to zone 1. What is the maximum length of the above solution?

The head of the snake first makes some steps in zone 3. As this is a shortest path, it cannot touch itself, and we can easily verify that the longest such path has 10 steps. Thus, after step 11 or sooner the head must enter zone 2. But zone 2 is already adjacent to the empty zone 1, and therefore the head will certainly reach the boundary after at most 12 steps.

This gives us an upper bound of 12 steps to reach the boundary, 28 steps for the circle around, 12 steps to return the head along the same path back, and finally at most 25 steps to walk the head along the cells where the snake started. The total of those counts is at most 77 steps.

ChristmasTwins

Clearly a necessary condition for a solution to exist is that the number N of # cells must be even.

We will show that the task has a solution that runs in O(poly * 2^(N/2)). (The actual number of valid cuts turns out to be much smaller than that.)

Suppose we label the # cells from 0 to N-1. One of the twins will get the part of the cake that contains cell 0. The other twin will get a part that looks the same. If we map the second part to the first one, some cell in the second part will correspond to cell 0 in the first part. We can generate all candidate solutions by iterating over all possibilities which cell P this is, and what transformation is used. The latter has only 8 options: if we move from cell 0 in the +row direction, there are four options for the corresponding movement from cell P, and once we choose that, we can choose either of the two orthogonal directions as corresponding to the movement from cell 0 in the +column direction.

Thus, we have only 8N possible maps that transform one part of the cake into the other. We will consider the maps in the direction that maps the part with cell 0 (“the first part”) onto the other (“second”) part of the cake.

On the infinite plane, each such map is a bijection. Thus, if we restrict it to our finite set of N cells, it will be an injection: some cells will map onto other valid cells, other cells won’t. The graph will consist of some paths and some cycles.

Paths are forced. The starting vertex of each path must be in the first part. The next vertex must then be in the second part. If there is a third vertex, it must again be in the first part. (It cannot be in the second part because each vertex in the second part needs a vertex in the first part that maps onto it.) And so on. Thus, if we have a path of an even length, we split it between the two parts. A path of an odd length immediately means that there is no valid division (each such path creates more cells in the first part than in the second part, and we won’t have any way to get rid of this bias). 

Cycles work similarly. A cycle of an odd length (exercise: can there be such a cycle of length other than 1?) is a contradiction. A cycle of an even length has two options: the cells at even positions must belong into one part and the remaining ones into the other part, but we don’t know which is which.

With N cells we can have at most N/2 even-length cycles. For the time complexity promised above, it is now enough to iterate over both possibilities for each of the cycles. For each of those, we can then check whether one part is contiguous and if yes, we can insert it into a set of solutions. (This last step is necessary because some valid cuts of the cake may correspond to more than one map. We actually need just 2^(N/2 – 1) possibilities because whenever 0 and P are on a cycle, we know how to split that one.)

Finally, note that the time complexity estimate is very loose, because it is impossible for all maps to produce N/2 cycles of length 2. (The worst case, all cells split into N/2 cycles of length 2, corresponds only to a subset of maps that are symmetries of the entire input image.)

For an alternate solution, it is probably also possible to get accepted with a well-pruned solution that iterates over all maps, as defined above, and then tries all possibilities how to “grow” both components from 0 and P at the same time. As the final answer is always very small for the given constraints, if we can prune enough branches that cannot produce a valid solution, this approach should also be fast enough.