December 2011 Cook-off Problem Editorials

Problem Setter for the contest was Hiroto Sekido.
Problem Tester for the contest was Jingbo Shang.

----------------------------------------------------------

CIEL8STR : Ciel and New Menu

Let S[a..b] denote the substring from a-th character to b-th character of S.

One of the solutions for this problem is to use the fact that 1000 is multiple of 8. Let consider the number of the integers S[i..digit] mod 8 = 0 for all i. This number can be calculated as following:

• count := 0.
• If S[digit] mod 8 = 0 and S[digit] ≠ 0, count := count + 1.
• If S[digit-1..digit] mod 8 = 0 and S[digit-1] ≠ 0, count := count + 1.
• If S[digit-2..digit] mod 8 = 0, count := count + the number of non-zero digits in S[1..digit-2].

Therefore, at first, calculate the number of non-zero digits in S[1..i], for all i, then this problem can be solved with O(|S|) time.

This problem also can be solved by using DP (Dynamic Programming). Let dp[digit][num] = the number of the integers S[i..digit] mod 8 = num for all i. Then dp[digit+1][aft] = (sum of dp[digit][bef]) + a, where (10 * aft + S[digit+1]) mod 8 = bef, and if aft = S[digit+1] ≠ 0, a = 1, otherwise a=0. Note that this algorithm will work for finding the number of the numbers multiple of 7, for example.

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

CIELAB : Ciel and A-B Problem

This is the easiest problem in the set. This problem can be solved various methods. For instance, if A - B mod 10 = 9, print A - B - 1, otherwise print A - B + 1. Be careful not to print 0 if A - B = 1. Your answer must be a positive integer.

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

CIELBTL : Ciel and Battle Arena

This problem can be solved by using DP (Dynamic Programming). Basically, the relationship dp[V_A][V_B][M_A] = max(dp[ceil(V_A/2)][ceil(V_B/2)][M_A-1], sum of dp[V_A-i][V_B-j][M_A] / ((S_A+1)*(S_B+1)), for 0 ≤ i ≤ S_A, 0 ≤ j ≤ S_B) is hold, where dp[V_A][V_B][M_A] is the answer for the input V_A, S_A, V_B, S_B, M_A. However there are some troubles.

First, dp[V_A][V_B][M_A] is appeared both of the left hand side and the right hand side. So, dp[V_A][V_B][M_A] cannot be calculated directly by using above expression. But this is not a hard problem. Transpose that term, then we obtain dp[V_A][V_B][M_A] = max(dp[ceil(V_A/2)][ceil(V_B/2)][M_A-1], sum of dp[V_A-i][V_B-j][M_A] / ((S_A+1)*(S_B+1)-1), for 0 ≤ i ≤ S_A, 0 ≤ j ≤ S_B, i+j > 0).

Second, dp[a][b][c] is unknown for a ≤ 0, b ≤ 0. We can use binary search for solving this issue. Let the correct answer be P. If we set dp[a][b][c] = X for a ≤ 0, b ≤ 0, then X ≤ dp[V_A][V_B][M_A] ≤ P or P ≤ dp[V_A][V_B][M_A] ≤ X is hold. Therefore, we can calculate the correct answer by using binary search. Note that, if V_A ≤ 0 and V_B > 0, dp[V_A][V_B][M_A] = 0, and if V_A > 0 and V_B ≤ 1, dp[V_A][V_B][M_A] = 1.

Third, if dp[a][b][c] is calculated naively with O(S_A*S_B) time, we will get TimeLimitExceeded. To avoid this, a cumulative sum can be used. Let sm[a][b][c] be sum of dp[x][y][c] for M ≤ x ≤ a, M ≤ y ≤ b, where M is a small integer such as -101. Then, sum of dp[a-i][b-j][c] for 0 ≤ i ≤ S_A, 0 ≤ j ≤ S_B = sm[a][b][c] - sm[a-S_A-1][b][c] - sm[a][b-S_B-1][c] + sm[a-S_A-1][b-S_B-1][c], and sm[a][b][c] = sm[a-1][b][c] + sm[a][b-1][c] - sm[a-1][b-1][c] + dp[a][b][c]. By using this relationship, dp[a][b][c] can be calculated with O(1).

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

CIELQUIZ : Ciel and Quiz Game

The model solution for this problem is very simple, and this problem can be solved for larger N. However I have set N ≤ 36 for keeping away from guessing the simple solution from the constraint. Naive bruteforce algorithms with O(N!/K!/(N-K)!) or O(N*2^N/2) will get TimeLimitExceeded. I would like to say that the tester can solve this problem by an optimized bruteforce solution.

Let's start the explanation of the model solution. We don't have to check all combinations. At first, sort P_i, and consider the case where P₁ ≤ P₂ ≤ ... ≤ P_N. There is at least one answer that first i problems and last K-i problems are chosen, that is, problem 1, 2, ..., i, and problem N-K+i+1, N-K+i+2, ..., N are chosen. This method is O(N² + K³) time implemented naively as the setter's solution.

A short proof is the following. Let one of the optimal sets be the problem A₁, A₂, ..., A_K, and let the set don't contain problem B and C, where B < A_K < C. For the set of K-1 problems A₁, A₂, ..., A_K-1, let x be the probability that all problems are solved correctly, and y be the probability that K-2 problems solved correctly. Then, the probability of solving K-1 problems correctly for the set of K problems A₁, A₂, ..., A_K-1, Z is (1 - P_Z/100) * x + P_Z/100 * y. Because this is the linear function of P_Z, the set of problems A₁, A₂, ..., A_K-1, B and A₁, A₂, ..., A_K-1, C are also optimal sets.

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

CIELWALK : Ciel and Random Walk

Let the matrix P satisfy P_i,j = the probability that Ciel is in j-th node at time 1 if Ciel is in i-th node at time 0. Then, (P^t)_i,j is equal to the probability that Ciel is in j-th node at time t if Ciel is in i-th node at time 0.

At first, we need to compress the graph as the below figure. The compressed graph contains only the nodes having beautiful flowers, start node, and end node. And the weight of edges Q_i,j is the probability that Ciel goes from i-th node to j-th node, without visiting other nodes having beautiful flowers. Q_i,j can be calculated as (P^∞)_i,j, where P_i,j is the weight of the lower left of the below figure. Then we obtain the answers by calculating Q^∞ corresponding the right graph of the below graph.

We may calculate P^M instead of P^∞, where M is an enough large integer. The expectation of the number of Ciel's move can be around 30! (2¹⁰⁸ < 30! < 2¹⁰⁹) for some graphs. (Think the graph that the edge from node i to node j exists iff i+1 ≥ j.) Therefore, M must be greater than 30!. For instance, 2¹¹⁰ is enough.

One important thing for calculating P^M is thinking about a numerical error. The sums of P_i,k for all k should be 1. But in the computer, this may be slight different from 1. Therefore, the elements of P^M will be 0 or inf. To avoid this trouble, a normalization is needed, that is, the sums of probabilities should be keep 1.

The total complexity for this algorithm is O(N⁴*log N!).

Note that P^∞ may be calculated by solving linear equations with Gaussian elimination. However, because Gaussian elimination is not good algorithm in terms of a numerical error, this method may get WrongAnswer. If a bignum arithmetic is used, this method also can be accepted.

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------