I gave a hiring contest yesterday. These are 2 questions i couldn't solve which I think were good problems. If you have any approach to solve these questions within given constraints, Please help.

Q1. Given an N*M matrix with k number of black cells in it. You have to find number of distinct paths from top left (1*1) corner to bottom right corner (n*m) such that each path has atleast one black cell in it. From position (x,y) you can go to (x+1,y) or (x,y+1) only. Positions of all k black cells in matrix are given in input.

N -> number of rows, m -> number of columns, k -> number of black cells

1<=N,M<=10^5, 0<=k<=10^3

Q2. Given a string of parenthesis containing either ')' or '(', you can perform three operations as follows : insert : enter any parenthesis anywhere in string remove : remove any parenthesis from anywhere in string replace : toggle the type of parethesis Now you have to balance the given parenthesis string with minimum number of operations. Output the minimum number of operations used to balance the string.

size -> size of string, 1<=size<=10^6

Note : if P,Q both are balanced then PQ is also balanced and (P) is also balanced.

when and where did this contest happen??

Title says 6th march, 19. Where -> Hackerrank.

For the first question, it is quite a tough dp problem. But I think that you can solve it by using 2 dp states:

I'll leave you to figure out the transitions.

Q1. Suppose we want to go freely, as if there is no black cell or if black cells are not important, from an arbitrary position (

x,y) to another position (p,q) withx≤pandy≤q. Then the number of distinct paths is . Now consider the original problem. The path from (1,1) to (N,M) can be broken into 2 stages: going from (1,1) to some black cell without encountering any other black cells before, and then going from that black cell freely to (N,M). Denotef[k],k= 1, 2, ...,Kas the number of distinct paths from (1,1) to the black cellkwithout encountering any other black cells,p[j,k],j= 1, 2, ...,Kas the number of distinct paths going freely from black celljtok. Sort the black cells increasingly by their rows and if two cells are in the same row, by columns. Thenf[k] can be computed inO(K^{2}):r_{1},c_{1}are the row and column of the first black cell in the sorted list.k> 1.Having

f[k] computed, the rest is simply summing up for allk= 1, 2, ...,Kthe number of distinct paths going from (1,1) tokfirst, then fromkto (N,M).Hey thank you so much, I now totally understand how to solve this. However in your comment, without considering black cells at all total count of paths from (x,y) to (p,q) given first point occurs first will be (p-x+q-y)C(p-x). I think this is a typo. Thanks for the help.

Q2. The first step is to remove all the parentheses that are part of a balanced string, which can be done in

O(N) whereNis the size of the string. We end up with one of the 2 following cases:Case 1: suppose there are

N= 2kparentheses. Toggle the first or the lastkparentheses to get a balanced string. The answer isk. IfN= 2k+ 1, the answer isk+ 1.Case 2: solve each part of the two parts in a similar way to case 1.

Thank you so much.