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.