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

×

XYPIZQ - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Sajal Agrawal
Tester: Xiuhan Wang
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Properties of triangles and Case-based Analysis.

PROBLEM:

Consider two Intersecting Lines interesecting at point $A_0$ having an angle $\theta < 90°$ and marking $N$ points $A_1, A_2 \ldots A_N$ on lower line and $B_1, B_2 \ldots B_N$ on upper line. Now join $A_i$ with $B_{i+1}$ and $B_i$ with $A_{i+1}$ for all $1 \leq i \leq N-1$. Also join $A_N$ and $B_N$.

Here, all these $2*N-1$ are equal in length and are also equal to segments $A_0A_1$ and $A_0B_1$.

The problem requires to find out angle formed by two segments at a specific point. Queries are of four types. Given $N$, $type$ and three integers $x$, $y$ and $z$.

  • Find angle $A_xA_yB_z$ if the query is of the first type.
  • Find angle $A_xB_yA_z$ if the query is of the second type.
  • Find angle $A_xB_yB_z$ if the query is of the third type.
  • Find angle $B_xB_yB_z$ if the query is of the fourth type.

SUPER QUICK EXPLANATION

  • For a given $N$, we can use Triangle sum property and Similarity of trinagles to systematically find out that $\theta = \pi/(2*N+1)$. After this, $\theta$ can be substituted to find the value of required angle.
  • It can also be seen that the angles generated on both lines are following the same pattern. Specifically, Angles formed at point $A_i$ are same as angles formed at point $B_i$. This way, answer to fourth query is exactly same as answer to second query, while answer to third query for triplet $(x,y,z)$ is same as answer to first query for triplet $(z,y,x)$.
  • When $y > 0$, Angle $A_{i-1}A_iB_{i-1}$ is $\pi*(i-1)/(2*N+1)$ Angle $B_{i-1}A_iB_{i+1} = \pi*(2*N+1-2*i)/(2*N+1)$ and Angle $B_{i+1}A_iA_{i+1} = \pi*(i+1)/(2*N+1)$
  • Corner case when $y = 0$, answer is $\theta = \pi/(2*N+1)$

EXPLANATION

Ignore queries for now, first focus on determining the angle $\theta$ between two lines.

Triangle properties used can be found below.

View Content

It can be seen that for a given $N$, Only one value of $\theta$ is valid. Let us try to find this value for say, $N = 4$, as shown in the image below.

alt text

In $\bigtriangleup A_0A_1B_2$, $\angle A_1A_0B_2 = \theta$ and we have $|A_0A_1| = |A_1B_2|$ which implies $\angle A_0B_2A_1 = \theta$. Now, $\angle A_0A_1B_2 = \pi-2*\theta$ which implies $\angle A_2A_1B_2 = 2*\theta$.

Consider $\bigtriangleup A_1B_2A_3$ now, where we have $\angle A_2A_1B_2 = 2*\theta$ and $|A_1B_2| = |A_3B_2|$, implying $\angle A_2A_3B_2 = 2*\theta$. Applying Angle sum property, we have $\angle A_1B_2A_3 = \pi-4*\theta$. Now, $\angle B_1B_2A_1 + \angle A_1B_2A_3 + \angle A_3B_2B_3 = \pi$ which implies $\theta+(\pi-4*\theta)+\angle A_3B_2B_3 = \pi$, giving $\angle A_3B_2B_3 = 3*\theta$. Once again we get $\angle A_3B_4B_3 = \angle A_3B_2B_3 = 3*\theta$.

Proceeding this way, we shall end up with $\angle A_3A_4B_4 = 4*\theta$ and $\angle A_3A_4B_3 = 3*\theta$ giving $\angle B_3A_4B_4 = \theta$. Also, we can find $\angle A_4B_3B_4 = \angle A_4B_4B_3 = 4*\theta$. Using angle sum property in $\bigtriangleup B_3B_4A_4$, we get $\theta = \pi/(2*N+1)$.

Now that we have found $\theta = \pi/(2*N+1)$, we can substitute this value to find out the answer for any query.

Corner case: Query 1 1 0 1 can be handled separately.

To answer queries, we need to notice the patter that $A_{i-1}A_iB_{i-1} = \pi*(i-1)/(2*N+1)$ and $B_{i-1}A_iB_{i+1} = \pi*(2*N+1-2*i)/(2*N+1)$ and $B_{i+1}A_iA_{i+1} = \pi*(i+1)/(2*N+1)$. We can form case based analysis to answer queries of first type.

The answer to queries of second and fourth type is same due to symmetry and answer to such queries is $\pi*(2*N+1-2*y)/(2*N+1)$.

It can be easily seen that answer to a query of the third type for triplet $(x, y, z)$ is same as the answer to a query of the first type for triplet $(z,y,x)$.

Time Complexity

Time complexity is $O(1)$ per test case.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution
Editorialist's solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 14 Jan, 16:10

taran_1407's gravatar image

6★taran_1407
3.9k2791
accept rate: 22%

edited 14 Jan, 19:35

admin's gravatar image

0★admin ♦♦
19.8k350498541


Thanks for such a great Editorial in the first place. I myself found it very difficult to explain it in such a lucid way! Kudos!

link

answered 14 Jan, 17:53

include_sajal's gravatar image

4★include_sajal
1716
accept rate: 0%

1

Glad the setter liked ;)

(14 Jan, 19:54) taran_14076★
1

Efforts never go unnoticed and you are already a celebrity on Codechef. Keep contributing. BOW!

(15 Jan, 06:12) include_sajal4★

Nice1! have to waste a lot of time due to that corner case :))

link

answered 14 Jan, 19:43

thesmartguy's gravatar image

4★thesmartguy
645
accept rate: 9%

link

answered 14 Jan, 23:29

jaggu1999's gravatar image

3★jaggu1999
11
accept rate: 0%

edited 14 Jan, 23:31

I would like to add a note that some languages (e.g. Lisp family, Perl 6) support rational number out of the box, thus the solution in Common Lisp can be as simple as

(defun xypizq (N q x y z)
  (cond ((= q 1) (if (= x z) (/ x (1+ (* N 2))) (- 1 (xypizq N 1 z y z))))
        ((= q 3) (xypizq N 1 z y x))
        (t (- 1 (/ (* y 2) (1+ (* N 2)))))))

(dotimes (tests (read))
  (let ((result (xypizq (read) (read) (read) (read) (read))))
    (format t "~a ~a~&" (numerator result) (denominator result))))

Or if one may find Perl 6 more readable (this one suffers TLE due to the lack of time multiplier though):

multi xypizq($N, 1, $x, $y, $z where $x == $z) { $x / ($N * 2 + 1) }
multi xypizq($N, 1, $x, $y, $z) { 1 - xypizq $N, 1, $z, $y, $z }
multi xypizq($N, 3, $x, $y, $z) { xypizq $N, 1, $z, $y, $x }
multi xypizq($N, $t, $x, $y, $z) { 1 - $y * 2 / ($N * 2 + 1) }
xypizq(|get.words>>.Int).nude.put for ^get
link

answered 15 Jan, 09:03

mcsinyx's gravatar image

2★mcsinyx
313
accept rate: 0%

link

answered 15 Jan, 23:47

saraswat000's gravatar image

3★saraswat000
1
accept rate: 0%

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:

×1,668
×1,184
×649
×109
×73
×51
×17

question asked: 14 Jan, 16:10

question was seen: 1,663 times

last updated: 15 Jan, 23:47