PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
Let c4[i] be the number of digits 4 among all digits in S[1, i] and c7[i] be the number of digits 7 among all digits in S[1, i]. Formally, you need to find the number of such pairs (L; R) that there exists at least one i (L <= i+1 <= R) such that c4[i]-c4[L-1] = c7[R]-c7[i] (here i+1 plays the role of X from the definition in the problem statement). Rewrite this equation as ñ4[i]+c7[i]-c4[L-1] = c7 [R]. Now you can notice, that actually c4[i]+c7[i] = i (recall that the numeration of characters starts from 1). So now i-c4[L-1] should be equal to c7[R]. Rewrite it as c7[R]+c4[L-1] = i. Iterate all L from 1 to N, now you need to find for fixed L the number of good R. Since L <= i+1 <= R you need to find the number of such R that L <= c7[R]+c4[L-1]+1 <= R. Note, that c7[R]+c4[L- 1]+1 is always greater than or equal to L, so restriction is just c7[R]+c4[L-1]+1 <= R. Rewrite it as
c4[L-1]+1 <= R-c7[R]. (1)
So the problem now is to find the number of such R (R >= L) that R-c7[R] is greater than or equal to c4[L-1]+1. This can be done using BIT (Binary Index Tree) (use Google to find information about that). Consider the array C, C[i] is the current number of such R that R-c7[R] = i. It will be updated during the pass by all L. Namely, we start from L = N and will decrease L by 1 at each step while L >= 1. At each step we at first increase value C[L-C7[L]] by 1. So array C will contain information about all R >= L and hence the number of good R for the current L can be simply found as the sum of C[i] for c4[L-1]+1 <= i <= N. BIT allows to do both operations (change and query) in O(log N). So we obtain the O(N log N) solution.
But such solution will be an overrun for this problem. There exists much simpler solution. Just notice, that the only strings that are not balanced are the strings that do not have digits 4, that is, the strings of the form 777…777 of any positive length. Next we present the proof of this fact. Even two proofs :). Choose the one you are more comfortable with.
Proof of the author. Let pair of integers (a, b) for some position x is the balance pair for x, i. e. a is equal to the number of digits 4 in S[1, x-1] and b is the number of digits 7 in S[x, N]. We need to find such x that a-b = 0 for that position. For x = 1 pair (a, b) is (0, c7), and for x = N this pair is (c4-1, 0) if the last digit is 4 and (c4, 1) if the last digit is 7, where c4 and c7 is the total number of corresponding digits in S. When you are iterating x from left to right, pair (a, b) turns either to (a+1, b) or to (a, b-1). During all N iterations of x, (0, c7) will be turned to (c4-1, 0) (or (c4, 1)). Since a increases by 0 or 1 and b decreases by 0 or 1 at each step, the case a = b will happen for some x, in general. But the only string that sucks is the string of the form mentioned above. In that case pair (0, c7) will be turned to pair (0, 1) by only decreasing c7. Hence there will be no x such that a = b for that x.
Proof of the tester. Let S be some lucky string of the length N. Denote by L4(x) the number of digits 4 in the substring S[1, x-1] and by R7(x) the number of digits 7 in the substring S[x, N]. Consider the difference D(x) = L4(x) - R7(x) as a function of x. According to the definition, the string S is balanced if and only if D(x) = 0 for some x with 1 <= x <= N. Try to analyze the behavior of this function. Note that, D(1) = -n7 <= 0 where n7 is the total number of digits 7 in the string S. Further note, that D(N) = n4’ if S[N] = 4 and D(N) = n4’ - 1 if S[N] = 7. Here n4’ is the number of digits strong text 4 in the substring S[1, N-1] (so we ignore last character of S). Note that D(N) < 0 if and only if n4’ = 0 and S[N] = 7, that is, if S does not have digits 4. We will use this important observation later. Now we analyze how D(x) changes when x is increasing by 1. If S[x] = 4 then L4(x+1) = L4(x) + 1 and R7(x+1) = R7(x). So in this case D(x+1) = D(x) + 1. Similarly if S[x] = 7 we see that D(x+1) = D(x) + 1. Thus, D(x+1) = D(x) + 1 for all x. Consider the case when D(N) >= 0, that is, the case when S contains at least one digit 4. Then, conditions D(1) <= 0, D(x+1) = D(x) + 1 for 1 <= x <= N-1 and D(N) >= 0 implies that D(x) = 0 for some x. Thus, the string that has at least one digit 4 is always balanced. On the other hand, it is easy to see that if S is composed of exactly N digits 7 then D(x) = x-1-N < 0 for 1 <= x <= N. So such string is not balanced. This finishes the proof.
This means that you just need to find the number of non-balanced substrings, and it is the number of such (L; R), 1 <= L <= R <= N that s[x] = 7 for L <= x <= R. And this is the simple problem which is the homework for you 
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.