Problem Link
Setter: Trung Nguyen
Tester: Hasan Jaddouh
Editorialist: Bhuvnesh Jain
Difficulty
MEDIUM
Prerequisites
Matrix Multiplication, Segment Trees, Sqrt Decomposition, Rotation Matrix
Problem
There are N operators in a plane which rotate a given point P around the point i and angle a_i. We need to process 2 types of queries.
- Output the result of performing all operators in order from l to r.
- Update a given operator.
The final coordinates of the points should be given modulo {10}^{9}+7.
Explanation
To rotate a given point about origin by \theta, we need the rotation matrix as follows:
\left({\begin{array}{cc} \cos{\theta} & -\sin{\theta}\\ \sin{\theta} & \cos{\theta} \end{array}}\right) *
\left({\begin{array}{c} x\\y \end{array}}\right) =
\left({\begin{array}{c} x'\\y' \end{array}}\right).
To see more details regarding the above matrix, refer to this wikipedia article.
Now, to rotate the above matrix about another point, P, by same angle \theta, we first shift the origin to that point, P, and after rotation shift the origin back to the original one. This can be written as equations:
x' = \cos{\theta} * (x - P.x) - \sin{\theta} * (y - P.y) + P.x
y' = \sin{\theta} * (x - P.x) + \cos{\theta} * (y - P.y) + P.y
This can also be written as rotation matrix of size 3 X 3 as follows:
\left({\begin{array}{ccc} \cos{\theta} & -\sin{\theta} & {(1-\cos{\theta})*P.x + \sin{\theta}*P.y}\\ \sin{\theta} & \cos{\theta} & {(1-\cos{\theta})*P.y - \sin{\theta}*P.x}\\0 & 0 & 1 \end{array}}\right) *
\left({\begin{array}{c} x\\y\\1 \end{array}}\right) =
\left({\begin{array}{c} x'\\y'\\1 \end{array}}\right).
To apply the operators one after the other, we first apply the first operator, get the new point and then another operator and so on. Thus, it basically means multiplying the corresponding rotation matrices and then applying the operator.
Thus, now the problem reduces to the following :
- Find the product of matrices in range l to r
- Update a given matrix
This problem of range query and point update can be easily handled with segment trees keeping a Matrix in each node. For more details on segment trees, one can refer to this. Each update will be handled in {d}^3 * \log{N} and each query will be handled in {d}^{3} * \log{N}, where d = 3, dimension of rotation matrix.
Editorialist Approach
Problems involving range queries and point updates are mostly solved with Segment Trees or Sqrt Decomposition. Sqrt Decomposition is useful when we can precompute some useful information in a block in such a way that the whole block can be queried efficiently.
The problem can be viewed as 2 independent coordinates systems undergoing rotation. The first is the rotation of given point by angle \theta about the origin and the other is combined effect of the rotation of “changed” operators around the origin.
To understand this, consider the initial point is (x, y) and we apply to operators (a_1, b_1, 90) and (a_2, b_2, 90), in order. Then the resulting point will be (-y + (a_1 + b_1), x + (b_1 - a_1)) and finally (-x - (b_1 - a_1) + (a_2 + b_2), -y + (a_1 + b_1) + (b_2 - a_2)).
This can be seen as:
- Rotation of (x, y) around origin by 90 twice.
- Rotation of (a_1 + b_1, b_1 - a_1) around origin by 90 once.
- No Rotation of (a_2 + b_2, b_2 - a_2) around origin.
The modified operators based on the angle are : (This is derived from the above 2 equation written above)
- Angle = 0, (x, y) → (x, y)
- Angle = 90, (x, y) → (x+y, y-x)
- Angle = 180, (x, y) → (-2x, -2y)
- Angle = 270, (x, y) → (x-y, x+y)
For a given a point, we can easily simulate the above process keeping the rotation effect of given point and of the “changed” operators separately. Thus, block queries, the idea behind splitting the array into blocks can be handled efficiently.
Thus, we can simply solve the problem using sqrt decomposition. For details, refer to the editorialist solution below.
Basic Tip: Sometimes deciding whether to use segment trees or sqrt decomposition can be difficult. According to me, I like to use Sqrt decomposition mostly when we apply some operation in a range in order as sometimes the order in which segment trees nodes can be combined becomes difficult to handle. Still, the choice depends on the reader and problem.
A final note, don’t forget to handle all operations in modulo field, i.e. modulo {10}^{9} + 7.
Time Complexity
O({d}^{3} * N * \log{N}), per test case, where d = 3, dimension of rotation matrix.
or O(N * sqrt(N)), per test case.
Space Complexity
O({d}^{2} * N)
or O(N * sqrt(N))
