 # CHEFBM - Editorial

Author: Dmytro Berezin
Tester: Sergey Kulik
Editorialist: Lalit Kundu

EASY

### PROBLEM:

There is a N * M matrix, where A[i][j] is j for all i,j. There are P queries of form (i,j), where we do A[i][j]++.
For each row i,
if there exists a j, such that A[i][j] > A[i][j+1], print -1.
else print sum[i=M to 2]{A[i][j]-A[i][j-1]}.
1 ≤ N,M,P ≤ 105

### QUICK EXPLANATION:

For each i, we also keep note of values (i,j-1) and (i,j+1), if (i,j) is given in input. Traversing over the queries, we can see which values change and print answer accordingly.

### EXPLANATION:

We have to process for each i independently. Let’s say for an i, we have NN queries of form (j,k) which means: increase A[i][j] by k. For such a query we also store (j-1,0) and (j+1,0), because these two indexes are also effected.
If there were no changes, our answer will be m-1. Now, we traverse over all queries in increasing order of j and look at index j+1, if the value at j+1 is less than value at j, we know that answer is -1 for this row. Else, we add the (A[i][j+1]-A[i][j]) to the answer and subtract -1 from the answer. We can use map to perform this process efficiently. See (setter/tester/editorialist)'s solution for implementation details.

### AUTHOR’S AND TESTER’S SOLUTIONS:

3 Likes

" For such a query we also store (j-1,0) and (j+1,0), because these two indexes are also effected."

Can anyone expand on this line? Where do we store that?

for which test case does this code fails
http://www.codechef.com/viewsolution/3898907 what is wrong in it

for input

``````1 4 5
1 3
1 2
1 2
1 1
1 1
``````

it returns `-1`

initial matrix

``````   *
**
***
****
``````

`````` ***
****
****
****
``````

so the result should be 1…

2 Likes

can you help me as well http://www.codechef.com/viewsolution/3900012

@ashish424 see this…http://ideone.com/pLUZzO …u r printing extra numbers!!!

2 Likes

I tried many times but always got WA . Both the above use case is correct for me .
If any one can give me test case that caused WA , it will be a great help.

http://www.codechef.com/viewsolution/3883304

Thanks
rajesh

try this case…

``````4 1 1
1 1
``````

ans should be:-

``````0
0
0
0
``````

urs is…

``````1
0
0
0``````

Since the explanation states “We can use map to perform this process efficiently”, I assume it means that we have to add an entry in our map which shows that (j-1) and (j+1) are not increased. Or more plainly, j+1 and j-1 are increased by 0.

http://www.codechef.com/viewsolution/3857701
Can someone please check if this is giving right answers on your test cases? It can calculate results even if input of a row changes after changes in other rows, for example

4 4 6

3 2

2 3

3 2

2 4

1 2

32

Can the approach be this:
storing count of the incremented index(the coloumn), adding to it the index values. Sort this, if its same as the initial string, ans will be m-1 otherwise -1. For eg.

``````4 4 6
2 2
3 2
3 2
4 3
4 4
4 3
``````

then for the third row, count(this array will be 1-indexed) will be 0 2 0 0, adding the index values to it, it will be 1 4 3 4. Now if i’ll sort this, i’ll not get the same array and hence answer should be -1. I implemented this here: http://ideone.com/LBmHGD and its most obvious to give TLE. BUt is there any way I can optimize this??

i corrected that …but it is still showing wrong answer
http://www.codechef.com/viewsolution/3900322

Why does this ans give TLE:
http://www.codechef.com/viewsolution/3842031

Where shall i get the input file and output file?

sorting is a very expensive operation. Initial cost is M-1. Consider this. If first element is increased, cost goes down by 1. If last element is increased, cost goes up by 1. If any other element is increased, as long as it is smaller than next, cost is unaffected. Hope you get the rest of idea, like checking if it was previously smaller and now larger and all that too.