5 weeks ago

Rohit • 600

Hyderabad

Question 1

Comedy Show

There are 2*N comedians and M audience member in a comedy show. The first N comedians are male and the last N are female. In a comedy show, all the comics gets one slot to perform their act. The slots are alloted randomly and any allocation is equally probable.

Each of the comedians has a humour level given by the array A. The charge of each comedian is given by the array B.

Each of the audience member has a tolerance level given by array C and seriousness level given by array D. The gender of the member is given by the array E where E[i] = 1 denotes that member is male and E[i] = 2 denotes that member is female.

A comic of same gender as an audience member will make that member laugh if there have been atleast C[i] comics before them of the same gender such that their humour level is more than D[i] of that member.

A comic of opposite gender as an audience member will make that member laugh if there have been atleast C[i] comics before them of the same gender of the comic such that their humour level is more than the 2*D[i] of that member.

If a member laughs, then they have to pay that comedian B[i] coins.

What is the expected sum of amount that all the comedians will earn in a single show. Express the expected sum as an irreducible fraction u/v, then you have to find the value of u * v^-1 mod 10^9+7.

Problem Constraints

• 1 <= N <= 10^5
• 1 <= M <= 10^5
• 1 <= A[i] <= 10^9
• 1 <= B[i] <= 10^9
• 1 <= C[i] <= N
• 1 <= D[i] <= 10^9
• 1 <= E[i] <= 2

Input Format

First argument A is an integer array denoting the humour level of each comedian 
Second argument B is an integer array denoting the charge of each comedian 
Third argument C is an integer array denoting the tolerance level of each audience member 
Fourth argument D is an integer array denoting the seriousness level of each audience member 
Fifth argument E is an integer array denoting the gender of each audience member 

Output Format

Return an integer denoting the expected sum of amount that all the comedians will earn in a single show.

Example Input

Input 1

A = [20, 2, 8, 17]
B = [16, 8, 8, 6]
C = [1, 1]
D = [6, 9]
E = [1, 2]

Input 2

A = [20, 2, 8, 17]
B = [16, 8, 8, 6]
C = [1, 1]
D = [9, 6]
E = [1, 2]

Example Explanation

For Input 1:
The first audience member will laugh during the act of 2-nd comic if 1-st comic performed before his.
He will laugh during the performance of 3-rd comic if the 4-th comic have performed before.
Both these have a 50% probability, so the expect sum that the first member pays is (8+8)/2 = 8

The second audience member will laugh during the act of 2-nd comic if 1-st comic performed before his.
She will laugh during the act of 3-rd comic if the 4-th comic have performed before her.
Both these have a 50% probability, so the expect sum that the second member pays is (8+8)/2 = 8

So the net expected sum the comedians make in the show is 8+8 = 16.

Question 2

Given a string S(consisting of only lower characters) and Q queries.

In each query you will given an integer i and your task is to find the length of longest odd palindromic substring whose middle index is i.

Note:

1. Assume 1 based indexing
2. Longest odd palindrome: A palindrome substring whose length is odd.

Problem Constraints

1 <= |s|, Q <= 1e5
1 <= i <= |s|

Input Format

First Argument A is string S.
Second Argument B is an array of integers where B[i] denotes the query index of ith query.

Output Format Return an array of integers where ith integer denotes the answer of ith query.

Example Input

Input 1

A = aaaaa
B = [2, 3]

Input 2

A = abcd
B = [2]

Example Output

Output 1:

[3, 5]

Output 2:

[0]

Example Explanation

Explanation 1:

For first query longest palindrome is aaa.
For second query whole string is the longest palindrome.

Explanation 2:

No palindrome is present.

Question 3

A number is beautiful if the xor sum of the digits of the number is strictly greater than the average of the minimum and maximum digit of the number. Given A and B, find the count of beautiful numbers in the range [A, B].

Since the answer can be very large, output the remainder after dividing the answer by 10^6+7

Note: The xor sum of the digits of a number is the bitwise XOR of all its digits.

Problem Constraints 1

• 1 <= A <= B <= 10^18

Input Format

• First argument A is a number in form of a string.
• Second argument B is a number in form of a string.

Output Format

• Return an integer

Example Input

Input 1

A = "10"
B = "12"

Input 2

A = "32"
B = "35"

Example Output

Output 1

2

Output 2

2

Example Explanation

For Input 1:

For 10, xor sum = 1, average of maximum and minimum digit is 0.5 
For 11, xor sum = 0, average of maximum and minimum digit is 1 
For 12, xor sum = 3, average of maximum and minimum digit is 1.5 
The beautiful numbers are 10 and 12.

For Input 2:

For 32, xor sum = 1, average of maximum and minimum digit is 2.5 
For 33, xor sum = 0, average of maximum and minimum digit is 3 
For 34, xor sum = 7, average of maximum and minimum digit is 3.5 
For 35, xor sum = 6, average of maximum and minimum digit is 4 
The beautiful numbers are 34 and 35.

28 days ago

Akash 240

New Delhi

Question 2: Palindrome Query

Overview

• For every query, find the length of the longest odd palindrome with the given center index.

Approach

• We solve this problem using Manacher’s algorithm. If we need to calculate Longest Palindromic Substring at each 2*|S|+1 position from left to right, then the palindrome’s symmetric property could help to avoid some of the unnecessary computations (i.e., character comparison). If there is a palindrome of some length L centered at any position i, then we may not need to compare all characters on left and right sides at position i+1. We already calculated LPS at positions before i, and they can help to avoid some of the comparisons after position i.

Pseudocode

This structure is used to implement Manacher's algorithm; first, the build function helps create the string, and then the run_manacher function is used to create the LPS array. getLongest function returns the longest palindrome with cen as the center, depending on whether it is an odd palindrome or even.

struct manacher {
    vector<int>p;          //array p will store the size of longest palindrome with ith index as centre
    void run_manacher(string s) {
        int n = s.size();
        p.assign(n, 1);      
        int l = 1, r = 1;
        for (int i = 1; i < n; i++) {
            p[i] = max(0ll, min(r - i, p[l + r - i]));
            while (i + p[i] < n and i - p[i] >= 0 and s[i + p[i]] == s[i - p[i]])
                p[i]++;
            if (p[i] + i > r)
                l = i - p[i], r = i + p[i];
        }
    }
    void build(string s) {
        string t = "";         //to generalise both odd and even palindromes, ‘#’ is added before and after each character    Eg: abba -> #a#b#b#a#
        for (auto x : s) {
            t += string("#") + x;
        }
        run_manacher(t + "#");
    }
    int getLongest(int cen, bool odd) {
        return p[2 * cen + 1 + (!odd)] - 1 == 1 ? 0 : p[2 * cen + 1 + (!odd)] - 1;
    }
} manacher;

Complexity

O(|S|+Q) |S| is the size of the string and Q are the number of queries.

7 months ago

Shikhar Mehrotra 480

Chennai

Q3)

Solution for 3

• The question can be solved using digit DP.
• Let's define F(R) as count of integers <=R which are beautiful
• Hence our answer would be finally F(R)-F(L-1)

Computing F(X)

• Let's define G(idx,tight,lead,XOR,mx,mn) as count of integers(<=X) and we have kept digits at positions[0,idx-1] such that bitwise xor of digits is XOR and maximum digit among all digit is mx and minimum digit is mn and tight is followed till idx-1 and lead represent that whether a non-zero digit has been put on some position from [0,idx-1].

  • S[l,r] represent digits of S from l to r , for eg: 522323[0,3]=5223
  • if tight=1 it means that integer formed is exactly same as that of index [0,idx-1] or integer_formed[0,idx-1]=X[0,idx-1]
  • if tight=0 it means that integer formed is less than X[0,idx-1]

• F(X) = G(0,1,1,0,0,9,X)
• Hence we could define recursion by:

    int G(int idx,int tight,bool lead,int XOR,int mx,int mn,string &s)
    {
        if(idx==(int)s.size())
        {
            if(lead)
                return 1;
            if(2*XOR>(mx+mn))
                return 1;
            return 0;
        }

        int up=9;
        if(tight)
            up=s[idx]-'0';
        int ans=0;
        for(int d=0;d<=up;d++)
        {
            if((!lead)||(d))
            {
            ans+=G(idx+1,(tight&&(d==up)),0,(XOR xor d),max(mx,d),min(mn,d),s);
            ans%=mod;
            }
            else
            {

                ans+=G(idx+1,(tight&&(d==up)),1,XOR,mx,mn,s);

            }
        }
        return ans;
    }

• Finally above recursion could be optimized by memoizing the states.
• Answer would be G(0,1,1,0,0,9,R)-G(0,1,1,0,0,9,L-1) or F(R)-F(L-1)