Question: Trilogy Innovation(CodeNation), Intern Hunt, 18th December, 2022
1
Entering edit mode

# 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 &lt;= |s|, Q &lt;= 1e5
1 &lt;= i &lt;= |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.
``````
3
Entering edit mode

## 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&lt;int&gt;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 &lt; n; i++) {
p[i] = max(0ll, min(r - i, p[l + r - i]));
while (i + p[i] &lt; n and i - p[i] &gt;= 0 and s[i + p[i]] == s[i - p[i]])
p[i]++;
if (p[i] + i &gt; 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 -&gt; #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.

Entering edit mode
0

I've done it using string hashing and binary search. Overall complexity O(Q*log(N))

``````#include &lt;bits/stdc++.h&gt;
using namespace std;
#define int long long

#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(x...)
#endif

struct H {
uint64_t x; H(uint64_t x = 0) : x(x) {}
H operator+(H o) { return x + o.x + (x + o.x &lt; x); }
H operator-(H o) { return *this + ~o.x; }
H operator*(H o) {
auto m = (__uint128_t)x * o.x;
return H((uint64_t)m) + (uint64_t)(m &gt;&gt; 64);
}
uint64_t get() const { return x + !~x; }
bool operator==(H o) const { return get() == o.get(); }
bool operator&lt;(H o) const { return get() &lt; o.get(); }
};
static const H C = (long long)1e11 + 3; // (order ~ 3e9; random also ok)

struct Hash {
vector&lt;H&gt; ha, pw;
Hash(string&amp; str) : ha(str.size() + 1), pw(ha) {
pw[0] = 1;
for (int i = 0; i &lt; str.size(); i++) {
ha[i + 1] = ha[i] * C + str[i],
pw[i + 1] = pw[i] * C;
}
}
H query(int a, int b) { // hash [a, b)
return ha[b] - ha[a] * pw[b - a];
}
};

void solve() {
string s; cin &gt;&gt; s;
int n = s.size();
Hash sh(s);
string t = s;
reverse(t.begin(), t.end());
Hash rsh(t);
int q; cin &gt;&gt; q;

function&lt;bool(int, int)&gt; check = [&amp;](int start, int end) {
int start1 = n - 1 - end, end1 = n - 1 - start;
return (sh.query(start, end + 1) == rsh.query(start1, end1 + 1));
};

function&lt;int(int)&gt; get = [&amp;](int i) {
int lo = 1, hi = min(n - i - 1, i);
int ans = 0;
while (lo &lt;= hi) {
int mid = (lo + hi) / 2;
int left = i - mid, right = i + mid;
if (check(left, right)) {
ans = 2 * mid + 1;
debug(ans);
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
};

while (q--) {
int i; cin &gt;&gt; i;
--i;
cout &lt;&lt; get(i) &lt;&lt; '\n';
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
int  t = 1;
// cin &gt;&gt; t;
while (t--)
solve();

return 0;
}
``````
Arpan Desai
• 0
2
Entering edit mode

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 &amp;s)
{
if(idx==(int)s.size())
{
return 1;
if(2*XOR&gt;(mx+mn))
return 1;
return 0;
}

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

ans+=G(idx+1,(tight&amp;&amp;(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)