LELUCKYN - Editorial

editorial
, , , ,
1

PROBLEM LINK

Practice
Contest

DIFFICULTY

MEDIUM

PREREQUISITES

Maths, Binary Search

PROBLEM

You are given a list of N numbers, say A. Find the number of ranges (L, R) such that

  • If C4 = number of 4s in A[i], i = L to R, inclusive
  • If C7 = number of 7s in A[i], i = L to R, inclusive
  • C4C7 ≤ R-L+1
  • C4 ≠ 2 and C7 ≠ 2

QUICK EXPLANATION

There 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].
Let, A7[i] be the number of 7s in A[i].
Let, C4[i] be the number of 4s in A[ 1 … i ]. We set C4[0] = 0.
Let, C7[i] be the number of 7s in A[ 1 … i ]. We set C7[0] = 0.

In terms of sequences C4[] and C7[] the problem can be stated as follows: find all pairs (L; R) for which:

  • 0 ≤ L < R ≤ N
  • (C4[R] - C4[L])C7[R] - C7[L] ≤ R - L
  • C4[R] - C4[L] ≠ 2
  • C7[R] - C7[L] ≠ 2

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.

  • count1(A,v)
    • Find the number of pairs (L, R) in A such that A[R]-A[L] = v
  • count2(A,a,B,b)
    • Find the number of pairs (L, R) such that
    • a = A[R] - A[L]
    • b = B[R] - B[L]
    • L + ab ≤ R
  • count3(A,B)
    • Find the number of pairs (L, R) such that
    • A[R] - A[L] ≤ R - L
    • B[R] - B[L] = 1

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.

EXPLANATION

count1(A,v)

  • Since A is sorted, we can iterate over L and maintain a range of values for R, within which A[R]-A[L] = v.
  • As L increases, R1 can only increase, and hence, R2 can also only increase.

count2(A,a,B,b)

  • Similar to count1, we iterate over L and maintain valid range of values for R.
    • One set of values for the condition A[R]-A[L] = a
    • Another set of values for the condition B[R]-B[L] = b
  • We also want the minimum value of R to be L + ab
    • Hence we can find the closed interval within which there is a valid value of R, and add that range for each L.

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.

  • Similar to count1 and count2, we can iterate over L and try to find the range R, which satisfies the constraints.
  • Since C7 = 1, we already have one insight
    • For an L, R1 and R2 will be the next range that contains only one 7 in between L and R1 to R2.
    • This means, that as soon as L becomes equal to R1, the next value of R1 will be R2 + 1, and next value of R2 will be the next 7, in C7 (or the end of the array).
    • We will see why this is helpful below.

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

  • C4[R] - R ≤ C4[L] - L

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

  • The complexity of count1 is O(N).
  • The complexity of count2 is O(N).
  • The complexity of count3 is O(N log N).
  • The number of iterations in considering each c4 and c7 where c4 ≥ 3, c7 ≥ 3 and c4c7 ≤ N is in fact very small: ~78 for N = 100000. But one can prove that complexity in this case is O(N * N1/3).

SETTERS SOLUTION

Can be found here.

TESTERS SOLUTION

Can be found here.

2

how to optimise this solution if i take the input as strings.

#include<iostream>
#include<string.h>
#include<algorithm>
#include<cstdio>
#include<math.h>

using namespace std;

int main()
{
    int t,n,i,j,k,c4,c7,l;
    scanf("%d",&t);
    while(t--)
    {
     c4=0;c7=0;
     scanf("%d",&n);
     
     int j=0;
     char s[100];
     int a4[n],a7[n];
     while(j<n)
     {
      c4=0;c7=0;
      scanf("%s",&s);
      l=strlen(s);
      for(i=0;i<l;i++)
      {
       if(s[i]=='4')
       c4++;
       if(s[i]=='7')
       c7++;
      }
      a4[j]=c4;
      a7[j]=c7;
      j++;
     }
    int c4f=0;
    int c7f=0;
    int ans=0;
     for(i=0;i<n;i++)
     {
     c4f=0;
     c7f=0;
      for(j=i;j<n;j++)
      {
       c4f+=a4[j];
       c7f+=a7[j];
       if((pow(c4f,c7f)<=j-i+1) && (c4f!=2) && (c7f!=2))
        ans++;  
      }
     }
     
     printf("%d\n",ans);
  }
  
  system("PAUSE");
}
3

code

please give some test case for breaking this.

4

I am just sharing, donot know how much it is right. in your inner j loop, you can make j not just inc each time but put an else part and do something like it would be able to satisfy it next time. see the code in the comment below. but it is also giving wrong answer

5

i modified my code thinking that pow should be long long.
but it is also giving wrong answer.

code

another code that gave time limit exceeded and ran for 1.7 sec
code2

6

sorry the TLE code is this.

upper codes are giving WA.