The problem is to find out the longest possible move path under certain constraints. Not sure if there are better methods, but a brutal force DFS just works with the given test data.

#include <vector>
#include <iostream>
#include <fstream>

using namespace std;

int N, B, ans;
vector<vector<char>> grid;
vector<vector<bool>> visited;
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};

bool on_grid(int x, int y) {
    return x >= 1 && y >= 1 && x <= N && y <= N;
}

vector<int> next_dir(int d) {
    if (d == 0 || d == 3) {
        return {1, 2};
    } else {
        return {0, 3};
    }
}

void move(int x, int y, int d, int step) {
    if (visited[x][y]) return;
    visited[x][y] = true;
    ans = std::max(ans, step);
    int xx = x + dx[d], yy = y + dy[d];
    if (on_grid(xx, yy) && grid[xx][yy] != '#') {
        move(xx, yy, d, step + 1);
    } else {
        auto dirs = next_dir(d);
        for (auto dir : dirs) {
            xx = x + dx[dir]; yy = y + dy[dir];
            if (on_grid(xx, yy) && grid[xx][yy] == '.') {
                move(xx, yy, dir, step + 1);
            }
        }
    }
    visited[x][y] = false;
}

int main() {
    ifstream fin("snail.in");
    ofstream fout("snail.out");
    fin >> N >> B;
    grid = vector<vector<char>>(N + 1, vector<char>(N + 1, '.'));
    visited = vector<vector<bool>>(N + 1, vector<bool>(N + 1, false));
    for (int i = 1; i <= B; ++i) {
        char col; int row;
        fin >> col >> row;
        grid[row][col - 'A' + 1] = '#';
    }
    
    move(1, 1, 2, 1);
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= N; ++j) {
            visited[i][j] = false;
        }
    }
    
    move(1, 1, 3, 1);
    
    cout << ans << endl;
    fout << ans << endl;
}

Paper digest - Existential Consistency: Measuring and Understanding Consistency at Facebook

Motivation

• Provides real world insights on how to quantify trade offs between performance and consistency wrt replicated storage systems.
• Describes a practical consistency monitoring system that tracks a new consistency metric ideally suited for health monitoring.

Introduction

• Stronger consistency implementation increases latency and/or decrease throughput.
• Eventual consistency (usually) provides good latency and/or throughput at larger scale. However there are drawbacks:
  • User visible anomalies: e.g. out order comments on social network post.
  • Programming complexity: complicated cases to reason about on weaker consistency model.
• So lots of recent work focus on providing stronger consistency models to overcome drawbacks of a weaker consistency model.
• But, not much work is done to quantify the trade offs, which this paper addresses.
• Within a cluster, per-object sequential and read-afterwrite consistency are provided.
• Across the entire system, eventual consistency is provided.
• Consistency is measured by running offline consistency checker (that checks various consistency models) on a logs that gathers random samples of social graph system.

Background

• Facebook’s replicated storage
  • Data model is directed graph.
  • User data is persistent in relational database, which is sharded, geo-replicated.
  • Each shard has a single maser region. Replication to slave region is async.
  • Database is cached (two-level) for the full replica per region. Root / leaf caches. Reads served by leaf cache.
  • Write path to cache: invalidation is async.
• Consistency models:
  • The usual ones, mentioned again (linearizability, sequential, per object sequential, read-after-write, eventual.)
  • Facebook’s consistency: per-object sequential consistency and read-after-write consistency within a cache, and eventual consistency across caches.
  • When user session spreads across multiple leaf caches (e.g. load balanced, or leaf cache failed): eventual consistency.

Principled Consistency Analysis

• Trace
  • Collect trace to identify violation of consistency models.
  • Trace only requests to a subset of vertices / edges stored in system for practical feasibility / avoid overhead.
  • Requests are logged on the web server that issuing the requests.
• Deal with clock skew
  • Solved by adding offsets (We account for this clock skew by expanding the invocation time and response time, i.e., we subtract 35 ms from all invocation times and add 35 ms to all response times.)
• Deal with losing logs
  • Use a secondary trace from Wormhole system which is lossy as well but combined with the writes from both trace has good coverage.
• The checker
  • Anomaly Checkers
    • Maintaining a directed graph.
    • Vertices represent the state of an object.
    • Edges represent the constraints on the ordering.
    • Check state transition order observed by reads is consistent with these constraints.
  • Linearizability Checker
    • Model operation as vertices, edges as constraints.
    • Check cycles.
    • Linearizability requires that there exists a total order that is legal.
    • Merging read vertices into the write vertices they observe requires matching reads to write.
  • Per-Object Sequential and Read-After-Write Checkers
    • As an add on of linearlizability checker which is superset of sequential / RAW consistency.
• Directions on future research into systems with stronger consistency
  • Build system were non-anomalous types have negligible overhead or
  • Provide stronger consistency for a small subset of a larger system.
  • While the latter would not prevent all anomalies, it would allow incremental deployment of these systems and significantly reduce the rate of anomalies.
  • Interestingly, such a subsystem that does provide linearizability is used within Facebook for a small set of object types, e.g., passwords.

Practical Consistency Analysis

• Why - need real time (for monitoring) instead of principal analysis (can be only done offline).
• φ-consistency

Conclusion

• TAO is highly consistent.
• There were anomalies under all of the consistency models we studied.

If there is no constraint of the “transpose” (Transposed means that a constant positive or negative value is added to every note value in the theme subsequence), then the problem is obviously a string search problem. How to deal with transpose when doing string search?

• The property of transpose imply that if sequence A is a transpose of sequence B, then there must be that for every Ai, we have Ai + Diff = Bi. Similarly, Ai+1 + Diff = Bi+1.
• Now we have Ai+1 - Ai = Bi+1 - Bi.
• So the problem can be reduced again to plain sub string search problem: we just need to transform the input to a diff sequence by having each element a diff between two adjacent elements.
• For string search, use KMP so the time is linear.

#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>

using namespace std;

int ans = 0;
int N;
vector<int> str, table;

int main() {
    ifstream fin("theme.in");
    ofstream fout("theme.out");
    fin >> N;
    str = vector<int>(N + 1, 0);
    table = vector<int>(N + 1, 0);
    int prev = 0, cur;
    for (int i = 0; i < N; ++i) {
        fin >> cur;
        str[i] = cur - prev;
        prev = cur;
    }
    str[N] = prev * -1;
    for (int from = N - 5; from >= 5; --from) {
        std::fill(table.begin(), table.end(), 0);
        table[0] = table[1] = 0;
        for (int i = from + 1; i <= N; ++i) {
            int j = table[i - from];
            while (j > 0 && str[i] != str[from + j]) {
               j = table[j];
            }
            table[i - from + 1] = (str[i] == str[from + j]) ? j + 1 : 0;
        }
        int j = 0;
        for (int i = 0; i < from - 1; ++i) {
            while (j > 0 && str[i] != str[from + j]) {
                j = table[j];
            }
            if (str[i] == str[from + j]) {
                j++;
                ans = std::max(ans, j + 1);
            }
        }
    }
    
    cout << (ans < 5 ? 0 : ans) << endl;
    fout << (ans < 5 ? 0 : ans) << endl;
    return 0;
}