Will it be available on the CSES website right after the mirror ends?

We won't organise it, but we will share problem data after the contest ends.

I don't think Baltic was over posted on CF, but probably it will be on qoj.ac

Where can we find tasks?

The website doesn't load for me fsr

That is correct. You should be careful with the implementation though, because we are dealing with a graph that has 3 million vertices and 5 million edges.

no, cause submissions from the official contest have higher priority queue from the mirror contest.

We will have dedicated judges for the mirror for day 2 which should solve this problem. We apologise for the long queue on the first day.

In such number theory problems almost everything passes lol. I have a solution using DP which minimizes GCD given the number of operations. I have no idea why it's optimal to minimize GCD at each step. Also this solution didn't get 100 at first. Then I added if (1.0 * clock() / CLOCKS_PER_SEC >= TL) and it passed.

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int &x : a) {
    cin >> x;
  }
  constexpr int C = 8, INF = 1e9 + 1;
  vector<vector<int>> dp(n, vector<int>(C, INF));
  for (int i = 0; i < C; i++) {
    dp[0][i] = a[0] + i;
  }
  int max_i = 0;
  for (int i = 1; i < n && 1.0 * clock() / CLOCKS_PER_SEC <= 1.3; i++) {
    for (int j = 0; j < C; j++) {
      for (int dj = 0; j + dj < C; dj++) {
        dp[i][j + dj] = min(dp[i][j + dj], gcd(dp[i - 1][j], a[i] + dj));
      }
    }
    ++max_i;
  }
  for (int i = 0; i < C; i++) {
    if (dp[max_i][i] == 1) {
      cout << i << "\n";
      exit(0);
    }
  }
}

Not sure what you are doing here, but here is some reasoning for why most reasonable solutions will get AC on the problem:

• The answer for two given $$$a, b \leq 10^{7}$$$ is apparently always $$$\leq 4$$$ (in particular, the answer is always $$$\leq 4$$$), so for $$$n \leq 8$$$, say, one can bruteforce the up to $$$4^{8}$$$ possibilities and win. If your code does anything like this, it solves the answer for small $$$n$$$. By the way, note that we may also expect bruteforcing $$$4^{8}$$$ to take care of automatically a random testcase where the answer is $$$ \gt 4$$$, since these pairs are very rare and it is highly unlikely that $$$(a, b)$$$ and $$$(a+1, b)$$$ are both rare.

• For larger $$$n$$$, say $$$n \geq 9$$$ with some simple arguments it can be shown that the answer is always $$$0$$$ or $$$1$$$, since the $$$9$$$th primorial exceeds $$$10^{7}$$$. As a result, any bruteforce that is optimised in the sense that it stops searching for suboptimal answers relative to an already found answer will always succeed quickly for $$$n \geq 9$$$, since it would have already found a working example with $$$\text{cost} = 1$$$.

By the way, in case heuristics are unable to convince you the answer is low, I recommend looking at USA TSTST 2011/3, which proves that for two numbers $$$a, b \leq N$$$ we need no more than $$$O(\log N)$$$ steps to convert their $$$\gcd$$$ to $$$1$$$. Of course, this bound is very crude and in practice the answer is even lower.

No. Problem A seems that you can write the brutest dp and optimize it by only recording the useful values of each $$$a'_i$$$. That is (for me), $$$a'_i$$$ is always in $$$a_{i\pm 0\sim 2}\pm 0\sim 4$$$ (maybe that's a very loose bound). Anyway, time complexity is absolutely $$$O(n)$$$.

EDIT. The solution turned out to be wrong.

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;

constexpr int MAX_N = 300000, MAX_L = 40;
constexpr int MAX_M = 1'000'005;

int rmq[MAX_L][MAX_N];
vector<int> groups[MAX_M];
int lq[MAX_N], rq[MAX_N], max_q[MAX_N];
int A[MAX_N], answer[MAX_N];

int query_max(int left, int right) {
  int t = __lg(right - left);
  return max(rmq[t][left], rmq[t][right - (1 << t)]);
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    cin >> A[i];
    rmq[0][i] = A[i];
    groups[A[i]].push_back(i);
  }
  for (int i = 0; i + 1 < MAX_L; i++) {
    for (int j = 0; j + (2LL << i) <= n; j++) {
      rmq[i + 1][j] = max(rmq[i][j], rmq[i][j + (1 << i)]);
    }
  }
  for (int i = 0; i < q; i++) {
    cin >> lq[i] >> rq[i];
    --lq[i];
    max_q[i] = query_max(lq[i], rq[i]);
  }
  vector<int> ord(q);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [](int x, int y) {
    return max_q[x] < max_q[y];
  });
  for (int i = 0; i < q; i++) {
    int ir = i + 1;
    while (ir < q && max_q[ord[i]] == max_q[ord[ir]]) {
      ++ir;
    }
    vector<int> pos;
    int low = max_q[ord[i]] - MAX_L;
    for (int j = max_q[ord[i]]; j > max_q[ord[i]] - MAX_L && j >= 0; j--) {
      for (int k : groups[j]) {
        pos.push_back(k);
      }
    }
    sort(pos.begin(), pos.end());
    vector<int> B, pos_new;
    B.reserve(2 * pos.size() + 1);
    pos_new.reserve(2 * pos.size() + 1);
    if (pos.empty() || pos[0] > 0) {
      B.push_back(0);
      pos_new.push_back(0);
    }
    for (int j = 0; j < int(pos.size()); j++) {
      B.push_back(A[pos[j]] - low);
      pos_new.push_back(pos[j]);
      if (j + 1 < int(pos.size()) && pos[j + 1] - pos[j] > 1) {
        B.push_back(0);
        pos_new.push_back(pos[j] + 1);
      }
    }
    if (!pos.empty() && pos.back() < n - 1) {
      B.push_back(0);
      pos_new.push_back(pos.back() + 1);
    }
    int K = int(B.size());
    vector<vector<int>> up(MAX_L + 20, vector<int>(K + 1, K));
    for (int j = 0; j < MAX_L + 20; j++) {
      for (int k = 0; k < K; k++) {
        if (B[k] == j) {
          up[j][k] = k + 1;
        } else if (j == 0) {
          up[j][k] = k;
        } else {
          up[j][k] = up[j - 1][up[j - 1][k]];
        }
      }
    }
    for (int j = i; j < ir; j++) {
      int left = upper_bound(pos_new.begin(), pos_new.end(), lq[ord[j]]) - pos_new.begin() - 1;
      int right = upper_bound(pos_new.begin(), pos_new.end(), rq[ord[j]] - 1) - pos_new.begin();
      for (int k = MAX_L; k < MAX_L + 20; k++) {
        if (up[k][left] >= right) {
          answer[ord[j]] = max_q[ord[j]] + k - MAX_L;
          break;
        }
      }
    }
    i = ir - 1;
  }
  for (int i = 0; i < q; i++) {
    cout << answer[i] << "\n";
  }
}

The hack is 1 1 1 2 3 4 ... N 1 1 2 3 4 ... N (thanks Milmon for this test and avighnakc for letting me know about it).

https://boi2025.mat.umk.pl/editorial_and_tests.php

Cses is usually where it's the easiest to practice, but I don't know the exact date that it will be uploaded.