codechef co92matr

Question link:

The problem asked that, we have replace each -1 with +ve integers, such that all rows and columns are in non-decreasing order. So, i am taking a 2D array and taking the input. But, to go to each '-1' and comparing it with its neighbouring elements(which can be atmax 4), will require use of LOTS OF NESTED LOOPS. And adding to that we have to consider all the possible cases where -1 can be,like at the top or top-left or middle of the matrix.

Is there is any easier and compact approach to this problem ? 

Samrat De

Please Log in to answer

Note: Your answer should not be too short. Please wait a few seconds for the editor to load

Please make sure the answer is not too short

1 Answer

shubhgup 18:33, Mar 23
Shubham Gupta

Think about this approach:

Traverse the matrix in row wise manner...

Now ,when traversing the elements keep a check ,if the element just below and towards the right are in the sense that the increasing order is maintained other wise the arrangement is not possible...

consider this example...

1 2 2 3
1 -1 7 -1
6 -1 -1 -1
-1 -1 -1 -1



Now in 1 st row traversal ,you traverse 1 ,2,2, each case you compare it with the bottom and right member ...the  sequence is maintained.

Similarly do it with the 2nd row and all the rows;

if at any time ,you visit a -1.. compare the values of the element just above -1 and just towards the left of it....whatever be the greater of them it in the index containing -1(because that is the least value you can store in it..if the sequene is to be maintained....

and then again perform a check of the sequence ... i.e comparing it with the right and bottom element.... do the same and avoid check for the corner elements...

Hope this would be helpful.. :)



Please make sure the answer is not too short
No Comments yet