ICPC 2021 - L. Where Am I?

#include <algorithm>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <utility>
#include <vector>

using namespace std;

namespace {

struct Coordinate {
    int x;
    int y;
};

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

    int dx, dy;
    cin >> dx >> dy;

    vector<string> raw(dy);
    for (int row = 0; row < dy; ++row) {
        cin >> raw[row];
    }

    vector<Coordinate> markers;
    for (int row = 0; row < dy; ++row) {
        int y = dy - row;
        for (int x = 1; x <= dx; ++x) {
            if (raw[row][x - 1] == 'X') {
                markers.push_back({x, y});
            }
        }
    }

    const int radius = max(dx - 1, dy - 1);
    const int side = 2 * radius + 1;
    const int sequence_length = side * side;
    const int word_count = (sequence_length + 63) / 64;

    vector<int> visit_time(side * side, -1);
    auto offset_index = [radius, side](int x, int y) {
        return (y + radius) * side + (x + radius);
    };

    int covered = 0;
    int x = 0;
    int y = 0;
    int time = 0;
    visit_time[offset_index(0, 0)] = 0;
    covered = 1;

    const int dir_x[4] = {0, 1, 0, -1};
    const int dir_y[4] = {1, 0, -1, 0};
    for (int step_length = 1, dir = 0; covered < sequence_length; ++step_length) {
        for (int repeat = 0; repeat < 2; ++repeat, dir = (dir + 1) % 4) {
            for (int step = 0; step < step_length; ++step) {
                x += dir_x[dir];
                y += dir_y[dir];
                ++time;
                if (-radius <= x && x <= radius && -radius <= y && y <= radius) {
                    visit_time[offset_index(x, y)] = time;
                    ++covered;
                    if (covered == sequence_length) {
                        break;
                    }
                }
            }
            if (covered == sequence_length) {
                break;
            }
        }
    }

    const int starts = dx * dy;
    vector<uint64_t> sequences(static_cast<size_t>(starts) * word_count, 0ULL);
    auto set_bit = [&](int id, int pos) {
        sequences[static_cast<size_t>(id) * word_count + pos / 64] |= 1ULL << (pos % 64);
    };
    auto get_word = [&](int id, int word) -> uint64_t {
        return sequences[static_cast<size_t>(id) * word_count + word];
    };

    for (int sy = 1; sy <= dy; ++sy) {
        for (int sx = 1; sx <= dx; ++sx) {
            int id = (sy - 1) * dx + (sx - 1);
            for (size_t i = 0; i < markers.size(); ++i) {
                int rx = markers[i].x - sx;
                int ry = markers[i].y - sy;
                int pos = visit_time[offset_index(rx, ry)];
                set_bit(id, pos);
            }
        }
    }

    vector<int> order(starts);
    iota(order.begin(), order.end(), 0);

    auto sequence_less = [&](int a, int b) {
        for (int word = 0; word < word_count; ++word) {
            uint64_t wa = get_word(a, word);
            uint64_t wb = get_word(b, word);
            if (wa != wb) {
                uint64_t diff = wa ^ wb;
                int bit = __builtin_ctzll(diff);
                return ((wa >> bit) & 1ULL) < ((wb >> bit) & 1ULL);
            }
        }
        return false;
    };

    sort(order.begin(), order.end(), sequence_less);

    auto lcp = [&](int a, int b) {
        int shared = 0;
        for (int word = 0; word < word_count; ++word) {
            uint64_t wa = get_word(a, word);
            uint64_t wb = get_word(b, word);
            if (wa == wb) {
                shared += 64;
                continue;
            }
            uint64_t diff = wa ^ wb;
            shared += __builtin_ctzll(diff);
            break;
        }
        if (shared > sequence_length) {
            shared = sequence_length;
        }
        return shared;
    };

    vector<int> answer(starts, 0);
    for (int i = 0; i < starts; ++i) {
        int id = order[i];
        int best = 0;
        if (i > 0) {
            best = max(best, lcp(id, order[i - 1]));
        }
        if (i + 1 < starts) {
            best = max(best, lcp(id, order[i + 1]));
        }
        answer[id] = best;
    }

    double expected = 0.0;
    int maximum = 0;
    for (int id = 0; id < starts; ++id) {
        expected += answer[id];
        maximum = max(maximum, answer[id]);
    }
    expected /= starts;

    cout << fixed << setprecision(3) << expected << '\n';
    cout << maximum << '\n';

    bool first = true;
    for (int sy = 1; sy <= dy; ++sy) {
        for (int sx = 1; sx <= dx; ++sx) {
            int id = (sy - 1) * dx + (sx - 1);
            if (answer[id] == maximum) {
                if (!first) {
                    cout << ' ';
                }
                first = false;
                cout << '(' << sx << ',' << sy << ')';
            }
        }
    }
    cout << '\n';

    return 0;
}

}  // namespace

int main() {
    return main_impl();
}

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

\title{ICPC World Finals 2021\\L. Where Am I?}
\author{}
\date{}

\begin{document}
\maketitle

\section*{Problem Summary}

For each possible starting cell inside the given $dx \times dy$ rectangle, the subject observes a binary
sequence while walking on the fixed clockwise spiral:
\begin{itemize}[leftmargin=*]
    \item $1$ if the current cell contains a marker,
    \item $0$ otherwise.
\end{itemize}

The subject stops as soon as the observed prefix is compatible with only one starting cell.

We must compute:
\begin{itemize}[leftmargin=*]
    \item the average stopping time over all starting cells,
    \item the maximum stopping time,
    \item all starting cells attaining that maximum.
\end{itemize}

\section*{Key Observations}

\begin{itemize}[leftmargin=*]
    \item All markers lie inside the given rectangle, and the starting cell is also inside that rectangle.
    Therefore every marker is at relative offset
    \[
        (\Delta x, \Delta y) \in [-(dx-1), dx-1] \times [-(dy-1), dy-1].
    \]
    If we define
    \[
        R = \max(dx-1, dy-1),
    \]
    then every relevant marker lies inside the square $[-R, R]^2$.

    \item The spiral visits every cell in that square within its first
    \[
        (2R+1)^2
    \]
    visited positions (including the starting cell). So after that many observations, every subject has
    already checked every relative position where a marker could possibly exist.

    \item Therefore each starting cell can be represented by one finite binary string of length
    \[
        L = (2R+1)^2,
    \]
    where bit $t$ tells whether the spiral position numbered $t$ contains a marker.

    \item A starting cell is identified after exactly $k$ steps iff its first $k+1$ bits form a prefix that no
    other starting cell has. Equivalently, if the largest common-prefix length with any other string is
    $\ell$, then the answer for that start is exactly $\ell$.

    \item After sorting all binary strings lexicographically, the largest common prefix of one string with
    any other string is attained by one of its two neighbors in sorted order. So only adjacent pairs matter.
\end{itemize}

\section*{Algorithm}

\begin{enumerate}[leftmargin=*]
    \item Generate the spiral order inside the square $[-R,R]^2$ and store, for each relative offset, the
    time when the spiral visits it.

    \item For each starting cell $(s_x, s_y)$, build its binary observation string:
    \begin{itemize}[leftmargin=*]
        \item for each marker $(m_x, m_y)$,
        \item compute the relative offset $(m_x-s_x, m_y-s_y)$,
        \item look up the spiral time of that offset,
        \item set that bit to $1$.
    \end{itemize}
    Since there are at most $100$ markers, this is much cheaper than simulating the whole spiral for every
    start.

    \item Store every binary string as packed $64$-bit words.

    \item Sort the starting cells lexicographically by these packed bit strings.

    \item For every adjacent pair in sorted order, compute their common-prefix length by scanning the
    words until the first differing word, then locating the first differing bit inside that word.

    \item For each start, let $\ell$ be the maximum common-prefix length with its predecessor and successor
    in sorted order. Then $\ell$ is exactly the required number of steps for that start.

    \item Aggregate the average, the maximum, and all coordinates achieving the maximum.
\end{enumerate}

\section*{Correctness Proof}

We prove that the algorithm returns the correct answer.

\paragraph{Lemma 1.}
For any starting cell, every marker that can ever be observed lies at a relative offset inside $[-R,R]^2$.

\paragraph{Proof.}
Both the starting cell and every marker lie inside the input rectangle. Hence the $x$-difference between
them is between $-(dx-1)$ and $dx-1$, and similarly the $y$-difference is between $-(dy-1)$ and
$dy-1$. Since $R = \max(dx-1, dy-1)$, every relative offset lies in $[-R,R]^2$. \qed

\paragraph{Lemma 2.}
For every starting cell, its infinite observation sequence is completely determined by the first
$L=(2R+1)^2$ visited positions of the spiral.

\paragraph{Proof.}
By Lemma 1, a marker can occur only at one of the $(2R+1)^2$ relative offsets inside $[-R,R]^2$.
The spiral visits each cell of this square exactly once before leaving it permanently. Therefore after the
first $L$ observations, the subject has already checked every relative position where a marker could exist.
All later observations are necessarily $0$, so the infinite sequence is fully determined by the first $L$
bits. \qed

\paragraph{Lemma 3.}
If two starting cells have longest common prefix of length $\ell$, then the first starting cell is identified
after exactly $\ell$ steps against the second one.

\paragraph{Proof.}
The first $\ell$ bits of the two observation strings are equal, so after fewer than $\ell$ steps the subject
has seen only a prefix that is still compatible with both starts. At step $\ell$, the subject has seen the
bit at index $\ell$, and this bit differs between the two strings. Thus these two starts become
distinguishable exactly after $\ell$ steps. \qed

\paragraph{Lemma 4.}
After lexicographically sorting all observation strings, for every string its maximum common-prefix length
with any other string is attained by one of its adjacent neighbors in the sorted order.

\paragraph{Proof.}
This is the standard property of lexicographic order. Fix a string $S$, and consider any other string $T$.
All strings sharing a given prefix with $S$ form a contiguous interval in sorted order. Therefore among all
strings, the ones with the longest shared prefix with $S$ must appear immediately next to $S$ on one
side or the other. \qed

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

\paragraph{Proof.}
By Lemma 2, the finite bit string built by the algorithm contains exactly the relevant observations for
each starting cell. By Lemma 3, the number of steps needed to distinguish one start from another is the
common-prefix length of their strings. By Lemma 4, it is enough to compare each string only with its
sorted neighbors to find the worst competing start. Therefore the algorithm computes the correct stopping
time for every starting cell. The reported average, maximum, and list of maximizers are then immediate
from these correct per-cell values. \qed

\section*{Complexity Analysis}

Let
\[
    S = dx \cdot dy,\qquad M = \text{number of markers},\qquad L = (2R+1)^2.
\]

Building all bit strings takes $O(SM)$. Sorting them takes
\[
    O\!\left(S \log S \cdot \frac{L}{64}\right)
\]
word comparisons in the worst case. Computing all adjacent longest common prefixes takes
\[
    O\!\left(S \cdot \frac{L}{64}\right).
\]
With $dx,dy \le 100$, this easily fits within the limits.

The memory usage is
\[
    O\!\left(S \cdot \frac{L}{64}\right)
\]
for the packed observation strings.

\section*{Implementation Notes}

\begin{itemize}[leftmargin=*]
    \item The spiral order is exactly the one from the statement: up $1$, right $1$, down $2$, left $2$,
    up $3$, right $3$, and so on.
    \item The input rows are given from top to bottom, so line $j$ corresponds to $y = dy-j+1$.
    \item If two strings first differ inside one $64$-bit word, the first differing bit is found with
    \texttt{\_\_builtin\_ctzll}.
\end{itemize}

\end{document}