PROBLEM LINKDIFFICULTYMEDIUM PREREQUISITESMaths, Binary Search PROBLEMYou are given a list of N numbers, say A. Find the number of ranges (L, R) such that
QUICK EXPLANATIONThere are several tricks that we will use along the way to solve this problem. Let, A4[i] be the number of 4s in A[i]. In terms of sequences C4[] and C7[] the problem can be stated as follows: find all pairs (L; R) for which:
The main idea is to fix differences C4[R]  C4[L] and C7[R]  C4[L]. We will use the following three methods to solve the problem. Note that all these methods are passed sorted arrays and can hence optimize the time complexity of the operations that they must perform.
The answer can then be calculated using these methods. We must use these methods for inclusion and exclusion of several pairs (L, R). For a summary on how to use these methods and how they can be implemented, refer to the commented solution of the Tester. The method "smart" in the code refers to using count1, count2 and count3. The code has neat and clean definitions of the respective methods as well, but we will also be looking at them in detail, below. EXPLANATIONcount1(A,v)
count2(A,a,B,b)
count3(A,B) This specifically handles the case when C7 = 1 and we want to find all the pairs such that C4[R]C4[L] ≤ R  L.
For a given range of R1 and R2, we still have to find R such that C4[R]C4[L] ≤ R  L. Everytime we make a selection of R1 and R2 (which is mutually exclusive from the previous selection), we can store the values C4[r]r for each r between R1 and R2. This trick comes from the following rearrangement of our condition
Now, once we store all the values of C4[r]  r, and sort them, looking up the maxR for each L < R1 can be done via binary searching the matrix of C4[r]r values. Complexity
SETTERS SOLUTIONCan be found here. TESTERS SOLUTIONCan be found here.
This question is marked "community wiki".
asked 19 Nov '12, 08:36

please give some test case for breaking this. answered 24 Dec '12, 23:56
i modified my code thinking that pow should be long long. but it is also giving wrong answer. another code that gave time limit exceeded and ran for 1.7 sec code2
(25 Dec '12, 01:04)
upper codes are giving WA.
(25 Dec '12, 01:06)
