HackerRank Algebra – Minimal Cyclic Shift – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Challenge: Minimal Cyclic Shift

Subdomeniu: Algebra (algebra)

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464815295

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/minimal-cyclic-shift/problem

Cerinta

We consider two sequences of integers, $a_0, a_1, \ldots, a_{n-1}$ and $b_0, b_1, \ldots, b_{n-1}$, to be _similar_ if there exists a polynomial, $P(x)$, with integer coefficients of a degree $\le k$ such that $P(i) = (a_i - b_i ) \bmod m$ (where $m = 998244353$) for $0 \le i \lt n$. 

Given sequences $a$ and $b$, find and print the minimal integer $x$ (where $0 \le x \lt n$) such that a [cyclic shift](https://en.wikipedia.org/wiki/Circular_shift) of $b$ on $x$ elements (sequence $b_{x\ \text{mod}\ n}, b_{(x+1)\ \text{mod}\ n}, \dots b_{(x+n-1)\ \text{mod}\ n}$) is _similar_ to $a$; if no such $x$ exists, print $-1$ instead.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ (the length of the sequences) and $k$ (the maximum degree of polynomial).		
The second line contains $n$ space-separated integers describing the respective values of $a_0, a_1, \ldots, a_{n-1}$.			
The third line contains $n$ space-separated integers describing the respective values of $b_0, b_1, \ldots, b_{n-1}$.

Output Format

Print an integer, $x$, denoting the minimal appropriate cyclic shift. If no such value exists, print $-1$ instead.

Constraints

- $1 \le n \le 10^5$
- $0 \le k \le 10^9$
- $0 \le a_i, b_i < m$

Cod sursa

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

static const int MOD = 998244353;
static const int G = 3;

static int mod_pow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return (int)r;
}

static inline int addm(int a, int b) { a += b; if (a >= MOD) a -= MOD; return a; }
static inline int subm(int a, int b) { a -= b; if (a < 0) a += MOD; return a; }

static void ntt(vector<int>& a, bool invert) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        int wlen = mod_pow(G, (MOD - 1) / len);
        if (invert) wlen = mod_pow(wlen, MOD - 2);
        for (int i = 0; i < n; i += len) {
            int w = 1;
            for (int j = 0; j < len / 2; j++) {
                int u = a[i + j];
                int v = (int)(1LL * a[i + j + len / 2] * w % MOD);
                a[i + j] = addm(u, v);
                a[i + j + len / 2] = subm(u, v);
                w = (int)(1LL * w * wlen % MOD);
            }
        }
    }
    if (invert) {
        int n_inv = mod_pow(n, MOD - 2);
        for (int &x : a) x = (int)(1LL * x * n_inv % MOD);
    }
}

static vector<int> convolution(vector<int> a, vector<int> b) {
    if (a.empty() || b.empty()) return {};
    int need = (int)a.size() + (int)b.size() - 1;
    int n = 1;
    while (n < need) n <<= 1;
    a.resize(n); b.resize(n);
    ntt(a, false);
    ntt(b, false);
    for (int i = 0; i < n; i++) a[i] = (int)(1LL * a[i] * b[i] % MOD);
    ntt(a, true);
    a.resize(need);
    return a;
}

static vector<int> z_function(const vector<long long>& s) {
    int n = (int)s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

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

    int n;
    long long k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    if (k >= n - 1) {
        cout << 0 << '\n';
        return 0;
    }

    int K = (int)k + 1;
    int M = n - K; // number of constraints positions
    if (M <= 0) {
        cout << 0 << '\n';
        return 0;
    }

    vector<int> fact(K + 1), invfact(K + 1);
    fact[0] = 1;
    for (int i = 1; i <= K; i++) fact[i] = (int)(1LL * fact[i - 1] * i % MOD);
    invfact[K] = mod_pow(fact[K], MOD - 2);
    for (int i = K; i >= 1; i--) invfact[i - 1] = (int)(1LL * invfact[i] * i % MOD);

    auto C = [&](int N, int R) -> int {
        if (R < 0 || R > N) return 0;
        return (int)(1LL * fact[N] * invfact[R] % MOD * invfact[N - R] % MOD);
    };

    vector<int> c(K + 1), d(K + 1);
    for (int j = 0; j <= K; j++) {
        int v = C(K, j);
        if (((K - j) & 1) != 0) v = (v == 0 ? 0 : MOD - v);
        c[j] = v;
        d[K - j] = v;
    }

    vector<int> A = a;
    vector<int> convA = convolution(A, d);
    vector<int> r(M);
    for (int i = 0; i < M; i++) {
        r[i] = convA[i + K];
    }

    vector<int> B(2 * n);
    for (int i = 0; i < 2 * n; i++) B[i] = b[i % n];
    vector<int> convB = convolution(B, d);

    int needLen = n + M - 1;
    vector<int> seq(needLen);
    for (int s = 0; s < needLen; s++) {
        seq[s] = convB[s + K];
    }

    vector<long long> combo;
    combo.reserve(M + 1 + needLen);
    for (int v : r) combo.push_back(v);
    combo.push_back(-1);
    for (int v : seq) combo.push_back(v);

    vector<int> z = z_function(combo);

    for (int x = 0; x < n; x++) {
        int pos = M + 1 + x;
        if (z[pos] >= M) {
            cout << x << '\n';
            return 0;
        }
    }

    cout << -1 << '\n';
    return 0;
}

HackerRank Algebra – Minimal Cyclic Shift