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
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.
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.
Problem 1] can be solved offline using trie, sort the queries and the values of the array, now the task is just to calculate value in array using trie that give max xor with X. Until this point trie will have values less than m value of query as we are solving offline, store the answer.
This link will give you idea how to calculate max xor with a particular value.
Problem 2] can be solved using bitmask dp in N^2 * 2^N
where dp will be like dp[mask][last_char] , here mask represents the characters we covered and last_char represents last_character we used, which we will use in making transitions.
This blog would be helpful for learning subset dp.
code for Problem 1 using above logic ,
Auto comment: topic has been updated by parbhu (previous revision, new revision, compare).
I think problem 2 can also be solved greedily? We can make a graph of N^2 edges of the given string and then try to find the MST of the graph.
I think it can't be done using MST. As you have to consider directed edges in that case. Bitmask DP is the only go I think.
Considering min cost of edges i -> j and j -> i and including that only can solve the issue, can it? As only one of them will be there in the final ans and considering any of them shouldn't change the cost of other orderings.
MST won't work because you can only use 1 outgoing edge from each vertex (because an edge A->B is 'place letter B right after letter A'). MST algorithm's won't account for that, and given that N <= 20, it strongly suggests an exponential solution.
It translates very easily to TSP, which you can solve in $$$O(N2^N)$$$ with bitmasks as darkcoder123 mentioned.
may not be. As if I understand correctly A[i][j] is cost of writing j immediately after i, not in general after i. So in the final answer both i->j and j->i may not be present.