You are not logged in. Please login at www.codechef.com to post your questions!

×

ROTPTS - Editorial

Problem Link

Practice

Contest

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.

  1. Output the result of performing all operators in order from $l$ to $r$.
  2. 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 :

  1. Find the product of matrices in range $l$ to $r$
  2. 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:

  1. Rotation of $(x, y)$ around origin by 90 twice.
  2. Rotation of $(a_1 + b_1, b_1 - a_1)$ around origin by 90 once.
  3. 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)

  1. Angle = 0, (x, y) -> (x, y)
  2. Angle = 90, (x, y) -> (x+y, y-x)
  3. Angle = 180, (x, y) -> (-2x, -2y)
  4. 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))$

Solution Links

Setter's solution

Tester's solution

Editorialist's solution

This question is marked "community wiki".

asked 21 Dec '17, 12:23

likecs's gravatar image

6★likecs
3.7k2078
accept rate: 9%

edited 26 Dec '17, 01:39


Is sqrt(N) approach basically "let's use sqrt-decomposition instead of segment tree for range queries, and let's avoid using matrices directly but instead try to write down all possible configurations of matrix at given moment, and apply matrix of given block to our point each time instead of getting product of all matrices first", or it there some notably different ideas involved? This part of explanation is not very clear to me, and after looking at code for a minute or two I got lost in a bunch of if-statements :)

link

answered 26 Dec '17, 01:18

lebron's gravatar image

7★lebron
3.3k317
accept rate: 24%

1

Yes, the idea seems same. Basically what you described above. The approached mention by me of 2 coordinates basically does simulation of $3X3$ matrix in 2 parts, one of the normal $2X2$ matrix and the other of remaining part. Since, I solved it this way, i included it in the editorial. Though after seeing the author's solution, I think his was more intuitive one and used by almost all the participants.

(26 Dec '17, 01:23) likecs6★

"The problem can be viewed as 2 independent coordinates systems undergoing rotation. The first is the rotation of given point by angle θθ about the origin and the other is combined effect of the rotation of "changed" operators around the origin."

can you please explain this a little more! I am weak in maths so, didn't able to understand it properly.

link

answered 26 Dec '17, 14:02

pk301's gravatar image

3★pk301
62710
accept rate: 16%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,266
×2,536
×591
×278
×106
×72
×18
×17

question asked: 21 Dec '17, 12:23

question was seen: 2,125 times

last updated: 26 Dec '17, 14:02