Help wanted for a problem
Difference between en1 and en2, changed 443 character(s)
Problem Statment↵
------------------↵

You're given a matrix of 
N$N$ rows and M$M$ columns, and Q$Q$ queries. $(1 <= N, M, Q <= 1000)  $↵

For each query 
$(x, y, c)$, you need to rotate clockwise the square child matrix whose upper left corner is $(x, y)$ and lower right corner is $(x + c &mdash; 1, y + c &mdash; 1).  ↵
Print the final matrix as res
+c-1, y+c-1)$.↵

Print the final matrix as result.↵

Sample↵
------------------↵

input: ↵

~~~~~↵
4 5 3↵
9 9 3 4 5↵
5 0 2 1 3↵
9 3 6 4 3↵
5 9 3 9 0↵
1 3 1↵
2 1 2↵
2 2 1↵
~~~~~↵

output: ↵

~~~~~↵
9 9 3 4 5↵
9 5 2 1 3↵
3 0 6 4 3↵
5 9 3 9 0↵
~~~~~↵

Obviously there is an $O(n^3)$ brute force algorithm which is not fast enough. Are there any solution faster than $O(n^3)$?↵

I guess the technique of dancing links may be usef
ult.↵

thanks :-)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English EarthMessenger 2022-10-17 17:13:22 443 (published)
en1 English EarthMessenger 2022-10-17 16:59:30 370 Initial revision (saved to drafts)