How to solve CO92MATR(Chef Restores a Matrix) form Cookoff 92(March Cook-off 2018)

general
, , ,
1

I spend like 20 minutes figuring out how to solve it. But ended up solving only first(CO92JUDG) and second(CO92SUBW) problem form Div2. Can anyone explain intuition as well as step by step guide to solve this problem.

1 Like
2

Greedy Approach

Step 1: Restore the elements of first column and first row, for first row or first column it can be simply done as follows

let’s do it for first row

let Var = 1

 for( i=0; i<n; i++)

    if(a[i]==-1) set a[i] = Var; 
    else
    set Var = a[i]

similarly do it for first column.

Step 2: Check if first row and first column element are satisfying given property or not, if not print answer “-1”

Step 3: Now restore remaining elements as, a[i][j] = max(a[i-1][j],a[i][j-1])
and keep checking the value of (a[i][j]<a[i-1][j] || a[i][j]<a[i][j-1]) if it becomes 1 print answer “-1”

Step 4: Print the matrix

3 Likes
3

Greedy if an element is -1 then its values should be max(up,left) if those neighbours exist. this ensures that it is the best value of it for the next phase.Now after filling it up check whether the developed matrix is non decreasing
(Note: we didnt check while substituting the value for unkown value we just replaced it with best possible value assuming that the array was going to satisfying non decreasing property.)

1 Like
4

Simple Nested Loop, insert max of upper and left col and row res +1. the only case you should aware of is of what if all the index are -1, ie if you have to fill the complete matrix yourself.

Here is my solution, This can be used as reference.
https://www.codechef.com/viewsolution/17897343

1 Like
5

Can somebody help my answer prints the same but its showing wrong https://hastebin.com/irulunalin.cpp