link (it says unofficial, but it is actually official)

M: notice that if we replace min by max, then this is L_{\inf} distance, and it's equivalent to the Manhattan distance after rotating everything by 45 degrees. And for Manhattan distance, the sum separates into two sums that can be computed straightforwardly.

And then we notice that min+max=sum, so we can subtract the above from the sum of sums (which is again finding the sum of Manhattan distances, but without rotating by 45).

F: notice that in a group of consecutive stones of the same color, we can get at most one weight, and we can get no weights from the first and last groups. It turns out that we can always get any ceil(k/2) maximum weights from k non-first-and-non-last groups (because we can always find a group that we want adjacent to a group that we don't want, and remove both).

Here's my code, 2.8/3s :) (I've removed includes and modint from ACL to make it smaller)

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()

using namespace std;

typedef int64_t int64;
typedef pair<int, int> ii;

int MAX_JUMP = 18;

using mint = atcoder::modint1000000007;

const mint base = 31373137;

const int INF = (int) 1e9;

struct Jump {
  int dest;
  mint hash;
};

class LMakeDifferent {
 public:
  void solveOne() {
    int n, q;
    cin >> n >> q;
    vector<int> t(n);
    for (auto& x : t) cin >> x;
    vector<int> tr = t;
    reverse(all(tr));
    vector<mint> basePow(MAX_JUMP);
    basePow[0] = base;
    for (int i = 1; i < MAX_JUMP; ++i) basePow[i] = basePow[i - 1] * basePow[i - 1];

    auto computeSingle = [&](vector<int> t) -> vector<Jump> {
      vector<int> backwards(n, 0);
      for (int i = 0; i < n; ++i) if (t[i] == 2 && backwards[i] == 0) {
        int j = i;
        int steps = 0;
        while (steps < n + 1 && t[j] == 2 && backwards[j] == 0) {
          j = (j + n - 2) % n;
          ++steps;
        }
        if (steps == n + 1) {
          j = i;
          for (int u = 0; u < steps; ++u) {
            backwards[j] = INF;
            j = (j + n - 2) % n;
          }
        } else {
          for (int u = 0; u < steps; ++u) {
            int nj = (j + 2) % n;
            backwards[nj] = 1 + backwards[j];
            j = nj;
          }
        }
        assert(backwards[i] > 0);
      }
      vector<Jump> res(n);
      for (int i = 0; i < n; ++i) {
        if (t[i] == 1) {
          res[i].dest = (i + 1) % n;
          int j = (i + n - 1) % n;
          res[i].hash = backwards[j] + 1;
        } else {
          res[i].dest = (i + 2) % n;
          res[i].hash = 0;
        }
      }
      return res;
    };

    auto duplicate = [&](int stage, const vector<Jump>& ju) -> vector<Jump> {
      vector<Jump> res(n);
      for (int i = 0; i < n; ++i) {
        Jump j1 = ju[i];
        Jump j2 = ju[j1.dest];
        res[i].dest = j2.dest;
        res[i].hash = j1.hash + basePow[stage] * j2.hash;
      }
      return res;
    };

    vector<vector<Jump>> direct;
    vector<vector<Jump>> reverse;
    direct.push_back(computeSingle(t));
    reverse.push_back(computeSingle(tr));
    for (int i = 1; i < MAX_JUMP; ++i) {
      direct.push_back(duplicate(i - 1, direct.back()));
      reverse.push_back(duplicate(i - 1, reverse.back()));
    }

    auto findNextDiff = [&](const vector<vector<Jump>>& direct, int p1, int p2) -> tuple<int, int, int, int, int> {
      if (direct.back()[p1].hash == direct.back()[p2].hash) return {INF, -1, -1, -1, -1};
      int when = 0;
      for (int j = MAX_JUMP - 1; j >= 0; --j) {
        if (direct[j][p1].hash == direct[j][p2].hash) {
          when += 1 << j;
          p1 = direct[j][p1].dest;
          p2 = direct[j][p2].dest;
        }
      }
      return {when, p1, p2, direct[0][p1].hash.val(), direct[0][p2].hash.val()};
    };

    auto handleDirection = [&](const vector<vector<Jump>>& direct, int p1, int p2) -> int {
      int res = INF;
      int offset = 0;
      for (int step = 0; step < MAX_JUMP; ++step) {
        auto[when, np1, np2, w1, w2] = findNextDiff(direct, p1, p2);
        if (when >= INF) return res;
        if (w1 == 0 || w2 == 0) {
          res = min(res, offset + when);
        } else {
          res = min(res, offset + when + min(w1, w2));
        }
        offset += when + 1;
        p1 = direct[0][np1].dest;
        p2 = direct[0][np2].dest;
      }
      return res;
    };

    for (int qi = 0; qi < q; ++qi) {
      int p1, p2;
      cin >> p1 >> p2;
      --p1; --p2;
      int res = min(handleDirection(direct, p1, p2), handleDirection(reverse, n - 1 - p1, n - 1 - p2));
      if (res >= INF) res = -1;
      cout << res << "\n";
    }
  }

  void solve() {
    int nt = 1;
    for (int it = 0; it < nt; ++it) {
      // cout << "Case #" << (it + 1) << ": ";
      solveOne();
    }
  }
};

// #define st_mtimespec st_mtim

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    LMakeDifferent solver;


    solver.solve();
    return 0;
}

Hi, I uploaded the tester's solutions to the Gym. They should have no TL issues in Yandex, I think.

I believe L also could be solved in $$$O((n + q) \log n)$$$ for any graph, not a specific one given in this task.

It is somewhat similar to DFA minimization algorithm. Let's first split all vertices into two groups by color. Then do at most $$$n$$$ iterations of splitting groups into smaller ones. We can maintain the property that after $$$k$$$ iterations two vertices are in the same group iff they cannot be distinguished by $$$k$$$ moves.

Naively on each iteration, we can split vertices into new groups by key (current group id, [current group id of the $$$i$$$-th children of current vertex] for all $$$i$$$).

But it can be done in a lazy way. We could recalculate the group for a vertex only if one of its child groups changed in the previous step.

Also, we can apply optimization — if, on some step we want to move more than half of the vertices of some group to the same new group, we can leave them in the current group, and move others. This way every time a vertex is moved to another group, group size is reduced at least by a factor of two, so each vertex is moved at most $$$O(\log n)$$$ times.

Here is my implementation: 164708181, it is $$$O(n \log^2 n)$$$ because it uses sets to maintain groups, but it can be easily optimized to $$$O(n \log n)$$$.

K: For a board, if $$$n,m\ge 2$$$ you delete the last column and the last row, and delete empty columns and rows at the same time, it will be the same as the original board. That's because if one player move the piece to the last column or the last row, the opposite can do $$$\ge 1$$$ operations.
If every board has $$$n=1$$$ or $$$m=1$$$, the answer can be get easily.

I also did all of that (on paper), but I didn't believe I would be able to implement that, so I found a simplification:

I was going through (anti-)diagonals instead of rows, there we also have several arithmetic progressions with step 2. There will be one arithmetic progression (I called them segments) which is closest to 0, it will become wider with time, while other segments will shrink (at least on the side closer to the "main" segment). In terms of the initial picture the main segment covered some upper-left part of the plane, while segments below it covered some segments of rows (below that upper-left part) and segments above covered some segments of columns (to the right of that upper-left part). But since we are only interested in the value in the top-left corner, all the areas except for the main upper-left part are not interesting to us! Thus we can ignore all the segments except the main one. Moreover, new segments can only appear when some cell doesn't have the neighbour to the right or below AND the value we would assign there normally is not correct, but in this case we will assign 0 to this cell, which means that this cell will become the corner of the new main zone. In the end the solution is very simple: traverse both borders, maintain the current corner of the main zone, if encounter a cell with only one neighbour which would have incorrect value, make it the new corner of the main zone.

This is to guarantee that simplex would MLE.

No reference solutions are close to 32MB ML, my tester solution came in under 4MB and I think only one tester had a solution above 8MB.