can someone figure out my mistake in this question.
solution link : CodeChef: Practical coding for everyone
It seems like this problem was having weak test case as I have seen a solution in which a vector was defined with size of n+3 and he was accessing this vector upto m. This clearly says that in test case difference between n and m are very small < 3.
You are updating a 2_D matrix inside the query loop.Now updating an 1_D array using slicing has a complexity of O(n), so in 2_D would take a time nearly of O(n*n). Already there are 10^6 queries, only statements of complexity of O(1) can be used inside that loop. Slicing has its own complexity hence giving TLE.
There are lot of statements in python that seem to be simple ie complexity O(1) but a lot of work is done on the inner side. Before using these fancy techniques one must always go through there complexities. You can check here
1 Like
You are updating a 2_D matrix inside the query loop.Now updating an 1_D array using slicing has a complexity of O(n), so in 2_D would take a time nearly of O(n*n). Already there are 10^6 queries, only statements of complexity of O(1) can be used inside that loop. Slicing has its own complexity hence giving TLE.
There are lot of statements in python that seem to be simple ie complexity O(1) but a lot of work is done on the inner side. Before using these fancy techniques one must always go through there complexities. You can check here
**Learned a lot from this problem and definitely it is a nice editorial.
Thanks for this amazing concept.**
I dont know what was wrong with my code i did multiple changes and optimization … but it showed wrong answer then i looked into your comment!!!
I am not sure wheather you found the mistake or not. but this is what it is
if they give rc matrix then we should create r+1c+1 matrix
in the editorial they said update [x1,y1] and [x2+1,y2+1] as +1 but you have made [x2][y2] as +1 . Similairly -1 also updated in one row above and one coloum before.
Is the 3rd matrix drawn in proof right? Shouldn’t it be like:
[
[ 0 0 0 0 ]
[ 0 1 0 -1]
[ 0 0 0 0 ]
[ 0 0 0 0 ]
]