LUCKY9 - Editorial

editorial
, , , ,
1

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|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 :slight_smile:

The answer thus would be

NCN4 - N-2CN4-1

SETTERS SOLUTION

Can be found here.

TESTERS SOLUTION

Can be found here.

1 Like
2

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
3

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

4

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.

1 Like
5

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.

5 Likes
6

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.

7

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

8

can you please explain how you found nCr??

9

You can find perfect answer from @gamabunta here

10

@martin :thank you