 MEDIUM

# PREREQUISITES

Simple Math, Binomial Coefficient

# PROBLEM

You are given a string of length N that contains only 4s and 7s. Find the number of balanced strings that can be reached by any permutation of S. A balanced string is a string for which an index x (1-based) exists such that

number of 4s in substring [1, x) = number of 7s in substring (x, N]

Note: We can trivially simplify “any number of swaps on pairs of consecutive digits” as given in the problem statement to “any permutation”.

# QUICK EXPLANATION

The answer can be found in O(|s|2) time for each test case using Dynamic Programming. But there is a much more clever solution! After you precalculate all the binomial coefficients nCr for 0 ≤ r ≤ n ≤ 5000 you can calculate the answer in O(1) time for each test case!

Alternately, the answer for each test case can be found in O(|s|) time.

All the details of the proof below are taken from the notes of Hiroto Sekido that he gave during testing this problem.

# EXPLANATION

Let S be the string which is given.

• Let N4 be the number of 4s in S
• Let N7 be the number of 7s in S

Theorem: S is unbalanced iff S is of the form A + “47” + B, AND |A| = N7-1, AND |B| = N4-1.

Proof

Let us show the S of the form as described in the theorem, is indeed unbalanced.

• Let z be the number of 4s in A
• Number of 7s in A = N7-1 - z
• Since |A| = N7-1
• Number of 7s in B = z
• Since Number of 7s in B = N7 - (number of 7s in A) - 1 = N7 - N7 + 1 + z - 1 = z
• Number of 4s in B = N4-1 - z
• Since |B| = N4-1

Now, consier x = N7

• Number of 4s in [1, x) = z
• Number of 7s in (x, N] = z+1

Hence, string is not balanced at x = N7

Now, consider x = N7+1

• Number of 4s in [1, x) = z+1
• Number of 7s in (x, 1] = z

Hence, string is not balanced at x = N7+1

The following insights are trivially observable

• If we increase x, the number of 4s on the left can never decrease.
• Similarly, if we increase x, the number of 7s on the right can never increase.

Corollarly,

• If we decrease x, the number of 4s on the left can never increase.
• Similarly, if we decrease x, the number of 7s on the right can never decrease.

Thus, we make the following conclusions

• In S, for any x < N7, number of 4s in [1, x) < number of 7s in (x, N]
• Since, number of 4s in [1, N7) < number of 7s in (N7, N]
• Similarly, for any x > N7+1, number of 4s in [1, x) > number of 7s in (x, N]
• Since, number of 4s in [1, N7+1) > number of 7s in (N7+1, N]

Hence, S must be an unbalanced string.

But to prove the if-and-only-if part of our Theorem, we must also prove that any other form of S is balanced except the one that satisfies the description in the theorem.

There are three more cases that should be proven as “balanced” to call the Theorem true.

Case 1: S = A + “44” + B, |A| = N7-1, |B| = N4-1

• Let z be the number of 4s in A
• Number of 7s in A = N7-1 - z
• Number of 7s in B = N7 - (number of 7s in A) = N7 - (N7-1 - z) = z + 1

Now, at x = N7+1

• Number of 4s in [1, x) = z+1
• Number of 7s in (x, N] = z+1

Hence S is balanced.

Case 2: S = A + “77” + B, |A| = N7-1, |B| = N4-1

• Let z be the number of 4s in A
• Number of 7s in A = N7-1 - z - 2
• Number of 7s in B = N7 - (number of 7s in A) - 2 = N7 - (N7-1 - z) - 2 = z - 1

Now, at x = N7

• Number of 4s in [1, x) = z
• Number of 7s in (x, N] = z

Hence S is balanced.

Case 3: S = A + “74” + B, |A| = N7-1, |B| = N4-1

• Let z be the number of 4s in A
• Number of 7s in A = N7-1 - z
• Number of 7s in B = N7 - (number of 7s in A) - 1 = N7 - (N7-1 - z) - 1 = z

Now, at x = N7

• Number of 4s in [1, x) = z
• Number of 7s in (x, N] = z

Also, at x = N7+1

• Number of 4s in [1, x) = z
• Number of 7s in (x, N] = z

Hence S is balanced. In fact, we have two evidences this time.

## CONCLUSION

Thus, we have seen that for any string S of the type A + “xx” + B, where |A| = N7-1, |B| = N4-1, S will be unbalanced iff “xx” = “47”.

This is a very strong condition. Every string will have a unique partition into an A and B, and its balanced-ness simply depends upon the two characters in between NCN4 - N-2CN4-1

# SETTERS SOLUTION

Can be found here.

# TESTERS SOLUTION

Can be found here.

2 Likes

Alternatively one can precompute all factorials and inverse factorials in O(|s|) time before reading test cases and then answer each query in O(1) time. See my solution for details.

Also I use another formula C(n-1,n4) + C(n-1,n7) - C(n-2,n4-1) which follows from inclusion-exclusion principle and slightly different reasoning that describe in the editorial.

2 Likes

but array might be out of bounds

That’s quite a long proof.

Suppose there are k sevens, and we want to count unbalanced numbers.

We can place a 4 at position x <=>
number of 4s before x != number of 7s after x <=>
number of 4s before x != k - number of 7s before x <=>
number of 4s before x + number of 7s before x != k <=>
x != k

We can place a 7 at position x <=>
number of 4s before x != number of 7s after x <=>
number of 4s before x != k - 1 - number of 7s before x <=>
number of 4s before x + number of 7s before x != k-1 <=>
x != k-1

So if k = 0, there are no unbalanced numbers; if k>0 we must place a 4 at position k-1, a 7 at position k, and the rest can be anything.

6 Likes

The memory limits on the cube judge are 1536 MB.

an int array would only consume 100 MBs.

But this array cannot be declared on the stack (that is, local to a function in C++). It should be declared globally / on heap. Another option is to declare it as a static, since runtime allocates them in a separate area.

The stack size of execution is typically much much smaller.

1 Like

I also used the same approach as you. Sum all balanced strings for balance b=0 to b = min(n4, n7) - which was counted twice because of “74” as substring.

@anton_lunyov : Can you please explain your approach in a bit more detail.
Thanks

can you please explain how you found nCr??

You can find perfect answer from @gamabunta here

@martin :thank you