EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2023
ICPC 2023

F. Tilting Tiles

47th Annual hosted by ICPC World Championship AASTMT Problem F Tilting Tiles Time limit: 3 secon...

Updated May 21, 2026
Track ICPC
Year 2023
Statement Text + PDF
TeXC++Statement textStatement PDF
Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF 
  47th Annual                                                                                 hosted by
  ICPC World
Championship                                                                                  AASTMT
                                                 Problem F
                                                 Tilting Tiles
                                       Time limit: 3 seconds
You found a weird puzzle in a box with old toys in your attic. The puzzle forms a rectangular grid board
made of h × w square cells. Some cells in that grid have a colored tile placed on them, as shown in
Figure F.1.
r        g   y       b
y   r
Figure F.1: Color tiles correspond to the starting arrangement in Sample Input 1.

You are not yet sure what the exact goal of this puzzle is, but you started examining possible ways of rearranging the tiles. Their arrangement can be manipulated by tilting the grid in one of the four cardinal directions: to your left, to your right, towards you, or away from you. Tilting causes all the tiles to slide in the respective direction until they are blocked either by the boundary or by another tile. Given a starting and ending arrangement, determine whether there exists some sequence of tilts that transforms the former into the latter. Figure F.2 illustrates tilting of the puzzle shown in Sample Input 1.

         r                   tilt     r                                     r      tilt    y   r   b   r
 tilt                      towards                       tilt                     away
         r     g   y   b              r                                     r                      y   r
 left                        you                        right                   from you
=⇒       b                   =⇒       b    g            =⇒              b   g     =⇒                   g
y     r                      y    r    y   b           y   r   y   b                          b
Figure F.2: Solution to Sample Input 1.

Input

The first line of input contains two integers h and w (1 ≤ h, w ≤ 500) representing the height and width of the grid. Then follow h lines giving the starting arrangement from the top row to the bottom row. Each of these lines contains a string of length w describing cells on the row from left to right. If a cell is empty, the corresponding character is a dot (.). If there is a tile, the color of that tile is given, denoted by a lowercase letter (a-z). Different letters represent different colors, and tiles of the same color cannot be distinguished. After the starting arrangement, there is one empty line and then follows a description of the ending arrangement, consisting of h lines in the same format as for the starting arrangement.

                                    World Finals | ICPC 2023 Luxor
  47th Annual                                                                           hosted by
  ICPC World
Championship                                                                            AASTMT

Output

Output yes if a sequence of tilts exists that transforms the starting arrangement to the ending arrange- ment, and no otherwise.

Sample Tests

Sample 1
Sample Input 
 4 4
 .r..
 rgyb
 .b..
 .yr.

 yrbr
 ..yr
 ...g
 ...b
Sample Output 
yes
Sample 2
Sample Input 
 1 7
 ....x..

 ..x....
Sample Output 
no
Sample 3
Sample Input 
 4 3
 yr.
 ..b
 ry.
 b..

 ...
 ..b
 .ry
 byb
Sample Output 
no
Editorial

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

  • After we have made at least one horizontal and at least one vertical tilt, every tile is flush in a corner. From then on, the occupied shape never changes; only the corner anchor and the order of the tiles inside that shape can change.

  • Therefore every reachable configuration is of one of two types:

    • the start itself or a state reachable in one move;

    • a corner-anchored state obtained after one horizontal and one vertical move, followed by repeated cycling through the four corners.

    • For a fixed corner-anchored base state, one full 4-move cycle induces a permutation $p$ on the tile positions. Reachability becomes: does some power $p^n$ produce the target labeling?

    • On each cycle of $p$, this is a string-rotation problem. Either there is no valid rotation, or the valid exponents satisfy one congruence \[ n \equiv a \pmod m. \]

    • The whole board is reachable iff the congruences from all permutation cycles are mutually consistent.

    Algorithm

    1. Compare the multisets of letters in the two boards. If they differ, output no.

    2. Check the trivial cases: the start itself and the four boards reachable in one tilt.

    3. If the board has height $1$ or width $1$, no longer sequence can change anything beyond those cases, so we stop.

    4. Otherwise try the eight two-move seeds consisting of one horizontal and one vertical move. Each seed produces a corner-anchored base state.

    5. For that base state:

      • label the tiles distinctly and simulate one full 4-move corner cycle to obtain the permutation $p$ of positions;

      • for each of the four corner anchors along this cycle, check whether the target has the same occupied shape;

      • if so, read the target letters in the order of the current labels and test whether some power of $p$ maps the base letter sequence to that target sequence.

      • To test a power of $p$, decompose $p$ into cycles. For each cycle:

        • extract the source and target strings on that cycle;

        • find a matching rotation by string matching on the doubled source string;

        • reduce all valid shifts modulo the minimal period of that cycle string.

        • If the resulting congruences are pairwise consistent, output yes. If all seeds fail, output no. enumerate

          Correctness Proof

          We prove that the algorithm returns the correct answer.

          Lemma 1.

          After at least one horizontal and at least one vertical tilt, the occupied shape is fixed up to which corner it is anchored in.

          Proof.

          A horizontal tilt compresses each row against one side, and a vertical tilt compresses each column against one side. After both directions have been used, every row and every column is already maximally compressed, so later tilts can only move the compressed shape between corners. The set of occupied cells inside that shape cannot change anymore. □

          Lemma 2.

          For a fixed corner-anchored base state, the reachable labelings are exactly the boards obtained by applying some power of the induced permutation $p$ and then possibly stopping at one of the four corner anchors on that cycle.

          Proof.

          By Lemma 1, once the shape is corner-anchored, every later move only changes the corner and the order of the labeled tiles within the fixed shape. One full round through the four corners applies a fixed permutation $p$ to the labels. Therefore every later state is described by a power of $p$ together with one of the four anchors where we stop, and every such state is realized by following that many full rounds and then the corresponding prefix of the 4-cycle. □

          Lemma 3.

          For one cycle of the permutation $p$, the set of valid exponents is either empty or one congruence class $n \equiv a \pmod m$, where $m$ is the minimal period of the source string on that cycle.

          Proof.

          Along one cycle of length $L$, applying $p$ repeatedly rotates the letters cyclically. A target labeling is reachable on that cycle exactly when it is some rotation of the source string. String matching on the doubled source string finds one such rotation, if it exists.

          If the source string has minimal period $m$, then two rotations produce the same string exactly when their offsets are congruent modulo $m$. Hence all valid exponents form one residue class modulo $m$. □

          Theorem.

          The algorithm outputs yes exactly when the target board is reachable.

          Proof.

          By Lemma 1, every nontrivial reachable board is covered by one of the eight two-move seeds and one of the four anchors examined by the algorithm. By Lemma 2, after fixing such a seed and anchor, reachability reduces exactly to whether some power of the associated permutation $p$ produces the target labeling.

          By Lemma 3, each cycle of $p$ contributes either impossibility or one congruence on the exponent. A single exponent exists exactly when all these congruences are mutually consistent. Therefore the algorithm accepts exactly the reachable targets. □

          Complexity Analysis

          Let $N=hw$ be the number of cells and let $T$ be the number of tiles. Each tilt simulation is $O(N)$. We try only a constant number of seeds and anchors, so the board-processing cost is $O(N)$. For each candidate we also process the permutation cycles and run linear-time string matching on the cycle strings, which is $O(T)$. Thus the total running time is $O(N)$ and the memory usage is $O(N)$.

          Implementation Notes

          • Equal-colored tiles are handled by comparing label sequences only after the occupied shape is matched.

          • Congruences are checked by grouping equal moduli and then applying the gcd consistency test.

Implementation

Code

C++ solution used for this page.

C++

Clean code view with a raw-file link when you want the original source.

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

namespace {

int gcd_int(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int minimal_period(const string& s) {
    int n = static_cast<int>(s.size());
    if (n == 0) {
        return 1;
    }
    vector<int> pi(n);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            ++j;
        }
        pi[i] = j;
    }
    int p = n - pi.back();
    return (n % p == 0 ? p : n);
}

int rotation_match(const string& source, const string& target) {
    int n = static_cast<int>(source.size());
    if (n != static_cast<int>(target.size())) {
        return -1;
    }
    if (n == 0) {
        return 0;
    }

    string text = source + source;
    vector<int> pi(n);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && target[i] != target[j]) {
            j = pi[j - 1];
        }
        if (target[i] == target[j]) {
            ++j;
        }
        pi[i] = j;
    }

    int j = 0;
    for (int i = 0; i < 2 * n - 1; ++i) {
        while (j > 0 && text[i] != target[j]) {
            j = pi[j - 1];
        }
        if (text[i] == target[j]) {
            ++j;
        }
        if (j == n) {
            int pos = i - n + 1;
            if (pos < n) {
                return pos;
            }
            j = pi[j - 1];
        }
    }
    return -1;
}

bool consistent_under_permutation(const vector<int>& to, const string& source, const string& target) {
    int n = static_cast<int>(to.size());
    vector<char> seen(n, false);
    unordered_map<int, int> residue_by_modulus;

    for (int i = 0; i < n; ++i) {
        if (seen[i]) {
            continue;
        }
        vector<int> cycle;
        int cur = i;
        while (!seen[cur]) {
            seen[cur] = true;
            cycle.push_back(cur);
            cur = to[cur];
        }

        string a;
        string b;
        a.reserve(cycle.size());
        b.reserve(cycle.size());
        for (int idx : cycle) {
            a.push_back(source[idx]);
            b.push_back(target[idx]);
        }

        int pos = rotation_match(a, b);
        if (pos == -1) {
            return false;
        }

        int period = minimal_period(a);
        int need = (static_cast<int>(cycle.size()) - pos) % static_cast<int>(cycle.size());
        need %= period;

        auto it = residue_by_modulus.find(period);
        if (it == residue_by_modulus.end()) {
            residue_by_modulus[period] = need;
        } else if (it->second != need) {
            return false;
        }
    }

    vector<pair<int, int>> congruences(residue_by_modulus.begin(), residue_by_modulus.end());
    for (int i = 0; i < static_cast<int>(congruences.size()); ++i) {
        for (int j = i + 1; j < static_cast<int>(congruences.size()); ++j) {
            int m1 = congruences[i].first;
            int a1 = congruences[i].second;
            int m2 = congruences[j].first;
            int a2 = congruences[j].second;
            if ((a1 - a2) % gcd_int(m1, m2) != 0) {
                return false;
            }
        }
    }
    return true;
}

vector<string> tilt_chars(const vector<string>& grid, char dir) {
    int h = static_cast<int>(grid.size());
    int w = static_cast<int>(grid[0].size());
    vector<string> next(h, string(w, '.'));

    if (dir == 'L' || dir == 'R') {
        for (int r = 0; r < h; ++r) {
            string values;
            values.reserve(w);
            for (int c = 0; c < w; ++c) {
                if (grid[r][c] != '.') {
                    values.push_back(grid[r][c]);
                }
            }
            int offset = (dir == 'L' ? 0 : w - static_cast<int>(values.size()));
            for (int i = 0; i < static_cast<int>(values.size()); ++i) {
                next[r][offset + i] = values[i];
            }
        }
    } else {
        for (int c = 0; c < w; ++c) {
            string values;
            values.reserve(h);
            for (int r = 0; r < h; ++r) {
                if (grid[r][c] != '.') {
                    values.push_back(grid[r][c]);
                }
            }
            int offset = (dir == 'U' ? 0 : h - static_cast<int>(values.size()));
            for (int i = 0; i < static_cast<int>(values.size()); ++i) {
                next[offset + i][c] = values[i];
            }
        }
    }
    return next;
}

vector<vector<int>> tilt_labels(const vector<vector<int>>& grid, char dir) {
    int h = static_cast<int>(grid.size());
    int w = static_cast<int>(grid[0].size());
    vector<vector<int>> next(h, vector<int>(w, -1));

    if (dir == 'L' || dir == 'R') {
        for (int r = 0; r < h; ++r) {
            vector<int> values;
            values.reserve(w);
            for (int c = 0; c < w; ++c) {
                if (grid[r][c] != -1) {
                    values.push_back(grid[r][c]);
                }
            }
            int offset = (dir == 'L' ? 0 : w - static_cast<int>(values.size()));
            for (int i = 0; i < static_cast<int>(values.size()); ++i) {
                next[r][offset + i] = values[i];
            }
        }
    } else {
        for (int c = 0; c < w; ++c) {
            vector<int> values;
            values.reserve(h);
            for (int r = 0; r < h; ++r) {
                if (grid[r][c] != -1) {
                    values.push_back(grid[r][c]);
                }
            }
            int offset = (dir == 'U' ? 0 : h - static_cast<int>(values.size()));
            for (int i = 0; i < static_cast<int>(values.size()); ++i) {
                next[offset + i][c] = values[i];
            }
        }
    }
    return next;
}

vector<string> apply_sequence(vector<string> grid, const string& sequence) {
    for (char dir : sequence) {
        grid = tilt_chars(grid, dir);
    }
    return grid;
}

string corner_cycle(const string& seq) {
    bool left = (seq.find('L') != string::npos);
    bool up = (seq.find('U') != string::npos);
    if (left && up) {
        return "RDLU";
    }
    if (!left && up) {
        return "DLUR";
    }
    if (!left && !up) {
        return "LURD";
    }
    return "ULDR";
}

bool same_grid(const vector<string>& a, const vector<string>& b) {
    return a == b;
}

bool same_multiset(const vector<string>& a, const vector<string>& b) {
    array<int, 26> ca{};
    array<int, 26> cb{};
    for (const string& row : a) {
        for (char ch : row) {
            if (ch != '.') {
                ++ca[ch - 'a'];
            }
        }
    }
    for (const string& row : b) {
        for (char ch : row) {
            if (ch != '.') {
                ++cb[ch - 'a'];
            }
        }
    }
    return ca == cb;
}

bool check_cycle(const vector<string>& base_grid, const vector<string>& target, const string& order) {
    int h = static_cast<int>(base_grid.size());
    int w = static_cast<int>(base_grid[0].size());

    int tiles = 0;
    vector<vector<int>> labels(h, vector<int>(w, -1));
    string source;
    for (int r = 0; r < h; ++r) {
        for (int c = 0; c < w; ++c) {
            if (base_grid[r][c] != '.') {
                labels[r][c] = tiles++;
                source.push_back(base_grid[r][c]);
            }
        }
    }

    vector<vector<vector<int>>> states(5);
    states[0] = labels;
    for (int i = 0; i < 4; ++i) {
        states[i + 1] = tilt_labels(states[i], order[i]);
    }

    vector<int> permutation(tiles);
    int idx = 0;
    for (int r = 0; r < h; ++r) {
        for (int c = 0; c < w; ++c) {
            if (states[4][r][c] != -1) {
                permutation[states[4][r][c]] = idx++;
            }
        }
    }

    for (int step = 0; step < 4; ++step) {
        string pulled(tiles, '?');
        bool valid = true;
        for (int r = 0; r < h && valid; ++r) {
            for (int c = 0; c < w; ++c) {
                bool occupied = (states[step][r][c] != -1);
                bool want = (target[r][c] != '.');
                if (occupied != want) {
                    valid = false;
                    break;
                }
                if (occupied) {
                    pulled[states[step][r][c]] = target[r][c];
                }
            }
        }
        if (valid && consistent_under_permutation(permutation, source, pulled)) {
            return true;
        }
    }
    return false;
}

void solve() {
    int h, w;
    cin >> h >> w;

    vector<string> start(h), target(h);
    for (int i = 0; i < h; ++i) {
        cin >> start[i];
    }
    string blank;
    getline(cin, blank);
    getline(cin, blank);
    for (int i = 0; i < h; ++i) {
        cin >> target[i];
    }

    if (!same_multiset(start, target)) {
        cout << "no\n";
        return;
    }

    if (same_grid(start, target)) {
        cout << "yes\n";
        return;
    }

    vector<char> moves = {'L', 'R', 'U', 'D'};
    for (char dir : moves) {
        if (same_grid(tilt_chars(start, dir), target)) {
            cout << "yes\n";
            return;
        }
    }

    if (h == 1 || w == 1) {
        cout << "no\n";
        return;
    }

    const vector<string> seeds = {"LU", "LD", "RU", "RD", "UL", "UR", "DL", "DR"};
    for (const string& seq : seeds) {
        vector<string> base = apply_sequence(start, seq);
        if (check_cycle(base, target, corner_cycle(seq))) {
            cout << "yes\n";
            return;
        }
    }

    cout << "no\n";
}

}  // namespace

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

    solve();
    return 0;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2023/F-tilting-tiles/solution.texC++ implementationcompetitive_programming/icpc/2023/F-tilting-tiles/solution.cppStatement textcompetitive_programming/icpc/2023/F-tilting-tiles/statement.txtStatement PDFcompetitive_programming/icpc/2023/F-tilting-tiles/statement.pdfMetadatacompetitive_programming/icpc/2023/F-tilting-tiles/meta.jsonYear packetcompetitive_programming/icpc/2023/contest_problems.pdf