AEHASH - Editorial

PROBLEM LINKS

Practice
Contest

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.

1 Like

Can anyone explain this

DP(V, A, E) = sum { DP(V1, A1, E1) * DP(V2, A2, E2) }

How this formula solves the problem ?

Can anyone please explain the logic behind what is written here ?? It seems like this tutorial is for those who already solved it.

Someone please explain… please…

1 Like
//