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.
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/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
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: LBmHGD - Online C++ Compiler & Debugging Tool - Ideone.com and its most obvious to give TLE. BUt is there any way I can optimize this??
I did this in pretty naive way…
stored all the queries in vector pairs…
sorted the vector pairs with first element increasing and corresponding second element decreasing…
for e.g if pairs are (1,2) (2,3) (2,1) (2,4)… the results of sorting would be (1,2) (2,4) (2,3) (2,1)…
then…
j=0;
for i from 1 to n:
if pair.at(j).first==i:
count all the occurrences of pair.at(j).second (since vectors are sorted, just increment j and keep checking
count all occurrences of next number and if the next number is 1 less than previous number that this count shouldn't be greater than count(previous number)+1
if its not 1 less than previous number than count shouldn't be more than 1
count all the occurrences of (i,m).. let this be k
count all the occurrences of (i,1).. lets this be f
if all the conditions above are satisfied answer is (m+k)-(f+1)
else its -1
else:
ans is m-1
</pre>
http://www.codechef.com/viewsolution/3885273
is working fine for every test cases, but I’m getting wrong answer. Can any one please tell me which test case is failing?
I used the following approach:
Store queries in struct A {int i,j;}
Sort A in increasing order of rows and corresponding decreasing order of columns
count=0
for i=1 to n {
if A[count].i!=i
print m-1
continue;
k=A[count].j;
if k!=m
ans=m-k-1, next=k+1;
else
ans=0, next=-1;
for j=k to 1 {
freq=0;
while(A[count].j==j && A[count].i==i)
count++,freq++;
temp=j+freq;
if(temp>next)
ans=-1;
break;
ans+=(next-temp);
next=temp;
}
print ans;
}
http://www.codechef.com/viewsolution/3904846 is my solution to the problem, I have tried all the test cases provided in the above answers and also the sample test case and it is working fine, I’m not able to figure out why my code is getting a WA.