LUCKY9 - Editorial

[gamabunta]

PROBLEM LINK

Practice
Contest

DIFFICULTY

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|²) time for each test case using Dynamic Programming. But there is a much more clever solution! After you precalculate all the binomial coefficients ⁿC_r 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

The answer thus would be

^NC_N4 - ^N-2C_N4-1

SETTERS SOLUTION

Can be found here.

TESTERS SOLUTION

Can be found here.

[anton_lunyov]

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.

[pankajb23]

but array[5000][5000] might be out of bounds

[triplem]

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.

[gamabunta]

The memory limits on the cube judge are 1536 MB.

an int[5000][5000] 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.

[alphanso]

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.

[sourabh912]

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

[abhinav1234]

can you please explain how you found nCr??

[betlista]

You can find perfect answer from @gamabunta here

[abhinav1234]

@martin :thank you