Single Round Match 773 Editorials
Christmas Crackers
If each of N people wants to crack at least C crackers, we need at least N*C/2 crackers total (because each cracker is cracked by two people). If N*C is odd, this number is not an integer: for example, if 3 people want to crack 3 crackers each, we need at least 4.5 crackers - and thus the smallest integer number of crackers is 5. In general, we need at least ceiling(N*C/2) crackers.
This can always be done. Probably the easiest way to do it is to assign the people to crack crackers in a “round-robin” fashion: 0,1,2...,n-1,0,1,2,...,n-1, and so on. Thus, if N*C is even, we can simply return an array in which the sequence 0,1,...,n-1 is repeated C times, and if N*C is odd, the returned array will contain an extra 0 (or any other number) at the end.
Christmas Pudding
If we look at an optimal solution, we can observe the following properties:
a sweet pudding will only be touched if all the tastier sweet puddings have been eaten completely
a savory pudding will only be touched if all the tastier puddings (of any kind) have been eaten completely
In both cases the reason is obvious: in the opposite situation there would be a better solution that includes eating fewer spoons of this pudding and more spoons of that tastier one.
Thus, we can construct the optimal solution greedily as follows:
Order all puddings according to their tastiness in decreasing order.
Go through all the puddings and whenever you encouter a sweet pudding, eat from it. Do this until you either filled in the minimum requirement on sweet pudding, or until you have eaten all sweet puddings, whichever happens sooner. (Note that if we, for example, still need at least 30 spoons of a sweet pudding and we encounter a sweet pudding that has 100 spoons, at this point we only eat 30 of them.)
Go once again through all the puddings (in decreasing order of tastiness), this time considering both savory puddings and uneaten sweet puddings. Eat them until you reach the requirement on total consumption, or until you eat them all.
The time complexity is O(n log n), where n is the number of puddings. (Interestingly, the task can also be solved without sorting, in O(n) time. Can you see how?)
Christmas Song Broadcast
Consider a graph in which the households are vertices and calls are (undirected, weighted) edges. Add another vertex representing the broadcast center, and edges between that vertex and the households representing all possible uses of the towers. In this graph, the optimal broadcast schedule corresponds to the minimum spanning tree (MST). This is because the set of edges we’ll use must make the graph connected, so we cannot do better, and if we choose any minimum spanning tree, we can use it to make a valid broadcast e.g. by doing BFS from the broadcast center.
The graph has at most 51 vertices, so we can use any polynomial MST algorithm (e.g., Jarník-Prim or Kruskal).
The only remaining issue is the huge number of “tower” edges. To get rid of these, we need to solve one more subproblem: for each household, what is the cheapest tower we should use?
Mathematically, we have the following question: find the smallest among the numbers of the form (Ax+B) mod (10^9 + 7), where x is in {0,...,T-1}.
We know that the number A is in [1,100]. Thus, the answer is either B (if Ax+B never exceeds 10^9+7) or it is at most 99 (as the first time Ax+B exceeds 10^9+7, the value of that term will be at most 99). Thus, one straightforward way is to solve the equation Ax+B = y for each y in [0,99] and pick the smallest one for which x<T, if any.
Another solution is to just traverse all possible x in a more efficient way: if you know the current value of (Ax+B) mod (10^9+7), in constant time you can compute the next x such that Ax+B will exceed 10^9+7 and jump straight to that value. This approach is probably more error-prone but it only uses highschool mathematics, as opposed to the previous solution (which needs to compute A^(-1) efficiently in order to solve the equation quickly).
Christmas Travel
If we have N airports, there are N(N-1)/2 pairs of airports, so that is the maximum number of airlines we can have. What is the minimum? We’ll show that with A airlines we can have at most 2^A airports.
Claim: If there are more than 2^A airports, some airline must have an odd cycle.
Proof: By induction. We know it’s true for A=1. Suppose it’s true for some A, and suppose we now have A+1 airlines and more than 2^(A+1) airports. Take any one airline. If this airline has an odd cycle, we are done. If it doesn’t, the graph formed by its flights is bipartite. Take the bigger partition: it has more than 2^A airports and those have to be served by A airlines. From the induction hypothesis it follows that on this graph one of the airlines must have an odd cycle.
This proof also gives us a construction how to serve 2^A airports using A airlines: Split them into halves, have one airline do all traffic between those halves, and solve each half recursively using the remaining airlines.
The full solution now looks as follows:
Given N and A, check whether A is in the range where a solution exists.
Find the smallest A’ such that 2^A’ >= N.
Construct a valid schedule for A’ airlines and 2^A’ airports.
Discard the extra airports to have a valid schedule for A’ airlines and N airports.
While you don’t have enough airlines, take any airline that has multiple pairs of cities and give one of its pairs to a new airline. (Removing flights from an airline will never create an odd cycle for that airline, and an airline with a single edge also doesn’t have any odd cycles.)
Christmas Candy Split
One possible solution is to construct a solution for the set {1,2,...,22} somehow. Then, for any input we can simply fill in the missing numbers and append that solution. This task can be solved on paper, but as the main idea of the construction (at least the one I used) generalizes to an arbitrary test case, I’ll describe that one below. There are also other correct general constructions than the one I describe below. Can you find a more efficient one (in terms of the largest number used)?
We’ll start by addressing a special case: if there is only one number, we do not need to do anything, we already have a valid solution. (The reference solution returns {2x,3x} for the input {x}, just because it can, but returning {} is also valid.)
From this point on, we can assume that the sum S of all the numbers we have is strictly bigger than each of our numbers. The strategy we’ll use will consist of two rounds: first we’ll add some nice multiples of S to make sure that the new sum is divisible by each of the original numbers (except possibly for powers of 2), and then we’ll add some more numbers to make sure the new new sum is divisible also by all the remaining numbers.
After the first phase, we want the new sum to be the multiple of all numbers in the input - i.e., to be a multiple of their least common multiple (LCM). Let’s denote it L. Note that LCM([1,22]) is less than 10^9, so L is always reasonably small.
So, now we have two parameters: S and L. Let’s write L = 2^A * B.
Suppose, for example, that B = 21 = 16 + 8 + 1. Our current sum is 1*S. If we now add the numbers 8*S and 16*S, we will have the sum B*S. This is what we’ll do in the first phase in general: we’ll split B into powers of 2 and add the corresponding multiples of S.
Now all that remains is to add the numbers B*S, 2*B*S, 4*B*S, and so on, until we have a power of 2 that is both at least equal to A and at least equal to the largest power of 2 we used among the numbers added in the first phase. The largest number used is at most equal to SB^2, so for our input it still fits into the given constraints.