January 25, 2021 SRM 798 Editorials

Thanks to misof for writing the editorial.

SyllableCountEstimator

We just need to carefully implement the rules given in the problem statement. Probably the hardest part to get right is counting the number of occurrences of a specific substring. It pays off to use library functions for everything you can. Sample implementation follows.

int countOccurrences(String haystack, String needle) {
    	int count = 0, fromIndex = 0;
    	while (true) {
        		int where = haystack.indexOf(needle, fromIndex);
        		if (where == -1) return count;
        		++count;
        		fromIndex = where+1;
    	}
}

boolean isConsonant(char c) {
    	return "aeiou".indexOf(c) == -1;
}

public int estimate(String W) {
    	int answer = 0;
    	// rule 1
    	for (String vowel : new String[] {"a", "e", "i", "o", "u"})
answer += countOccurrences(W, vowel);
    	// rule 2
    	for (String group : new String[] {"au", "oa", "oo", "iou"})
answer -= countOccurrences(W, group);
    	// rule 3
    	int N = W.length();
    	if (W.charAt(N-1) == 'e') --answer;
    	// rule 4
    	if (N >= 3 && W.charAt(N-1) == 'e' && W.charAt(N-2) == 'l'
    && isConsonant(W.charAt(N-3))) ++answer;
    	// rule 5
    	if (answer < 1) answer = 1;
    	return answer;
}

LogiciansAndBeer

If all people want beer, the conversation that happens is the one in the joke: “??????+”

If the first K people want beer and person K+1 does not, the first K people will answer “?” and then the next person will answer “-”. From that point on, everyone else must also answer “-” because it’s already clear that somebody (more specifically, person K+1) does not want a beer.

Thus, the only valid inputs are “all ? and then one +” and “a non-negative number of ? followed by a positive number of -”. If the input is from the first category, the answer is N, if the input is from the second category, the answer is the number of “?”, and for each other input the answer is -1.

SuperSubset

Some sets of indices have the property that the sum of corresponding elements of A is exactly Y. Let’s call these good sets.

We are asked to compute the following sum:

let I = {0, 1, ..., N-1}
let answer = 0
for each subset A of I:
	answer += weight(A)

We can rewrite this definition as follows:

let I = {0, 1, ..., N-1}
let answer = 0
for each subset A of I:
	for each subset B of A:
if B is good:
answer += 1

And now we can use the oldest trick in the book, at least in combinatorics: change the order of summation.

let I = {0, 1, ..., N-1}
let answer = 0
for each subset B of I:
	for each superset A of B:
if B is good:
answer += 1

Which can now be simplified to

let I = {0, 1, ..., N-1}
let answer = 0
for each subset B of I:
     if B is good:
          answer += pow( 2, N-|B| )

because if B has |B| elements, it has exactly 2^(N-|B|) distinct supersets.

Let’s introduce a new term: we’ll call the value 2^(number of elements that are not in B) the power of B. We just argued that the answer we seek is also the sum of power(B) over all good sets B.

We can count this using dynamic programming. Suppose we already processed some prefix of the input sequence and for each sum S we have dp[S] = the sum of power(B) over all B with sum S. Now we are going to process the next element with value x. If we have a set with sum=S, we have two options: we either add x to it or we don’t. If we choose the first option, the power of the set remains the same and its sum becomes S+x. If we choose the second option, the sum remains S but the power doubles. Thus, we can process all these sets at once by doing newdp[S+x] += dp[S] and newdp[S] += 2*dp[S].

ExpectedValue

Each permutation can be broken into disjoint cycles.

If we swap two elements that are on the same cycle, the cycle breaks into two. If we swap two elements that are on different cycles, the cycles merge together. (Draw a picture if you don’t see why the first is true. The second is true because it undoes the first.)

The sorted permutation has N cycles. Each swap increases the number of cycles by at most 1. Thus, if we have a permutation that currently has C cycles, we need at least N-C swaps. Conversely, each cycle of length L can be resolved in L-1 swaps and this produces a solution with exactly N-C swaps total. Thus, the value f(P) is simply N minus the number of cycles in P. And, by linearity of expectation, the expected value of f(P) is N minus the expected number of cycles in P.

The total number of derangements is a well-known combinatorial problem, look it up on Wikipedia or OEIS for the formula. All we need is the total number of cycles in all derangements and we are done.

We will count the cycles of each length separately.

Suppose we are interested in cycles of length L. How many of them (over all derangements) contain a specific element x? We have:

• binomial( N-1, L-1) ways to select the other L-1 elements on the cycle
• factorial( L-1 ) ways to choose the order in which the cycle visits them after visiting x
• subfactorial( N-L ) ways to produce a derangement of all other elements

and therefore the count C of such cycles is the product of the above three values.

That was for one specific element x, but clearly the answer does not depend on the value x. Thus, N*C is the total count over all elements. This value counts each cycle L times – once for each its element. Hence, all derangements of N elements contain a total of NC/L cycles of length L.

The final answer is then N – sum( NC/L for L=2..N ) / subfactorial(N).

RaceCircuit

Conceptually this problem isn’t too complicated but its implementation can be ugly and it pays off to think about a good way of representing a state before starting to implement it.

The main idea is, of course, dynamic programming. More precisely, we will process the input one cell at a time, so the states of our algorithm will correspond to the so-called “broken profiles”.

Suppose we already drew some parts of the circuit onto the cells we already processed and we paid for the parts that are completely in the processed part. The circuit now consists of multiple disjoint parts. Each of those parts crosses the boundary between the processed and unprocessed part of the grid in exactly two places. The exact state of our construction is information about this boundary.

For example, if we have C = 10 columns and we already processed 47 cells, the current boundary between unprocessed and processed cells consists of C+1 = 11 sides of squares. In order to represent the current state, we need to write down which of these are crossed by parts of the circuit and which pairs of ends correspond. Thus, one possible state can be A_BB___C_CA.

The key observation is that everything is planar and the race circuit never crosses itself, which means that the different pieces of the circuit can be thought of as a well-parenthesized expression. The above state can therefore equivalently be represented as (_()___(_)_). We can look at this new expression and deduce which endpoints correspond to each other.

This gives us an upper bound of 3^(C+1) states for a specific broken profile, with the actual number being even smaller. This is clearly small enough, so we can go ahead and implement it. We’ll process the cells one at a time and we’ll maintain a map. In the map we’ll store the smallest possible cost for each reachable state.  Whenever we are adding a new cell to an existing state, we have at most two options how to draw the circuit in the new cell. Thus, a loose upper bound of the time complexity of this solution is O(R*C*3^C).