parbhu's blog

By parbhu, history, 4 years ago, In English

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
Sample test Case

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.
Sample Test Case
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.

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it