ICPC 2020 - O. Which Planet is This?!

#include <bits/stdc++.h>
using namespace std;

namespace {

const long long CIRCLE = 3600000;
const long long START_TOKEN = -1;
const long long SEP_TOKEN = -2;
const long long END_TOKEN = -3;
const long long LAT_SHIFT = 1000000;
const long long GAP_BASE = 4000000;

long long parse_scaled(const string& s) {
    int pos = 0;
    int sign = 1;
    if (s[pos] == '-') {
        sign = -1;
        ++pos;
    } else if (s[pos] == '+') {
        ++pos;
    }

    long long whole = 0;
    while (pos < int(s.size()) && s[pos] != '.') {
        whole = whole * 10 + (s[pos] - '0');
        ++pos;
    }

    long long frac = 0;
    int digits = 0;
    if (pos < int(s.size()) && s[pos] == '.') {
        ++pos;
        while (pos < int(s.size()) && digits < 4) {
            frac = frac * 10 + (s[pos] - '0');
            ++digits;
            ++pos;
        }
        while (digits < 4) {
            frac *= 10;
            ++digits;
        }
    }

    return sign * (whole * 10000 + frac);
}

vector<long long> build_sequence(const vector<pair<long long, long long>>& input_points) {
    vector<pair<long long, long long>> points = input_points;
    sort(points.begin(), points.end());

    vector<pair<long long, vector<long long>>> buckets;
    for (int i = 0; i < int(points.size()); ) {
        int j = i;
        vector<long long> latitudes;
        while (j < int(points.size()) && points[j].first == points[i].first) {
            latitudes.push_back(points[j].second);
            ++j;
        }
        buckets.push_back({points[i].first, move(latitudes)});
        i = j;
    }

    vector<long long> sequence;
    sequence.reserve(points.size() * 2 + buckets.size() * 3);
    int m = int(buckets.size());
    for (int i = 0; i < m; ++i) {
        long long current_lon = buckets[i].first;
        long long next_lon = buckets[(i + 1) % m].first;
        long long gap = (next_lon - current_lon + CIRCLE) % CIRCLE;
        if (gap == 0) {
            gap = CIRCLE;
        }

        sequence.push_back(START_TOKEN);
        for (long long lat : buckets[i].second) {
            sequence.push_back(lat + LAT_SHIFT);
        }
        sequence.push_back(SEP_TOKEN);
        sequence.push_back(GAP_BASE + gap);
        sequence.push_back(END_TOKEN);
    }
    return sequence;
}

bool is_cyclic_shift(const vector<long long>& a, const vector<long long>& b) {
    if (a.size() != b.size()) {
        return false;
    }
    int n = int(b.size());
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && b[i] != b[j]) {
            j = pi[j - 1];
        }
        if (b[i] == b[j]) {
            ++j;
        }
        pi[i] = j;
    }

    int matched = 0;
    for (int i = 0; i < 2 * int(a.size()); ++i) {
        long long token = a[i % a.size()];
        while (matched > 0 && token != b[matched]) {
            matched = pi[matched - 1];
        }
        if (token == b[matched]) {
            ++matched;
        }
        if (matched == n) {
            int start = i - n + 1;
            if (start < int(a.size())) {
                return true;
            }
            matched = pi[matched - 1];
        }
    }
    return false;
}

void solve() {
    int n;
    cin >> n;

    vector<pair<long long, long long>> first(n), second(n);
    for (int i = 0; i < n; ++i) {
        string lat_str, lon_str;
        cin >> lat_str >> lon_str;
        long long lat = parse_scaled(lat_str);
        long long lon = parse_scaled(lon_str);
        if (lon < 0) {
            lon += CIRCLE;
        }
        first[i] = {lon, lat};
    }
    for (int i = 0; i < n; ++i) {
        string lat_str, lon_str;
        cin >> lat_str >> lon_str;
        long long lat = parse_scaled(lat_str);
        long long lon = parse_scaled(lon_str);
        if (lon < 0) {
            lon += CIRCLE;
        }
        second[i] = {lon, lat};
    }

    vector<long long> seq_first = build_sequence(first);
    vector<long long> seq_second = build_sequence(second);
    cout << (is_cyclic_shift(seq_first, seq_second) ? "Same" : "Different") << '\n';
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}

\title{ICPC World Finals 2020\\O. Which Planet is This?!}
\author{}
\date{}

\begin{document}
\maketitle

\section*{Problem Summary}

Each map is a set of points on a sphere, described by latitude and longitude. Two maps describe the same
planet exactly when one can be obtained from the other by adding one constant angle to every longitude,
while keeping all latitudes unchanged.

We must test this for up to $400\,000$ points, so the solution has to be almost linear after sorting.

\section*{Key Observations}

\begin{itemize}[leftmargin=*]
    \item Points with the same longitude always stay together under a rotation around the axis. Therefore it is
    natural to compress the map into \emph{longitude buckets}.
    \item For one fixed longitude bucket, the only information that matters is:
    \begin{itemize}[leftmargin=*]
        \item the sorted list of latitudes in that bucket,
        \item the angular gap to the next occupied longitude.
    \end{itemize}
    \item After sorting the occupied longitudes around the circle, a global rotation only changes where the
    circular order starts. So two maps are the same iff their bucket descriptions are equal up to a cyclic
    shift.
    \item Cyclic-shift testing can be done with a linear-time string-matching algorithm such as KMP once we
    encode the bucket descriptions into a token sequence.
\end{itemize}

\section*{Algorithm}

\begin{enumerate}[leftmargin=*]
    \item Parse all coordinates exactly as integers scaled by $10^4$.
    Normalize longitudes into $[0,360 \cdot 10^4)$.
    \item For each map:
    \begin{itemize}[leftmargin=*]
        \item sort all points by longitude, then by latitude;
        \item group equal longitudes into one bucket;
        \item for each bucket, append to a token sequence:
        \[
            \texttt{START},\ \text{all latitudes},\ \texttt{SEP},\ \text{gap to next bucket},\ \texttt{END}.
        \]
    \end{itemize}
    Distinct sentinel tokens ensure that a match can only start at a bucket boundary.
    \item Let the two token sequences be $A$ and $B$.
    Use KMP to test whether $B$ appears in $A+A$ with starting position less than $|A|$.
    \item Output \texttt{Same} iff such a match exists.
\end{enumerate}

\section*{Correctness Proof}

We prove that the algorithm returns the correct answer.

\paragraph{Lemma 1.}
If two maps differ by a rotation around the axis, then after sorting their occupied longitudes in circular
order, the sequence of longitude buckets is identical up to a cyclic shift.

\paragraph{Proof.}
Adding a constant angle to every longitude preserves:
\begin{itemize}[leftmargin=*]
    \item which points share a longitude,
    \item the sorted list of latitudes inside each shared longitude,
    \item the circular order of the occupied longitudes,
    \item the gap between consecutive occupied longitudes.
\end{itemize}
Only the starting position on the circle changes, so the bucket sequence changes by a cyclic shift and
nothing else. \qed

\paragraph{Lemma 2.}
If the bucket sequences of two maps are identical up to a cyclic shift, then the two maps differ by a
rotation around the axis.

\paragraph{Proof.}
Take the cyclic shift that aligns the first bucket of the first map with the matching bucket of the second.
Because the gap to the next bucket is part of the encoded data, all later occupied longitudes are forced to
line up as well after applying that same rotation. Since each matched bucket also contains exactly the same
sorted list of latitudes, every point of the first map is sent to a point of the second map, and vice versa.
Therefore the maps differ by one global longitude shift. \qed

\paragraph{Lemma 3.}
The token sequences produced by the algorithm are equal up to a cyclic shift exactly when the bucket
sequences are equal up to a cyclic shift.

\paragraph{Proof.}
Each bucket is encoded as
\[
    \texttt{START},\ \text{latitudes},\ \texttt{SEP},\ \text{gap},\ \texttt{END},
\]
with sentinel tokens that never occur as latitude or gap values. Hence the encoding is unambiguous and
preserves bucket boundaries. A cyclic shift of buckets is therefore exactly a cyclic shift of the token
sequence, and conversely any full-sequence match must start at a \texttt{START} token, so it corresponds to
whole buckets. \qed

\paragraph{Lemma 4.}
The KMP step returns true exactly when the two token sequences are equal up to a cyclic shift.

\paragraph{Proof.}
Searching for $B$ inside $A+A$ is the standard reduction from cyclic-shift matching to ordinary substring
matching. Restricting the start position to be less than $|A|$ ensures that we only consider one full wrap
around the circle. Since KMP finds exactly all occurrences of $B$ in linear time, the result is correct. \qed

\paragraph{Theorem.}
The algorithm outputs the correct answer for every valid input.

\paragraph{Proof.}
By Lemma 1, equal maps under rotation must produce bucket sequences that differ only by a cyclic shift.
By Lemma 2, any such cyclic shift really corresponds to a valid rotation. Lemmas 3 and 4 show that the
algorithm detects exactly this condition, so it outputs \texttt{Same} exactly for pairs of maps describing the
same planet. \qed

\section*{Complexity Analysis}

Sorting dominates the running time: $O(n \log n)$.
Building the token sequences and running KMP are both linear in the number of points.
The memory usage is $O(n)$.

\section*{Implementation Notes}

\begin{itemize}[leftmargin=*]
    \item Parsing coordinates as scaled integers avoids floating-point comparison issues completely.
    \item A bucket containing all points is legal; in that case the gap to itself is stored as the full circle.
    \item Negative longitudes are normalized by adding $360 \cdot 10^4$.
\end{itemize}

\end{document}