Problem 1:↵
↵
You are given an array consisting of n integers. You are given q queries. Each query has two integers x and m. for each query, you are required to determine the array value that provides the maximum bitwise XOR value with x where the array value is not more than m.↵
↵
In other words, for each query, you must find arr[i] (1<=i<=n , arr[i]<=m) such that the value of (x ^ arr[i]) is maximum where ^ denotes bitwise XOR operator. If there is no such value that satisfies the condition, then print -1.↵
↵
Input Format:↵
↵
- first line contains an integer t denoting the number of test cases.↵
- first line of each test case contains an integer n denoting the number of elements in the array.↵
- second line of each test case contains n space-separated integers denoting arr[1],arr[2],.....,arr[n].↵
- third line of each test case contains an integer q denoting the number of queries.↵
- next q lines contain two integers x and m denoting the ith query.↵
↵
Output Format:↵
↵
- For each test case, print q space-separated integers denoting the required answer.↵
↵
Constraints:↵
↵
- 1<=t<=5↵
- 1<=n,q<=10^5↵
- 0<=arr[i],x,m<=10^9↵
↵
<spoiler summary="Sample test Case">↵
Input:↵
↵
1↵
↵
7↵
↵
3 7 19 18 7 12 17↵
↵
7↵
↵
3 8↵
↵
21 20↵
↵
24 17↵
↵
1 7↵
↵
23 17↵
↵
12 9↵
↵
28 1↵
↵
Output: ↵
7↵
12↵
7↵
7↵
12↵
3↵
-1↵
</spoiler>↵
↵
Problem 2:↵
↵
You are given a matrix A of size N*N. Assign the letter 'a' and ID 1,'b' and ID 2, and so on. Here, A[i][j] denotes the value in cell(i,j) of matrix A denotes the cost of writing the letter corresponding to ID j immediately after the letter corresponding to ID i.↵
↵
Now, you are given a string S consisting of distinct lowercase alphabets and you have to determine the minimum cost to generate any permutation of the given string.↵
↵
A permutation of a string is the rearrangement of the letters of the string.↵
↵
NOTE: The cost of writing the first character is zero as no characters are present before the first character.↵
↵
Input Format:↵
↵
- The first line contains a single integer N.↵
- Next N lines contain N space-separated integers denoting matrix A.↵
- The next line contains a string S.↵
↵
Output Format:↵
↵
Print a single integer denoting the minimum cost as explained in the problem.↵
↵
Constraints:↵
↵
- 1<=N<=20↵
- 1<=A[i][j]<=10^9(i!=j)↵
- A[i][j]=0(i=j)↵
- 1<=|S|<=N↵
- S contains letters up to first N letters of lowercase alphabets.↵
- All characters in S are distinct.↵
↵
<spoiler summary="Sample Test Case">↵
Input:↵
↵
5↵
↵
0 5 1 5 3↵
↵
4 0 9 4 2↵
↵
7 9 0 10 7↵
↵
1 2 8 0 2↵
↵
3 9 7 7 0↵
↵
abcde↵
↵
Output:↵
8↵
</spoiler>↵
↵
<spoiler summary="Spoiler">↵
Both of the above questions were asked in Google online Challenge for summer Internship 2021 on 29th August 2020. ↵
</spoiler>↵
↵
Someone please tell me the approach to solve these problem and also comment what you think about the difficulty level of these questions with respect to Div 2-A,B,C,D,E,F and Problem Rating. ↵
↵
You are given an array consisting of n integers. You are given q queries. Each query has two integers x and m. for each query, you are required to determine the array value that provides the maximum bitwise XOR value with x where the array value is not more than m.↵
↵
In other words, for each query, you must find arr[i] (1<=i<=n , arr[i]<=m) such that the value of (x ^ arr[i]) is maximum where ^ denotes bitwise XOR operator. If there is no such value that satisfies the condition, then print -1.↵
↵
Input Format:↵
↵
- first line contains an integer t denoting the number of test cases.↵
- first line of each test case contains an integer n denoting the number of elements in the array.↵
- second line of each test case contains n space-separated integers denoting arr[1],arr[2],.....,arr[n].↵
- third line of each test case contains an integer q denoting the number of queries.↵
- next q lines contain two integers x and m denoting the ith query.↵
↵
Output Format:↵
↵
- For each test case, print q space-separated integers denoting the required answer.↵
↵
Constraints:↵
↵
- 1<=t<=5↵
- 1<=n,q<=10^5↵
- 0<=arr[i],x,m<=10^9↵
↵
<spoiler summary="Sample test Case">↵
Input:↵
↵
1↵
↵
7↵
↵
3 7 19 18 7 12 17↵
↵
7↵
↵
3 8↵
↵
21 20↵
↵
24 17↵
↵
1 7↵
↵
23 17↵
↵
12 9↵
↵
28 1↵
↵
Output: ↵
7↵
12↵
7↵
7↵
12↵
3↵
-1↵
</spoiler>↵
↵
Problem 2:↵
↵
You are given a matrix A of size N*N. Assign the letter 'a' and ID 1,'b' and ID 2, and so on. Here, A[i][j] denotes the value in cell(i,j) of matrix A denotes the cost of writing the letter corresponding to ID j immediately after the letter corresponding to ID i.↵
↵
Now, you are given a string S consisting of distinct lowercase alphabets and you have to determine the minimum cost to generate any permutation of the given string.↵
↵
A permutation of a string is the rearrangement of the letters of the string.↵
↵
NOTE: The cost of writing the first character is zero as no characters are present before the first character.↵
↵
Input Format:↵
↵
- The first line contains a single integer N.↵
- Next N lines contain N space-separated integers denoting matrix A.↵
- The next line contains a string S.↵
↵
Output Format:↵
↵
Print a single integer denoting the minimum cost as explained in the problem.↵
↵
Constraints:↵
↵
- 1<=N<=20↵
- 1<=A[i][j]<=10^9(i!=j)↵
- A[i][j]=0(i=j)↵
- 1<=|S|<=N↵
- S contains letters up to first N letters of lowercase alphabets.↵
- All characters in S are distinct.↵
↵
<spoiler summary="Sample Test Case">↵
Input:↵
↵
5↵
↵
0 5 1 5 3↵
↵
4 0 9 4 2↵
↵
7 9 0 10 7↵
↵
1 2 8 0 2↵
↵
3 9 7 7 0↵
↵
abcde↵
↵
Output:↵
8↵
</spoiler>↵
↵
<spoiler summary="Spoiler">↵
Both of the above questions were asked in Google online Challenge for summer Internship 2021 on 29th August 2020. ↵
</spoiler>↵
↵
Someone please tell me the approach to solve these problem and also comment what you think about the difficulty level of these questions with respect to Div 2-A,B,C,D,E,F and Problem Rating. ↵
