Randomness

You’re given a string S of N characters. It’s known that the string consists of lowercase latin letters. The string is generated randomly. That means that every symbol is chosen randomly and independently from others from the set {‘a’, ‘b’, …, ‘z’}. All the letters has equal probability to appear.

You’re given Q queries on this string. Each query is of the form P C, where P is an integer between 1 and N (both inclusive) and C is a character from the set {‘a’, ‘b’, …, ‘z’}. Both P and C were chosen at random and independently from other queries.

When you have a query of the form P C you have to change the Pth symbol of S to C. After every change we ask you to output the number of distinct nonempty sub-strings of S.

Input Format
The first line of input consists of two single space separated integers N and Q - the length of the string S and the number of queries respectively.

The second line contains the string S itself.

The following Q lines describe the queries in the form P C, where P and C are also separated with a single space.

Constraints

4 ≤ N ≤ 75000
4 ≤ Q ≤ 75000

Output Format
Output Q lines. Output the number of distinct substrings of S after the ith query on theith line of the output.

Sample Input

4 4 
aaab
1 a
2 b
3 c
4 d

Sample Output

7
7
9
10

Explanation

after replacing the character at 1st index with a, we still have the original string aaab. The total non empty substrings of aaab are

a b aa ab aaa aab aaab

hence 7.

after replacing the character at 2nd index with b, we have the string abab. The total non empty substrings of abab are

a b ab ba aba bab abab

hence 7.

after replacing the character at 3rd index with c, we have the string abcb. The total non empty substrings of abcb are

a b c ab bc cb abc bcb abcb

hence 9.

after replacing the character at 4th index with d, we have the string abcd. The total non empty substrings of abcd are

a b c d ab bc cd abc bcd abcd

hence 10.

Scoring

There are 12 test cases.

The first four test cases N = 100 and Q = 500
The next four test cases N = 75000 and Q = 10
The last four test cases N = 75000 and Q = 75000

solution-->

The solution consists of constructing the suffix array and then finding the number of distinct substrings based on the Longest Common Prefixes.

One key observation here is that:

If you look through the prefixes of each suffix of a string, you have covered all substrings of that string.

Let us take an example: BANANA

Suffixes are:

0) BANANA
1) ANANA
2) NANA
3) ANA
4) NA
5) A

It would be a lot easier to go through the prefixes if we sort the above set of suffixes, as we can skip the repeated prefixes easily.

Sorted set of suffixes:

5) A
3) ANA
1) ANANA
0) BANANA
4) NA
2) NANA

From now on, 

LCP = Longest Common Prefix of 2 strings.

Initialize

ans = length(first suffix) = length("A") = 1.

Now consider the consecutive pairs of suffixes, i.e, [A, ANA], [ANA, ANANA], [ANANA, BANANA], etc. from the above set of sorted suffixes.

We can see that,

LCP("A", "ANA") = "A".

All characters that are not part of the common prefix contribute to a distinct substring. In the above case, they are 'N' and 'A'. So they should be added to ans.

So we have, 

1 2	ans += length("ANA") - LCP("A", "ANA") ans = ans + 3 - 1 = ans + 2 = 3

Do the same for the next pair of consecutive suffixes: ["ANA", "ANANA"]

1 2 3 4

LCP("ANA", "ANANA") = "ANA". ans += length("ANANA") - length(LCP) => ans = ans + 5 - 3 => ans = 3 + 2 = 5.

Similarly, we have:

1 2	LCP("ANANA", "BANANA") = 0 ans = ans + length("BANANA") - 0 = 11

1 2	LCP("BANANA", "NA") = 0 ans = ans + length("NA") - 0 = 13

1 2	LCP("NA", "NANA") = 2 ans = ans + length("NANA") - 2 = 15

Hence the number of distinct substrings for the string "BANANA" = 15.

code---->

#include<iostream>

#include<string>

#include<algorithm>

using namespace std ;

int LCP(string s , string s1){

int x=s.size();

int y=s1.size();

if(x>y)

    x=y;

    int count=0 ;

    for(int i=0 ; i < x ;i++){

        if(s.at(i)==s1.at(i))

            count++;

        else

         break ;

    }

return count ;

}

void check(string s){

    int x= s.size();

    string ss[x];

    

    for(int i=0 ; i<x ;i++)

        ss[i]= s.substr(i);     

         sort(ss,ss+x);

         int ans=0;

         ans=ss[0].size();

      for(int i=1 ; i<x ; i++)

    ans+=( ss[i].size() - LCP(ss[i],ss[i-1]));

    cout << ans << endl ;    

}

int main(){

    int x=0,y=0 ;   

    cin >> x >> y ;

     string s ;

    cin >> s ;

    while(y--){

          int p ;

          char z ;

         cin >>p >> z ;

         s[p-1]=z;

         check(s);

     }

    return 0 ;   

}

Manasa loves Maths

You are given an integer N. Is there a permutation of digits of integer that’s divisible by 8? A permutation of digits of integer N is defined as an integer formed by rearranging the digits of N. For example, if the number N = 123, then {123, 132, 213, 231, 312, 321} are the possible permutations.

Input Format
The first line contains an integer T i.e. number of test cases.
T lines follow, each containing the integer N.

Output Format
For each test case print YES if there exists one such re-arrangement of N such that it is divisible by 8 or NO if there isn’t.

Constraints
1 <= T <= 45
0 <= N <= 10110

Note
Re-arrangements of 10 are {10, 01} which boils down to {10, 1}.

Sample Input

2
61
75

Sample Output

YES
NO

Explanation
Test case #00: 16 is permutation of 61 which is divisible by 8.
Test case #01: None of permutation of 75, {57, 75}, are divisible by 8.

solution -----> we know that if last 3 digit of a number is divisible by 8 then the whole no is divisible by 8 .

code-->

import java.util.*;

class Solution{

   

    static boolean ok(int i ,int j ,int k , String s){

        

        if((s.charAt(i)*100 + s.charAt(j)*10 + s.charAt(k))%8==0)

          return true ;

        else

            return false ;

    }

    

    static void check(String z){

        

        int si = z.length();

         

        if(si==0){

                System.out.println("NO");

                return ;

            }

      

        if(si==1){

            if(Integer.parseInt(z)%8==0){

                System.out.println("YES");

                return ;

            }

            System.out.println("NO");

                return ;

        }

        

        if(si==2){

            int a = z.charAt(0)-48 ;

            int b = z.charAt(1)-48 ;

            

            if(((a*10+b)%8==0) || ((b*10+a)%8==0)){

                System.out.println("YES");

                return ;

            }

            System.out.println("NO");

                return ;

        }

        

         

        for(int i=0 ; i < si-2 ;i++){

                for(int j=i+1 ; j < si-1 ; j++){

                       for(int k = j+1 ; k < si ; k++ ){

                         

                     if(ok(i,j,k,z) || ok(i,k,j,z) || ok(j,i,k,z) || ok(j,k,i,z) || ok(k,j,i,z) || ok(k,i,j,z) ){

                         System.out.println("YES");

                            return ;    

                     }  

                  }

                }

        }

        

        System.out.println("NO");    

    }

    

    

    public static void main(String ss[]){

        Scanner s = new Scanner(System.in);

        String  a = s.nextLine();

        boolean answer =false;

        int t = Integer.parseInt(a);

        

        for(int i=0;i<t;i++){

            String  z = s.nextLine();

            check(z);

        }

    }

}