- Given three strings p, q, r. Count the possible number of ways to create string r using string p and string q such that, the order of the selected characters in all the strings is preserved and at least one character from both the strings (p and q) is selected.
Note
Strings will have max length 100
They will consist of lowercase english alphabets.
Return the answer modulo 10^9 + 7.
Sample test case
p: ab
q: ba
r: aba
output: 2
Two ways to form aba
from p, a, from q, ba
from p, ab, from q, a
[execution time limit] 1 seconds (cpp)
[input] string p
[input] string q
[input] string r
[output] integer
[C++] Syntax Tips
// Prints help message to the console
// Returns a string
string helloWorld(string name) {
cout << "This prints to the console when you Run Tests" << endl;
return "Hello, " + name;
}
- You and your best friend leave messages for one another in your favorite places around town. But you don't want any strangers to read them, so you hide them within strings. To decode a message in a string you need to find a string subsequence of length 5 which is a palindrome - this subsequence is the code itself.
Given a string message, return the number of such subsequences within it.
Example
For message = "abcdba", the output should be
solution(message) = 2.
You can obtain such palindromes: "abcba" and "abdba".
For message = "aabccba", the output should be
solution(message) = 4.
You can obtain "abcba" 4 times with different a and c from the given string.
Input/Output
[execution time limit] 0.5 seconds (cpp)
[input] string message
The encrypted message.
Guaranteed constraints:
1 ≤ message.length ≤ 700.
[output] integer
The number of subsequence palindromes with exactly 5 letters in the given string. It's guaranteed that for the given test cases the answer always fits signed 32-bit integer type.
[C++] Syntax Tips
// Prints help message to the console
// Returns a string
string helloWorld(string name) {
cout << "This prints to the console when you Run Tests" << endl;
return "Hello, " + name;
}
3.You are given a tree of N nodes rooted at node 1. The tree will be given as an array p of size (N-1), where p[i] (0<=i<N-1) represents the parent of the (i+1)th node.
Each node also has a value associated with it, given as an array val of size N.
For each node V, you have to calculate the number of nodes in the subtree of V whose value is co-prime with the value of V.
You need to return the sum of this value for all nodes in the tree as an answer.
Constraints
1 <= n <= 100000
1 <= val[i] <= 1000
array p represents a valid tree, rooted at node 1.
Sample Input:
n: 5
par: [1, 1, 3, 3]
val: [1,2,3,4,5]
Sample Output:
6
Sample Explanation:
par array is [1,1,3,3]. This means parent of node 2 and node 3 is 1, and parent of node 4 and node 5 is 3.
val array is [1,2,3,4,5]. This means values of nodes 1,2,3,4 and 5 are 1,2,3,4 and 5 respectively.
The tree looks like this:
Sample Tree
For node 1, the nodes in its subtree whose values are co-prime with value of 1, i.e. 1 are: 2,3,4 and 5. Count: 4
For nodes 2,4 and 5 there are no such nodes as they have no subtree.
For node 3, the nodes in its subtree whose values are co-prime with value of 3 i.e. 3 are: 4 and 5. Count: 2.
So final answer = 4 + 2 = 6.
Input Generation
You are not directly given the arrays p and val. Instead you are given four integers N, seed, l, r and s for randomly generating the arrays p and val. Use the following stub to begin with:
int p[100001], val[100001]; // global arrays which will be randomly generated by below function
void generateTree(int N, int seed, int L, int R, int S) {
srand(seed);
for(int i=1;i<=N-1;i++) {
p[i] = max(1, i-S+1) + (rand() % (i+2 - max(1, i-S+1))); // random node in [i-S+1, i+1]
}
for(int i=1;i<=N;i++) {
val[i] = L + rand() % (R-L+1); // random integer between L and R
} }
long long solution(int n, int seed, int l, int r, int s) {
generateTree(n, seed, l, r, s); // Call the random generator to generate p and val arrays first
// Write your code from here
}
[execution time limit] 3 seconds (cpp)
[input] integer n
The number of nodes in the tree. 1 <= n <= 100000
[input] integer seed
parameter for random generation
[input] integer l
parameter for random generation
[input] integer r
parameter for random generation
[input] integer s
parameter for random generation
[output] integer64
The sum of the number of co-prime values in the subtree, for each node.
