LUCKY1 - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

It is well-known that the sum of any range Sum[l; r] can be rewritten in form Sum[0; r]-Sum[0; l-1]. Let Sum4[i] is the total number of digits 4 in all numbers from 1 to i, inclusive, and Sum7[i] is the total number of digits 7 in all numbers from 1 to i, inclusive. We need to find the number of such pairs (l; r) that 1 <= l <= r <= N and Sum4[r]-Sum4[l-1] = Sum7[r]-Sum7[l-1]. Rewrite it in this way: Sum4[l-1]-Sum7[l-1] = Sum4[r]-Sum7[r]. We can iterate through all r from 1 to N, and for each r we need to know the number of correct l indexes. Let S = Sum4[r]-Sum7[r] for some current r. We need to find the number of such l (l <= r) that Sum4[l-1]-Sum7[l-1] = S. Since we are iterating r through all numbers from 1 to N, we can handle some array C[i], where C[i] is current number of such l that Sum4[l]-Sum7[l] = i. In each iteration of r, we add to the result number C[Sum4 [r]-Sum7[r]], and then increment C[Sum4[r]-Sum7[r]] by 1. In general this array can has negative indexes so if your programming language does not support arbitrary indexation you should make some tricks. But it can be proven that Sum4[r]-Sum7[r] is always non-negative so you can use usual array for this. Also it is useful to handle arrays Cnt4[i] and Cnt7[i] where Cnt4[i] is the number of fours of decimal representation of i and similar definition is for Cnt7[i]. Then Cnt4[i] can be calculated in O(1) time from Cnt4[i/10]. Thus the total complexity of such algorithm is O(N) for one query. But, you can precompute results for all numbers from 1 to 105 and store them in some array. That gives O(1) complexity for each query.

And here is some example: test case for N = 10.

i Sum4[i] Sum7[i] Sum4[i]-Sum7[i] C[-1] C[0] C[1] Result
0 0 0 0 0 1 0 0
1 0 0 0 0 2 0 1
2 0 0 0 0 3 0 3
3 0 0 0 0 4 0 6
4 1 0 1 0 4 1 6
5 1 0 1 0 4 2 7
6 1 0 1 0 4 3 9
7 1 1 0 0 5 3 13
8 1 1 0 0 6 3 18
9 1 1 0 0 7 3 24
10 1 1 0 0 8 3 31

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

5 Likes

Nice question :slight_smile:

Having problem???

NO PROBLEM!!!

have a look…

http://discuss.codechef.com/questions/46405/long-challenge-feb12