IOI 2017 - Nowruz

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

namespace {

const int DR[4] = {-1, 0, 1, 0};
const int DC[4] = {0, 1, 0, -1};

struct Attempt {
    vector<char> used;
    int leaves = 0;
    int cells = 0;
};

int H, W, target_leaves;
vector<string> garden;
vector<int> free_cells;

inline int cell_id(int r, int c) { return r * W + c; }
inline int row_of(int id) { return id / W; }
inline int col_of(int id) { return id % W; }

bool is_free_cell(int r, int c) {
    return 0 <= r && r < H && 0 <= c && c < W && garden[r][c] == '.';
}

vector<int> neighbors(int id) {
    vector<int> out;
    int r = row_of(id), c = col_of(id);
    for (int dir = 0; dir < 4; ++dir) {
        int nr = r + DR[dir];
        int nc = c + DC[dir];
        if (is_free_cell(nr, nc)) out.push_back(cell_id(nr, nc));
    }
    return out;
}

struct Builder {
    vector<char> used;
    vector<unsigned char> degree;
    vector<unsigned char> adj_tree;
    int leaves = 0;
    int cells = 0;

    Builder() : used(H * W, 0), degree(H * W, 0), adj_tree(H * W, 0) {}

    void adjust_degree(int id, int delta) {
        if (degree[id] == 1) --leaves;
        degree[id] = static_cast<unsigned char>(degree[id] + delta);
        if (degree[id] == 1) ++leaves;
    }

    void add_cell(int id) {
        if (used[id]) return;
        used[id] = 1;
        ++cells;
        degree[id] = 0;

        for (int to : neighbors(id)) {
            if (used[to]) {
                adjust_degree(id, 1);
                adjust_degree(to, 1);
            } else {
                ++adj_tree[to];
            }
        }
    }

    vector<int> addable_leaves(int center) const {
        vector<int> extra;
        for (int to : neighbors(center)) {
            if (used[to]) continue;
            if (adj_tree[to] == 0) extra.push_back(to);
        }
        return extra;
    }

    int unique_parent(int id) const {
        for (int to : neighbors(id)) {
            if (used[to]) return to;
        }
        return -1;
    }

    Attempt finish() const { return {used, leaves, cells}; }
};

bool better_attempt(const Attempt &a, const Attempt &b) {
    if (a.leaves != b.leaves) return a.leaves > b.leaves;
    return a.cells > b.cells;
}

Attempt build_scan(int start, mt19937 &rng) {
    Builder cur;
    cur.add_cell(start);

    vector<int> order = free_cells;
    bool changed = true;
    while (changed) {
        changed = false;
        shuffle(order.begin(), order.end(), rng);
        for (int id : order) {
            if (cur.used[id] || cur.adj_tree[id] != 1) continue;
            cur.add_cell(id);
            changed = true;
        }
    }
    return cur.finish();
}

Attempt build_greedy(int start, mt19937 &rng) {
    Builder cur;
    cur.add_cell(start);

    vector<int> initial = neighbors(start);
    shuffle(initial.begin(), initial.end(), rng);
    for (int id : initial) {
        if (!cur.used[id] && cur.adj_tree[id] == 1) cur.add_cell(id);
    }

    while (true) {
        int best_immediate = -1;
        int best_net = INT_MIN;
        int best_seed_degree = -1;
        vector<pair<int, vector<int>>> options;

        for (int center : free_cells) {
            if (cur.used[center] || cur.adj_tree[center] != 1) continue;

            vector<int> extra = cur.addable_leaves(center);
            int immediate = max(1, (int)extra.size());
            int parent = cur.unique_parent(center);
            int net = immediate - (parent != -1 && cur.degree[parent] == 1 ? 1 : 0);
            int seed_degree = (int)neighbors(center).size();

            if (immediate > best_immediate ||
                (immediate == best_immediate && net > best_net) ||
                (immediate == best_immediate && net == best_net && seed_degree > best_seed_degree)) {
                best_immediate = immediate;
                best_net = net;
                best_seed_degree = seed_degree;
                options.clear();
            }
            if (immediate == best_immediate && net == best_net && seed_degree == best_seed_degree) {
                options.push_back({center, std::move(extra)});
            }
        }

        if (options.empty()) break;
        auto chosen = options[uniform_int_distribution<int>(0, (int)options.size() - 1)(rng)];
        cur.add_cell(chosen.first);
        shuffle(chosen.second.begin(), chosen.second.end(), rng);
        for (int leaf : chosen.second) {
            if (!cur.used[leaf] && cur.adj_tree[leaf] == 1) cur.add_cell(leaf);
        }
    }

    return cur.finish();
}

bool is_valid_tree(const vector<char> &used) {
    int start = -1;
    int nodes = 0;
    int twice_edges = 0;
    for (int id : free_cells) {
        if (!used[id]) continue;
        if (start == -1) start = id;
        ++nodes;
        for (int to : neighbors(id)) {
            if (used[to]) ++twice_edges;
        }
    }

    if (nodes <= 1) return true;
    if (twice_edges / 2 != nodes - 1) return false;

    vector<char> vis(H * W, 0);
    queue<int> q;
    q.push(start);
    vis[start] = 1;
    int seen = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        ++seen;
        for (int to : neighbors(v)) {
            if (!used[to] || vis[to]) continue;
            vis[to] = 1;
            q.push(to);
        }
    }
    return seen == nodes;
}

uint64_t input_hash() {
    uint64_t h = 1469598103934665603ULL;
    auto mix = [&](uint64_t x) {
        h ^= x;
        h *= 1099511628211ULL;
    };
    mix(H);
    mix(W);
    mix(target_leaves);
    for (const string &row : garden) {
        for (unsigned char ch : row) mix(ch);
    }
    return h;
}

}  // namespace

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

    cin >> H >> W >> target_leaves;
    garden.resize(H);
    for (int r = 0; r < H; ++r) cin >> garden[r];

    for (int r = 0; r < H; ++r) {
        for (int c = 0; c < W; ++c) {
            if (garden[r][c] == '.') free_cells.push_back(cell_id(r, c));
        }
    }

    if (free_cells.empty()) {
        for (const string &row : garden) cout << row << '\n';
        return 0;
    }

    uint64_t seed = input_hash();
    mt19937 rng((uint32_t)(seed ^ (seed >> 32)));

    vector<int> seed_order = free_cells;
    stable_sort(seed_order.begin(), seed_order.end(), [&](int a, int b) {
        int da = (int)neighbors(a).size();
        int db = (int)neighbors(b).size();
        if (da != db) return da > db;
        return a < b;
    });

    vector<int> starts;
    vector<char> taken(H * W, 0);
    int deterministic = min<int>((int)seed_order.size(), 24);
    for (int i = 0; i < deterministic; ++i) {
        starts.push_back(seed_order[i]);
        taken[seed_order[i]] = 1;
    }

    vector<int> shuffled = free_cells;
    shuffle(shuffled.begin(), shuffled.end(), rng);
    int extra_runs = min<int>((int)free_cells.size(), 96);
    for (int id : shuffled) {
        if ((int)starts.size() >= deterministic + extra_runs) break;
        if (taken[id]) continue;
        starts.push_back(id);
        taken[id] = 1;
    }

    Attempt best;
    best.used.assign(H * W, 0);
    best.leaves = -1;

    for (int start : starts) {
        Attempt cand1 = build_greedy(start, rng);
        if (is_valid_tree(cand1.used) && better_attempt(cand1, best)) best = cand1;
        if (best.leaves >= target_leaves) break;

        Attempt cand2 = build_scan(start, rng);
        if (is_valid_tree(cand2.used) && better_attempt(cand2, best)) best = cand2;
        if (best.leaves >= target_leaves) break;
    }

    if (best.leaves < 0) {
        best.used.assign(H * W, 0);
        best.used[free_cells[0]] = 1;
    }

    for (int r = 0; r < H; ++r) {
        string out = garden[r];
        for (int c = 0; c < W; ++c) {
            if (garden[r][c] != '.') continue;
            out[c] = best.used[cell_id(r, c)] ? '.' : 'X';
        }
        cout << out << '\n';
    }
    return 0;
}

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

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{gray},
  numbers=left,
  numberstyle=\tiny\color{gray},
  breaklines=true,
  frame=single,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2017 -- Nowruz}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}
This is an \emph{output-only} task.
We are given a grid with rocks (`\#') and free cells (`.').
We may turn some free cells into bushes (`X').
The remaining free cells must form a maze, i.e.\ for every two free cells there is exactly one simple
path between them.

In graph terms, if we keep only the free cells and connect orthogonally adjacent cells, the remaining
graph must be a tree.
A kid can hide exactly in a free cell of degree $1$, so the score is the number of leaves of that tree.

\section{Editorial Heuristic}
The official editorial suggests the following strong heuristic.

\begin{itemize}
  \item Start from one free cell.
  \item Only add a cell that currently has exactly one neighbor already inside the tree.
        This preserves the invariant ``the chosen cells form a tree''.
  \item A stronger move is to take such a frontier cell $u$, add it, and then also add every free
        neighbor $v$ of $u$ that currently has no tree neighbor.
        After the move, each such $v$ becomes a leaf.
  \item Repeat the best-looking expansion, and try many different random starts.
\end{itemize}

This does not guarantee the optimal score, but it is exactly the kind of approach intended for this
output-only problem.

\section{Why the Invariant Holds}
Suppose the current chosen cells already form a tree.

If we add one new cell with exactly one neighbor in the current tree, then we attach a new vertex by
one edge, so the graph stays connected and acyclic.

For the batched expansion around a center $u$:
\begin{itemize}
  \item $u$ has exactly one neighbor in the old tree, so it attaches safely;
  \item every extra cell $v$ added together with $u$ has no neighbor in the old tree;
  \item therefore each such $v$ is adjacent only to $u$ inside the new graph.
\end{itemize}

So one expansion adds a small star to the current tree, and the result is still a tree.

\section{Implemented Strategy}
For each chosen starting cell, the implementation tries two constructions.

\begin{enumerate}
  \item \textbf{Greedy star-expansion.}
        Repeatedly consider every frontier cell $u$ (a free cell with exactly one tree neighbor).
        Let $L(u)$ be the neighbors of $u$ that are still unused and currently have no tree neighbor.
        Adding $u$ together with $L(u)$ creates $\max(1, |L(u)|)$ immediate leaves, so we choose the
        best frontier cell by this score, with a few tie-breakers.

  \item \textbf{Randomized scan.}
        This is the simpler editorial method: repeatedly scan the cells in random order and add every
        cell that currently has exactly one tree neighbor until nothing changes.
\end{enumerate}

We run these heuristics from many deterministic pseudo-random starting points and keep the output with
the largest number of leaves.

\section{Complexity}
Let $F$ be the number of free cells and $R$ the number of restarts.

\begin{itemize}
  \item \textbf{Time:} about $O(RF^2)$ in the current implementation, which is easily fast enough for
        the small IOI output files.
  \item \textbf{Space:} $O(F)$.
\end{itemize}

\section{Implementation}
\begin{lstlisting}
// 1. Treat the free cells as a grid graph.
// 2. Grow only by attaching cells that currently have exactly one tree neighbor.
// 3. Prefer frontier cells that can immediately spawn many new leaves.
// 4. Also try the simpler randomized scan heuristic from the editorial.
// 5. Keep the valid tree with the largest number of leaves.
\end{lstlisting}

\end{document}