May 26, 2018 TCO18 Beijing Regionals Round Editorials

TCO18 Beijing Regionals Round was held on 26th May 2018. Thanks to [ltdtl] and [lg5293] for the editorials.

Level Easy JumpingJackDiv1

Jack (the frog), starting at position 0 on day 0, jumps to the east once every day except on every k-th day. When Jack jumps, it moves from position x to position x+dist. You are asked where Jack will be on day n (after Jack jumps on that day, if at all).
Here, we can just simulate according to the problem statement, which would run in O(n) time.

public class JumpingJackDiv1 {
    public int getLocationOfJack(int dist, int k, int n) {
        int res = 0;
        for (int day = 1; day <= n; day++) {
            if (day % k != 0) res += dist;
        }
        return res;
    }
}

Bonus: If the limit on n was much larger (say, 10^18), the solution above may time out.
From day 1 to day n (inclusive), Jack would jump (n – floor(n/k)) times because Jack will skip jumping on day k, day 2k, day 3k, …, day floor(n/k)*k. This gives a solution that runs in O(1) time.

public class JumpingJackDiv1 {
    public int getLocationOfJack(int dist, int k, int n) {
        return dist * (n - n/k);
    }
}

Level Medium WordAndPhraseDiv1

We can use dp and process characters from left to right. The main thing we need to remember as we are moving along is whether the last character we processed is a period or not.
Thus, we have dp[i][0] = number of ways to make string of prefix i without the last character being a period, and dp[i][1] = number of ways to make string of prefix i with the last character becoming a period.
As we are processing, if we encounter a underscore character, we can either choose to turn it to a period or not (and we need to check that the beginning of the next word doesn’t begin with a digit).
This solution works in O(n) time.

public class WordAndPhraseDiv1 {
    public int mod = 1000000007;
    public int findNumberOfPhrases(String w) {
        int n = w.length();
        long[][] dp = new long[n+1][2];
        dp[0][0] = 1;
        dp[0][1] = 0;
        for (int i = 0; i < n; i++) { dp[i+1][0] = (dp[i][0] + dp[i][1]) % mod; if (i>0 && w.charAt(i) == '_' && i+1 < n && !Character.isDigit(w.charAt(i+1)))
                dp[i+1][1] = dp[i][0];
        }
        return (int)dp[n][0];
    }
}

Alternative solution:
Almost identical to the solution above, but one may have noticed that the number of ways to replace underscores by periods are the Fibonacci numbers. For instance, given ‘___’ (3 underscores), there are five ways: {___, .__, _._, __., ._.}. Using this fact, we just need to count the number of contiguous underscores, and multiply the Fibonacci numbers.
One tricky part is, however, to handle corner cases.
(1) When the input string begins with an underscore.
(2) When contiguous underscores are followed by a digit.
For case (1), if the input string begins with an underscore, it cannot be replaced by a period.
For case (2), any underscore followed by a digit cannot be replaced by a period.
Hence, in both cases, we can simply decrease the number of contiguous underscores we counted originally, and still multiply the Fibonacci numbers as explained earlier.
This approach works in O(n) time.

public class WordAndPhraseDiv1 {
	static final long MOD = 1000000007L;
	public int findNumberOfPhrases(String w) {
		int n = w.length(), i, j, val;
		long[] fib = new long[1024];
		fib[0] = 1;
		fib[1] = 2;
		for(i = 2; i < n; i++) fib[i] = (fib[i-1] + fib[i-2])%MOD;
		long ans = 1L;
		for(i = 1; i < n; i++) { // Ignore the first char of w (w[0]).
			if(w.charAt(i) != '_') continue;
			for(j=i; j < n && w.charAt(j) == '_'; j++); val = (j-i) - ((j==n || (w.charAt(j)>='0' && w.charAt(j)<='9')) ? 1 : 0);
			ans = (ans * fib[val])%MOD;
			i=j-1;
		}
		return (int) ans;
	}
}

Level Hard MaxNiceMatrixDiv1

Let’s rescale the problem from [a,b] to [0, b-a] for now. For the general input (with range [a,b]), we can simply add the value of a to every term at the end.
If there are k distinct rows, then the sum of each column is at least 0+1+…+(k-1) = k*(k-1)/2
The sum of the whole matrix is at least c * (k * (k-1) / 2)).
On the other hand, we know the sum of each row is exactly b-a, so the sum of the whole matrix is (b-a) * k.
Thus, we have c * k * (k-1) / 2 <= (b-a) * k.
Simplifying gives k <= 2 * (b-a) / c + 1.
We will explicitly construct a matrix to show that k = floor( (2*(b-a) )/c ) + 1 is always possible.
For c = 2 (two columns), this is pretty easy. Use 0, 1, …, k-1 in the first column (from row 0 to row k) and (b-a), (b-a)-1, …, (b-a) – (k-1) in the second column. The sum of each row is exactly (b-a). For instance, when c = 2 and k = 3:
0 (b-a)
1 (b-a)-1
2 (b-a)-2
Every column has distinct numbers, the numbers range between 0 and b-a, inclusive, and each row’s numbers sum up to exactly b-a.
When c is even, this idea can be generalized fairly easily. For the first c-1 columns, simply use the numbers from 0 to k-1 in increasing order for columns 0, 2, 4, …, c-2, and the numbers from k-1 to 0 in decreasing order for columns 1, 3, 5, …, c-3.
For instance, if c = 6 and k = 4, we would have:
0 3 0 3 0 ?
1 2 1 2 1 ?
2 1 2 1 2 ?
3 0 3 0 3 ?
It is easy to see that the sum of the first (c-2) numbers in each row is the same, and because of the second-to-the-last column, the sum of the first (c-1) numbers in each row is an arithmetic sequence. In this example, it is 6, 7, 8, 9. The last column is uniquely determined because each row’s sum must be equal to b-a (recall we ‘scaled’ the numbers from [a, b] to [0, b-a]). You can also easily show that the numbers found this way never exceeds b-a.
When c is odd, things get a bit trickier. We’ll still use the same idea as earlier, but this time we will need to pre-fill the first c-2 columns. For instance, if c = 7 and k = 4, we would have:
0 3 0 3 0 ? ?
1 2 1 2 1 ? ?
2 1 2 1 2 ? ?
3 0 3 0 3 ? ?
Again, the sum of the first c-2 numbers in each row forms an arithmetic sequence (the common difference is +1). The trick is to complement this sequence by another arithmetic sequence (whose common difference is -2). More specifically, starting from k-2 at row 0, we would use k-2, k-4, k-6, …, until this hits 1 or 0 depending on the value of k. Then, at the next row, we start from k-1, using k-1, k-3, and so on.
Using the same example as above (c = 7 and k = 4) we then have:
0 3 0 3 0 2 ?
1 2 1 2 1 0 ?
2 1 2 1 2 3 ? (*)
3 0 3 0 3 1 ?
Notice that now the sums of the first c-1 numbers in four rows are distinct, and therefore the last column (which is uniquely determined from the first c-1 columns) will not have duplicates.
For concreteness, it remains to show that the above solution works for all input values. It’s rather easy to prove this claim when c is even, so let us give a concise version for the case when c is odd.
Each cell must have a value between 0 and b-a, inclusive. Except for the last column, this is trivially true because of the way we choose the numbers. Numbers in the last column never exceed b-a (because we subtract the sum of the other c-1 non-negative numbers from (b-a)). To show that these numbers are non-negative as well, consider row q (where q= floor(k/2)) where the sum of the first c-1 numbers is the largest. In the example above, it’s marke with (*).
This row contains the numbers {q, k-q, q, k-q, …, k-q, q, k-1}. Summing these up yields (k * (c-3)/2 + floor(k/2) + k-1); recall that k = floor(2*(b-a)/c) + 1. With a bit of work, you can show that the sum is no greater than b-a. This bound is sharp; in the above example, for instance, pick b = 11 and a= 0 (which gives us k = floor(2*(b-a)/7) + 1 = 4). Row q (where q = floor(k/2) = 2), we have the sum (2+1+2+1+2+3 = 11) that is equal to b-a.
Lastly, we choose distinct numbers within each column except for the last column; for the last column we simply subtract the sum of the other c-1 values from (b-a). By showing that the sums are distinct, we can prove that the matrix we find is indeed a nice matrix.
Here is a reference solution, using the idea explained above.
This solution runs in linear time (in the size of the output matrix, of course), O((n/c)*c) = O(n) where n = b-a.

public class MaxNiceMatrixDiv1 {
	public int[] getMaxMatrix(int a, int b, int c) {
		int n = b-a, m = (n*2)/c + 1, x = m-2, idx = 0;
		int[] ret = new int[m*c];
		for(int i = 0; i < m; i++) {
			int sum = 0;
			for(int j = 0; j < c-2; j++) { // alternate [0,m-1] and [m-1,0].
				if(j%2 == 0) ret[idx++] = i;
				else ret[idx++] = m-1-i;
			}
			if(c%2 == 0) ret[idx++] = i;
			sum = (m-1)*(c/2 - 1) + i;
			if(c%2 == 1) { // when c is odd.
				ret[idx++] = x;
				ret[idx++] = n - sum - x;
				x-=2;
				if(x < 0) x = m-1;
			} else { // when c is even.
				ret[idx++] = n - sum;
			}
		}
		for(int i = 0; i < idx; i++) ret[i] = ret[i] + a;
		return ret;
	}
}