The problem can break down to simple case A: A. convert a row of size c elements to all zero using only operations a, b
which can further break down to substep B: B. for any two different value x, y in a row, use only operations a, b to convert to same value. Suppose x <= y, perform operation a on x until 2*x > y. Then if x == y, no more operation is needed; if x < y, perform operation b on current row 2*x-y times, now (x, y)->(x', y'), x'=y-x, y'=2y-2x; then perform operation a on x', now both value turns the same. Note that we focus on values instead of elements in the row, when we perform operation on a value, we perform the same operation on all elements in the row having such value. Now repeatly apply substep B on a row of size c elements, convert the least 2 different values to same value, until all values are the same. Then apply operation b until all values are zero. This way we can achieve A. For general case of r*c, just eliminate the rows one by one. ankur aggarwal 写道: > I've always wanted to feel the excitement in these interviews. I got a > chance, and I liked it. > > Here is the question: > > You are given a matrix: r rows, c cols. r x c matrix. > > Now they all have positive integers. Assume that the computer has no > overflow, it can store all possible integer values. > > Now there are only two operations you can perform on the matrix: > > a. Multiply one whole column (of size r elements) by 2 aij = aij * 2 > b. Decrement a whole row (of size c elements) by 1. aij = aij - 1 > > Now you are required to find out if it's possible with these > operations to convert this matrix into the O matrix. (one with all > zeroes in it.) > > If so, how do you solve it? Or when do you decide to terminate? > > give the algo.. > not the code. > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
