Published using Google Docs
Solutions to #8 Counting 15-295 Spring 2021
Updated automatically every 5 minutes

15295 Spring 2021 #8 Counting -- Problem Discussion

March 24, 2021

        

This is where we collectively describe algorithms for these problems.  To see the problem statements and scoreboard, go to this page and select this contest.

A. Random Sort

The answer is just the product of freq[z]! For all z in the array, where freq[z] is the frequency of z (number of its occurrences). Easy way to see this: the result has to be the sorted array, and we can only arrange elements of equal value, and we can arrange them in any order we want (there are freq[z]! Ways to arrange the elements with value z, so the product gives us the answer).

B. Apple Trees

One other way to view this problem is as follows: at any point in time, a tree is in one of 5 states: either it has existed for < 10 seconds (state 0), between 10 and 20 seconds (state 1), between 20 and 30 seconds (state 2), between 30 and 40 seconds (state 3), or it has existed between 40 and 50 seconds (state 4) (for now let’s ignore the requirement that the trees die after 45 seconds, and instead assume it is 50 seconds).

Then, every ten seconds, the number of trees in state 0 becomes 16 * (# of trees in state 0) + 9 * (# of trees in state 1) + 4 * (# trees in state 2) + (# of trees in state 3). Trees that were in state 4 do not contribute to the number of trees in state 0, because they will die during these ten seconds. Similarly, for i > 1, the number of trees in state i becomes the number of trees that were in state i - 1. This gives us a bunch of linear relationships between the number of trees in each state, which can be represented by a matrix (more formally, if f_0, …, f_4 are the number of trees in states 0 through 4, then M * (f_0 … f_4) will give us the vector containing the number of trees in each state exactly 10 seconds later). So it suffices to compute M^(floor(n/10)) and multiply it by (1 0 0 … 0). Also, to handle the “dying after 45 seconds” requirement, we simply need to not count the value of f_4 in our answer if n mod 10 >= 5 (because this means they would have all already died)

C. Matrix

Summing up all the pairwise products s_i * s_j inside a rectangle is equivalent to multiplying together the sums (s_x + … + s_y)  and (s_z + … + s_t), by the distributive property, so it remains to count how many substrings of s have sum equal to a divisor of a (unless a=0, in which case we simply count c = how many are 0, and take c * c + 2 * (nC2 - c) * c). We can count this in O(n^2) time using a prefix array, and store these counts as values c_d for d|a, and simply sum c_d * c_(a/d) over all d to get our answer.

- adam

IMPORTANT: use long long!

-Yichen Zhang

D. String Mark

The problem is equivalent to counting the number of strings <= a, and the number of strings <= b, and clearly we can do both of these using the same method. First, let c_1, …, c_26 be the number of each letter in a, and note that the total number of permutations of a is v = n! / [prod (c_i)!]. Now, we can recursively look at each prefix, and count the number of permutations whose corresponding prefix is the same, and whose next letter is strictly smaller. At some point in time, suppose that our prefix currently has d_1, …, d_26 of each letter. Then, for each possible next letter “x”, the number of permutations will be

( (n-L-1)! / ( (c_x - (d_x+1))! * [prod_(i != x) (c_i - d_i)!] ) = v * (c_x - d_x) / (n - L)

where L is the length of our current prefix, and v is the number of ways to permute our string while fixing our current prefix. We can easily compute these values by keeping track of c_i, d_i, L, and updating v at each step (v’ = v * (c_x - d_x) / (n - L), where x is the next letter in a). At any point, if some d_i exceeds c_i, we break out of the loop, since no further permutations will be possible (this can only happen when we are comparing b to a); otherwise, we add 1 at the very end to count the identity permutation. The runtime is O(26 * n), where n is the length of the string, since we check 26 possible letters at each step.

-adam

E. Creating a Connected Component

This is a subset-DP problem.  Let S be a subset of the vertices.  To set this up define the following:

First, it’s easy to see how to compute T(S) for any set S.  It’s done as follows:

What’s happening is that you have T(S’) the number of ways to set up S’, and you’re adding a new vertex v to it to create S.  The number of ways of coloring the edges between v and S’ is just the above product.  The base case of this recurrence is T(empty_set) = 1.  The time it takes to compute this is O(n 2^n).

For U(S) have the following recurrence:

You can understand this as follows.  Let v = L(S).  In any solution there must be a set of vertices S’ that is the connected component containing v.  This component cannot contain all vertices of S, otherwise S would be connected (and we’re trying to count the number of ways S can be a disconnected set).  And we’re trying all such subsets S’.  For a given choice of S’, the set S’ must be connected, and there are F(S’) ways to do this.  Now among the remaining vertices S\S’, we can pick any way at all of using those edges.  This is T(S\S’).

Now having computed U(S) we can use F(S) = T(S) - U(S) to compute F(S).

The time to compute the above recurrence is O(3^n).  There’s one unit of work for each (S,S’) pair.  And the number of these pairs is at most 3^n.  To see this, label each vertex with a number 0, 1, or 2.  The 1’s are the vertices of S’, the 1’s and 2’s are the vertices of S.  And the 0s are the vertices of neither.  (It’s < 3^n because there must be at least one vertex labeled 2.)

There’s a very nice trick that gives an extremely efficient and compact implementation of this algorithm.

Represent a set S as a number -- there’s a 1 in position i iff i is in S.  Now there’s a very elegant way to enumerate all subsets of S.  In pseudo-C code it looks like this:

void enumerate(int S) {

   int Sbar = ~S;            // the complement of S

   int S’ = 0;

   do {

          // process subset S'

          S' = S & (Sbar + S' + 1);

   } while (S' != 0);

}

The key to the whole thing is the statement S' = S & (Sbar + S' + 1). This causes S’ to run through all subsets of S in ascending order.  (More details on this technique can be found here.  They use S' = S & (S' - 1).  In that case the enumeration is in descending order.)

Also, using this representation we can just define an array F of size 2^n and then F[S] will memoize F(S).  And in fact we can compute the recurrence in order of increasing S.  I.e. S=0, 1, 2,… and by the time we’re working on F(S), all the subsets of S have already been computed.

--Danny

F. Concatenation

Ultimately, we are looking at ‘numbers as strings’.  Over the regular integers, we could encode these as strings, or instead as pairs of values and the length of the string---which would give you a measure of (kinda) how many leading zeros should be in the string.  Then, if we were to concatenate these values, say (a, la) ++ (b, lb) we should get (a * 10^lb + b, la + lb).  This generalizes nicely into the modular form, since we can continue to store these pairs of numbers (a, la) with the a being mod M, and the concatenation still works, since it functions exactly the same as if we had concatenated and then reduced.  Going a bit further for implementation convenience, we can store these ‘strings’ as (a, 10^la) so that (a, c) ++ (b, d) = (a * d + b, c * d), and both of these numbers can be freely reduced mod M.

It is simple to check that since these form a monoid with identity (0, 1), and as such we can use standard exponentiation-by-squaring to repeatedly “concatenate” one of these representations of a string very quickly.  Now, we want to construct a function f(length, high) that constructs the string corresponding to the concatenation of 000 001 002 003 … high, where each integer is considered as a string of the length in the argument.  As is somewhat standard for functions of this type, we can go digit-by-digit, and expand the number of arguments to f(length, high, digit), where digit is 10..0 corresponding to what digit we are in the process of choosing.  Then, we can just let f(length, high, digit) recursively call out to f(length, digit - 1, digit / 10) to develop the sequence that looks like 001 002 003 004 … 099 (in the case for length = 10^4, digit = 100) for which we can just add on (in value and not length) a repeated 100 (repeating using the prior trick) to get to 101 102 103 104 … 199 and similarly for 200s, 300s, and so on. Once we get to a situation where we have the cutoff in the middle of a sequence we would have added, we can just call out to f(length, high % digit, digit / 10) to generate 001 002 003 004 … 0high, for which we can just do the same thing to put the right digit in front of each of them.  There are very few possible combinations of arguments to send to f (since digit can only be one of log many things and so on), so this does not take a long time to compute.

Once we have this, we can just append together the numbers of length 1 less than n, then the ones of length 2 less than n, and so on to get the final string which is our result.

Thanks Chris.  Wassim has a conceptually simpler (at least to me) solution to this problem, and I wanted people to see it.  Here it is:

Define a 3x3 matrix M_k as follows:

If we multiply a power of M_1 by the vector (0,1,1)^T as shown above, we get the results shown above.  Note that the first element of the resulting vector is exactly the number we’re trying to compute.  The second element of the vector continues to increment by one each time.  (The third element is always 1.)  Multiplying by M_1 on the left will multiply the first element by 10 and add the second element to it.  Essentially appending an i to the number.  So for the first 9 iterations we use M_1 (one digit numbers) for the next 90 iterations we use M_2 (two digit numbers).  So M_2 to the 90th power is applied to the left of the (M_1)^9.  This process continues up until we have done M_k, where k is the number of digits in n.  At the kth level we use n to adjust the power of M_k to stop at the right point.

Of course all of the arithmetic is done modulo m.  And we use the efficient exponentiation algorithm explained in these notes.  Voilà   --Danny

G. Inversion Expectation

We can count the expected number of inversions using linearity of expectation; it is the sum over all ordered pairs (i, j) (where i != j) of the probability that min(i, j) occurs before max(i, j) in the final permutation. First we can count the number of inversions between fixed elements (i..e, those which are not zero). This is easy to do with a fenwick tree or segment tree in O(n log n).

Next, we consider the contribution to the aforementioned sum by pairs of indices which are both -1. There is a ½ probability that they will be correctly arranged, so summing this up over all pairs of values which are not present, we get a contribution to the sum of ½ * (# of negative ones choose 2).

Finally, we need to count the contribution to the sum that comes from a value which is not present, and a value whose position is already fixed. For each value x present in the array, it is straightforward to compute in O(n) time the following quantities: (1) the number of -1s that occur to the left of it in the array (call it a_x) and (2) the number of values which were not present in the input that are smaller than it (call it b_x). A particular value that is smaller than x has a probability of 1 - b_x / (# of negative ones) of occurring to the right of x (and thus contributing an inversion), and there are a_x many of them, so we need to add a_x * ( 1 - b_x / (# of negative ones)) for all x. Similarly, we also need to consider the probabilities associated with larger elements occurring to the left of x, which is (# of negative ones - a_x) * (b_x / (# of negative ones)), and add that up too. Finally we will be left with the answer.