Editorial for TLE '17 Contest 7 P1 - Stargazing


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: leonchen0613

Use two arrays to keep track of the X and Y coordinates for every planet. Let the first planet be located at the origin (0, 0). For each other planet, calculate its X and Y coordinates relative to the first planet, using the X and Y coordinates of a previously located planet:

\displaystyle \begin{align*}
x[i] &= x[P_i] + X_i \\
y[i] &= y[P_i] + Y_i
\end{align*}

After that, there are two main ways to count the number of distinct pairs of coordinates:

  1. Insert all the pairs of coordinates into a set. The size of the set will be your answer. Time Complexity: \mathcal O(N \log N)

  2. For each planet, loop through all previous planets to check if their coordinates match. If that new planet is unique so far, increment your answer by one. Time Complexity: \mathcal O(N^2)


Comments

There are no comments at the moment.