A matrix of size (m, n) is given, along with paint brush of size (x, y). The matrix contains few blocked cells, at which paint brush can't be applied. The task is to check if it is possible to paint submatrix of size (a, b) within (m, n) or not, ensuring the constraints.

Airport has m runways of length n units.

The rules of game are as follows:

• One can start at any runway.

• One can switch from ith runway to jth runway if (i, j) are coprime.

• It is compulsory to switch between runway after every 1 unit.

• One has to reach end of runway.

Find number of ways in which this can be achieved. As answer could be large, print it modulo 1000000007.

1<=n<=1000000000

1<=m<=10

Plz help me in this question.

Each test file starts with an integer ‘t’ — the number of testcases.

In each of the next ‘t’ lines, you are given a string of ‘n’ characters [ either ‘(‘ or ’)’ or ‘*’ ]. Your task is to find the number of distinct balanced parentheses expressions you can make by replacing the ‘*’ with either ‘(‘ or ‘)’ or removing the ‘*’

Note : You have to replace each ‘*’ with one of ‘(‘ or ‘)’ or remove it. If removed, assume the string has reduced by 1 character.

Duplicate strings are not allowed. The final expressions to be counted have to be distinct As the answer may be large, please output it modulo 1000000007 (10^9+7)

Output one integer per line corresponding to each testcase. Constraints :

1 <= t <= 20

1 <= n <= 100

0 <= Number of ‘*’ in the input string <= min(n,10)

Sample Input:

2

(*(*)*)

((**)*

Sample Output

5

9

Explanation

The five possible valid solutions are for the first input are :

((()))

()(())

()()()

(())()

(())

The nine possible valid solutions are for the second input are :

(((())))

(()(()))

(()()())

(()())

((()))

()(())

()()()

()()

(())

Given a matrix of n*n. Each cell contain 0, 1, -1.

0 denotes there is no diamond but there is a path. 1 denotes there is diamond at that location with a path -1 denotes that the path is blocked.

Now you have start from 0,0 and reach to last cell & then return back to 0,0 collecting maximum no of diamonds. While going to last cell you can move only right and down. While returning back you can move only left and up.

You are given a list of edges in a graph and for each pair of vertices that are connected by an edge, there are two edges between them, one curved edge and one straight edge i.e. the tuple (x, y, w1, w2) means that between vertices x and y, there is a straight edge with weight w1 and a curved edge with weight w2. You are given two vertices a and b and you have to go from a to b through a series of edges such that in the entire path you can use at most 1 curved edge.

Your task is to find the shortest path from a to b satisfying the above condition.

Given N objects numbered from 1 to N out of which all are of the same weights except only one object which is not known beforehand.

We are also given Q comparisons, in each of which an equal number of objects are placed on both sides of a balance scale, and we are told the heavier side.

The task is to find the inconsistently weighted object or determine if the data is not sufficient enough.

What can be minimum comparison strategy used over here?

Given a length l, find the angle and dimensions of the 4 sided quadrilateral formed having maximum area (this quadrilateral is not a square)?

Can someone provide me segment tree implementation of:

Range update : Add x to range

Finding frequency of a constant in range

I know of solution in sqrt decomposition exist, but I wanted in terms of segment tree (maybe lazy propagation or policy based data structures)?

Hi, I need to form test cases for a program having 2 parameters, but it should be blackbox and must find all possible exceptions (such as division by 0, etc). Could someone provide me some resource or algo?

x/(x+y-5)

(x, y) = (1, 4) is one test case generated

Provide me way to generate test cases (obviously it should be less).

Find if two people in a family tree are blood-related. I can't get what the question is and how to solve it.

Can anybody provide solution to this?

Link

If I want 1/i for 1<=i<=5000000, i.e. inv[i]

inv[1] = 1;
for (int i=2; i<p; ++i)
	inv[i] = (p - (p/i) * inv[p%i] % p) % p;

I used this but it times out. So I wanted a way for this.

Besides that, if I use fact[i-1]*invfact[i] : would that solve? It is not giving me correct answer so plz tell me what is wrong over here?

For serialising and deserialising a binary tree( or a n-ary tree ) only preorder traversal with # for Null is used in the given Link but I think both inorder and preorder are required to construct tree.

Please tell me what is that I am missing?

Q1).

Given isosceles right angled triangle, find the radius of the smaller circle.

Q2).

Given a rectangle ABCD with length l and breadth b, it is folded along diagonal BD. i.e. A is joined to C. Find the length of the line segment EF

You have a set of N objects. Each of these objects have certain properties associated with them. A property is represented by a (key, value) pair. For example, assume you have the following two objects.

Tower: { (height, 100), (weight, 50), (xposition, 25), (yposition, 36) }

Tree: { (area, 100), (noofleaves, 500), (height, 25), (yposition, 36) }

Each object you have, will have at most 4 properties. An object will have at least 1 property. Note, from the two objects above, that it is not necessary for key in the properties to be same for all the objects. Also, it is not necessary for the key to be different. Now, given N such objects, you wish to answer M queries. Each query is represented by a set of properties (again, at most 4 properties, and at least 1 property). The answer for the query is the number of objects in the set, that have all the given properties. Two properties are considered equal iff both the key and the value match. For example, if you have the above two objects, then the answer for the following queries is

Query: { (height, 100), (yposition, 36) }

Answer: 1 // matches Tower, but not Tree

Query: { (yposition, 36) }

Answer: 2 // matches both Tower and Tree

Query: { (height, 100), (noofleaves, 500) }

Answer: 0 // neither Tower, not Tree satisfy both properties

Input:

The first line of input contains N and M. This is followed by the description of the N objects. The description of the i-th object will start by a number k, which is the number of properties associated with the object. The next k lines contain two space separated strings – the property key and the property value. Note that the property value is not necessarily an integer (although this is so for the example above). This is followed by the description of M queries. The format of a query will be exactly same to that of the objects. Check the Sample Input for clarification. One test file will contain only one test case. A single test case may contain several queries.

Output:

Print M lines. Each line must be the answer of the respective query.

Constraints:

1 <= N <= 10000

1 <= M <= 100000

1 <= k <= 4

Sample Input 2 3

4

height 100a

weight 50b

xposition 25a

yposition 36b

4

area 100a

noofleaves 500

height 25

yposition 36b

3

weight 80

xposition 25a

yposition 36b

1

yposition 36b

2

xposition 25a

yposition 36b

Sample Output:

0

2

1

Given n boxes of different weights and m machines of different weight carrying capacity. Find the minimum time required to move all boxes. Each machine take 1 minute to carry one time.

Can somebody suggest a approach.

Link : In the given link it says if the word is in min heap, then also you can increase the count but it is slightly confusing. Can somebody suggest an approach for this or another way for updation if the word already exists in min_heap.

I am sharing image of question as link is not working:

Img1

Img2

Please someone help me in his question.

I had a doubt how this solution clears large dataset of Kickstart Round B as it is (N*M*K) which is dp entries and each entry is computed in approx (N*M). Lastly T test cases too and each of the variable, that is, N, M, K, T is in range 1,..,100.

Link of solution

Link Of Problem

Am I making an error in understanding or test cases were weak as I tried locally on large dataset and it worked within 2 mins.

You are given a string of ‘n’ characters where n is even. The string only consist of 6 type of characters: (){}[]. The task is to form a well formed expression. A well formed expression consist of proper nesting of braces and their is no priority between the braces like [ > } > ). You can edit any bracket and change it to remaining types for accomplishing the task.

Example 

A. "(){}" is valid 

B. "({[]})” is valid 

C. “((})” is invalid

You are given a number of points on the XY-plane, [(x0,y0),(x1,y1),(x2,y2),...]. A point (xi,yi) is dominant to another point (xj,yj) iff xi>xj and yi>yj. Calculate all pairs of points such that one dominates the other.

A time complexity less then O(n*n) was required.

In a city, the rents of apartments change every month according to the demand. If there are x apartments in the city, all the rents for 12 months are given for each apartment and also x one time relocation prices are given(Applies when you move from one apartment to other in the first month).

If a person comes to this city and wants to rent an apartment, optimize the rental cost for whole year by generating a month wise plan on where he must stay each month?

Given a set of restaurants (the number being quite large) and its geographical location(x,y) , you are allowed to do an significant amount of pre-processing on it. Now suppose there are x customers located at position (s,t), design an efficient algorithm to find the k nearest restaurants to these customers.

Problem: Write a method that, given a digit 'd' and number of its occurences 'k', returns a range which has that many occurrences of d. More precisely, return a lower and upper bound of this number N.

Example:

input: d=4, k=1

output {4, 13}

Range: 4-14

input: d=4, k=0

output {1, 3} Range: 1-3

Can anybody help me in this?

Hi,

Given a max-heap represented as an array, return the kth largest element without modifying the heap. Pleaae provide an algorithm which is most optimised. There are few answers on net but I guess most are following a particular structure of heap, so I want a correct answer.