## Description

1. Given an array P with elements p1, p2, …, pn and an n×n sized binary symmetric matrix A, you have to find

the lexicographically minimum permutation which can be achieved by swapping two distinct elements pi and

pj where the condition A[i][j]= 1 holds and 1 ≤ i, j ≤ n.

Input:

First line contains n.

Second line contains n elements of array P.

Each of the next n lines contains n

2

integers which denote matrix A as a whole. A[i][j] = 1 means pi and pj

can be swapped, otherwise no swapping can be done.

Output:

The lexicographically minimum permutation that can be achieved by swapping.

Example:

Input:

7

5 2 4 3 6 7 1

0001001

0000000

0000010

1000001

0000000

0010000

1001000

Output:

1 2 4 3 6 7 5

2. You want to sort n different arrays (each of size m) simultaneously. You can choose a pair of distinct indices

i and j (1 ≤ i, j ≤ m, i ≠ j). Then, in each array, the values at positions i and j are swapped only if the value at

position i is strictly greater than the value at position j. You want to find an array containing pairs of distinct

indices that, chosen in order, will sort all of the n arrays in ascending order or descending order.

Input:

Two integers n (no. of arrays) and m (size of each array) and k (k is zero if sorting is to be done in ascending

order and 1 if sorting is to be done in descending order).

Each of the next m lines contains the arrays of size m.

Output:

In the first line of the output, print an integer p, the size of the array (p can be at most m*(m-1)/2). Each of

the next p lines must contain two distinct integers i and j (1 ≤ i, j ≤ m, i ≠ j), representing the chosen indices.

Example:

Input:

2 5 0

1 3 2 5 4

1 4 3 2 5

Output:

3

2 4

2 3

4 5

3. You are a dog lover and thus you don’t like cats. You live by an unusual park. The park is a rooted tree of

n vertices with root node as 1. Vertex 1 also contains your house. Unfortunately, some vertices also contain

cats and you know those vertices. You want to travel to each of the leaves of the tree starting from your

house. But since you don’t like cats, if you encounter m consecutive cats in your path from your house to a

leaf node then you drop the path.

Input:

The first line contains two integers, n and m — the number of vertices of the tree and the maximum number

of consecutive vertices with cats that is still ok for you.

The second line contains n integers a1, a2, …, an where each ai either equals to 0 (then vertex i has no cat),

or equals to 1 (then vertex i has a cat).

Each of the next n-1 lines contains the edges of the tree in the format xi, yi, where xi and yi are the vertices

of the tree, connected by an edge.

Output:

A single integer — the number of distinct leaves of a tree, the path to which from your home contains at

most m consecutive vertices with cats.

Example:

Input:

4 1

1 1 0 0

1 2

1 3

1 4

Output:

2

4. You have n different socks with you. Each of the socks is of a colour. The total colours are k. Your mom is

going out for a vacation and has made you a schedule for the m days she is going out for. For each of the m

days, she has written down l[i], r[i] (l[i] denoting the left sock and r[i] denoting the right sock) which you will

wear for the day. Now she was in a hurry and didn’t realise that you can’t wear socks of different colours on

the same day. However, you possess k jars of paint – one for each colour. You want to fix the situation by

swapping socks between the given pairs or/and recolouring some of them. Note that you want to change

the colours of minimum number of socks.

Input:

The first line of input contains three integers n, m and k— the number of socks, the number of days and the

number of available colours respectively.

The second line contain n integers c1, c2, …, cn (1 ≤ ci ≤ k) — current colours of your socks.

The third line contains the number of socks for each colour.

Each of the following m lines contains two integers li and ri— indices of socks which you should wear during

the i-th day.

Output:

Print one integer — the minimum number of socks that should have their colours changed in order to be

able to obey the instructions.

Example:

Input:

4 3 3

1 2 3

1 2 1

1 2

2 3

3 1

Output:

1

Explanation: Put ‘2’ from second pair to the first pair. The first pair is then 2 2 and the second pair is 1 3 and

the third pair is 3 1. Now, recolour sock ‘1’ to ‘3’ then your second pair is 3 3 and the third pair is also 3 3.

You will be wearing the same colour of socks for two consecutive days. Thus, the situation is fixed by coloring

only one sock.

5. Merging two arrays is an essential step in merge sort. Can we do the same in case of linked list? Given 2

sorted linked lists, devise a way to merge them while only using O(1) memory ?

Input:

First line contains the size of the first sorted array.

Second line contains the elements of the first sorted array.

Third line contains the size of the second sorted array.

Fourth line contains the elements of the second sorted array.

Output:

The final merged sorted array.

Example:

Input:

5

1 2 3 4 5

6

2 2 4 4 5 5

Output:

1 2 2 2 3 4 4 4 5 5 5

6. Sachin loved Gully Boy and he is now inspired to become a rapper. His friend Saurav gives him a string and

asks him to rap it in his own way. Sachin, after some time, figures out that if there is a substring in that string

which reads same even backwards sounds amazing. In order to impress the crowd, he decided to find the

longest substring possible that contains half of the characters in proper alphabetical order. In other words,

if the desired substring is of size 2k, then the first k (k > 1, i.e., the substring cannot be of size 2) characters

are in proper alphabetical order. If there are two substrings possible with the same longest length, then print

the one which comes first in alphabetical order. If no such substring can be found, print -1.

Input:

String s

Output:

The desired longest substring.

Example:

Input:

aaaabaaa

Output:

aaabaaa

Input:

abdccdba

Output:

-1 (Though the string is the same even when read backwards, but ‘d’ appears before ‘c’ in first half of the

string. Note that ‘cc’ is not considered as the required substring.)

Input:

adsarttriopiuxyyxx

Output:

rttr (Here, both rttr and xyyx read the same when read backwards. However, rttr precedes xyyx

alphabetically.)

7. Sharat is currently at a car rental service, and he wants to reach a cinema hall. The film he has bought a

ticket for starts in t minutes. There is a straight road of length s from the car rental service to the cinema.

Let’s introduce a coordinate system so that the car rental service is at the point 0, and the cinema is at the

point s. There are k gas stations along the road, and at each of them, you can fill a car with any amount of

fuel for free! Consider that this operation doesn’t take any time, i.e. can be carried out instantly. There are

n cars in the rental service, i-th of them is characterized with two integers ci and vi — the price of renting

this car and the capacity of its fuel tank in litres. It is not possible to fuel a car with more fuel than its tank

capacity vi. All cars are have fuel filled to the full tank capacity at the car rental service. Each of the cars can

be driven in one of two speed modes: normal or accelerated. In the normal mode, a car covers 1 kilometre

in 2 minutes, and consumes 1 litre of fuel. In the accelerated mode, a car covers 1 kilometre in 1 minute, but

consumes 2 litres of fuel. The driving mode can be changed at any moment and any number of times. Your

task is to choose a car with minimum price such that Sharat can reach the cinema before the show starts,

i.e. not later than in t minutes. Assume that all cars are completely fuelled initially.

Input:

The first line contains four positive integers n, k, s and t — the number of cars at the car rental service, the

number of gas stations along the road, the length of the road and the time in which the film starts.

Each of the next n lines contains two positive integers ci and vi— the price of the i-th car and its fuel tank

capacity.

The next line contains k distinct integers g1, g2, …, gk— the positions of the gas stations on the road in

arbitrary order.

Output:

Print the minimum rent price of an appropriate car, i.e. a car so that Sharat will be able to reach the cinema

before the film starts (not later than t minutes). If there is no appropriate car, print -1.

Example:

Input:

3 1 8 10

10 8

5 7

11 9

3

Output:

10

8. Captain America hasn’t given up the hope and is now looking for some ways to get back the infinity stones

from Thanos. He goes to Titan to search for him but instead is stuck in a 2D string grid. After sending a

distress signal to Captain Marvel, he receives a word. If that word exists in the grid, then Captain can come

out otherwise not. The word can be constructed from horizontally or vertically neighbouring letters. Refer

to sample cases for more clarity.

Note – The cell itself does not count as an adjacent cell. The same letter cell may be used more than once.

Input:

N (Number of strings) M (length of each strings)

Each of the next N lines would be strings with M length

T (Number of test cases)

Each of the next T lines would be words received from Captain marvel

Example:

Input:

3 4

ABCE

SFCS

ADEE

5

ABCCED

SEE

ABCB

ABFSAB

ABCD

Output:

Yes

Yes

Yes

Yes

No

9. Imagine you have a special keyboard with the following keys:

Key 1: Prints ‘A’ on screen

Key 2: (Ctrl-A): Select screen

Key 3: (Ctrl-C): Copy selection to buffer

Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Suppose you can only press the above mentioned four keys of the keyboard at most N times. Write a

program to produce maximum numbers of A’s with N keystrokes. That is to say, the input parameter is N

(no. of times you can press the keys), and the output is M (no. of A’s that you can produce).

Input:

The first line is N where N is the number of times key is pressed.

Output:

Print maximum number of As. Print -1, if N is greater than 75.

Constraints:

1 ≤ N ≤ 75

Example:

Input:

3

Output:

3

Explanation: Type 3 As by pressing Key 1 3 times.

Input:

7

Output:

9

Explanation:

Key 1 – print A, buffer – A

Key 2 – print A, buffer – AA

Key 3 – print A, buffer – AAA

Key 4 – select, buffer – AAA

Key 1 – copy, buffer – AAA

Key 1 – paste, buffer – AAAAAA

Key 1 – paste, buffer – AAAAAAAAA

****************************