PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
This problem can be solved using dynamic programming approach.
Let DP(V, A, E) be the number of binary strings containing A ‘A’ characters and E ‘E’ characters, and have hash value V.
The base cases are
- DP(0, 0, 0) = 1, DP( * , 0 , 0 ) = 0 (* other than 0)
- DP(1, 1, 0) = 1, DP( * , 1 , 0 ) = 0 (* other than 1)
- DP(0, 0, 1) = 1, DP( * , 0 , 1 ) = 0 (* other than 0)
Then, we must define the recurrence formula. Let N = A + E. After the split, let the first half (N/2) of the string contains A1 'A’s, E1 'E’s, and has hash value V1. Let the second half (N - N/2) of the string contains A2 'A’s, E2 'E’s, and has hash value V2. Because they are independent, we can simply take the product.
So, the recurrence becomes
DP(V, A, E) = sum { DP(V1, A1, E1) * DP(V2, A2, E2) }
for all
A1 + A2 = A
E1 + E2 = E
A1 + E1 = N/2
A2 + E2 = N - N/2
max(V1, V2) = V - A
So, the idea is to try all possible values of A1, A2, E1, E2, V1, V2, then take the sum of the products. First, we try all possible values of A1. We automatically get A2, E1, and E2 by exploiting the above equation. After that, try all possible values of V1 and V2 whose max value is V - A.
This is our current solution in pseudocode.
for A1 := 0 to A
A2 := A - A1;
E1 := N/2 - A2;
E2 := E - E1;
for V1 := 0 to V - A
for V2 := 0 to V - A
if max(V1, V2) = V - A
DP(V, A, E) += DP(V1, A1, E1) * DP(V2, A2, E2);
The above algorithm is not very efficient, since there are only O(V - A) pairs of (V1, V2) that satisfy max(V1, V2) = V - A, i.e. when one of them is V - A. So, we can improve that into
for A1 := 0 to A
A2 := A - A1
E1 := N/2 - A2
E2 := E - E1
// both are V - A
V1 := V - A;
V2 := V - A;
DP(V, A, E) += DP(V1, A1, E1) * DP(V2, A2, E2);
// V1 is V - A, V2 < V - A
V1 := V - A;
for V2 := 0 to V - A - 1
DP(V, A, E) += DP(V1, A1, E1) * DP(V2, A2, E2);
// V2 is V - A, V1 < V - A
V2 := V - A;
for V1 := 0 to V - A - 1
DP(V, A, E) += DP(V1, A1, E1) * DP(V2, A2, E2);
The algorithm can still be improved further, by replacing the two for’s by partial sum, like this:
for A1 := 0 to A
A2 := A - A1
E1 := N/2 - A2
E2 := E - E1
// both are V - A
DP(V, A, E) += DP(V-A, A1, E1) * DP(V-A, A2, E2);
// V1 is V - A, V2 < V - A
DP(V, A, E) += DP(V-A, A1, E1) * SUM(V-A-1, A2, E2);
// V2 is V - A, V1 < V - A
DP(V, A, E) += SUM(V-A-1, A1, E1) * DP(V-A, A2, E2);
where SUM(V, A, E) = sum {DP(V, A, E)} for all v := 0 to V.
The complexity then becomes O(A^2 E V). If you have completed the solution, you can easily check that the maximum value of V is 152.
TESTER’S SOLUTION
Can be found here.