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.
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
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.)
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.
Can somebody help my answer prints the same but its showing wrong https://hastebin.com/irulunalin.cpp