MODMIR - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: nikhil_010309
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given N and M, construct any array A of length N such that:

  • There exists at least one index i satisfying A_i \gt 0; and
  • For each i = 1, 2, \ldots, N, it holds that A_i = (A_{i-1} + A_{i+1}) \bmod M.

If no valid array exists, print -1 instead.

EXPLANATION:

The condition of A_i = (A_{i-1} + A_{i+1}) \bmod M can be rewritten into

A_{i+1} = (A_i - A_{i-1}) \bmod M

That is, each element depends on the previous two elements.

For convenience of notation, all addition and subtraction of elements below is assumed to be modulo M, and the (\bmod M) will be dropped.

A_0 = 0 is already fixed.
Suppose we also decide on some value for A_1.
Observe that this then fixes the entire rest of the array!
Specifically, we have:

  • A_2 = A_1 - A_0 = A_1
  • A_3 = A_2 - A_1 = A_1 - A_1 = 0
  • A_4 = A_3 - A_2 = 0 - A_1 = -A_1
  • A_5 = A_4 - A_3 = -A_1 - 0 = -A_1
  • A_6 = A_5 - A_4 = -A_1 - (-A_1) = 0
  • A_7 = A_6 - A_5 = 0 - (-A_1) = A_1
    \vdots
    and the pattern repeats.

That is, upon fixing A_1, the array will be periodic, following the pattern [0, A_1, A_1, 0, -A_1, -A_1, 0, A_1, A_1, \ldots] over and over again.

The other restrictions we have are that A_{N+1} = 0 must hold, and that the array must contain at least one non-zero element.
For the non-zero element, note that if A_1 \ne 0 then the condition trivially holds; while if A_1 = 0 then the periodicity guarantees that every element will be 0.
So, we just need to ensure that we choose some non-zero A_1.

Next, looking at the above pattern, it will have a 0 at position N+1 if and only if N+1 is a multiple of 3, because the zeros are at indices 0, 3, 6, 9, \ldots

So,

  • If N+1 is not a multiple of 3, no solution exists.
  • If N+1 is a multiple of 3, we can choose any non-zero value of A_1 and then form the array [0, A_1, A_1, 0, -A_1, -A_1, \ldots] as a solution.
    • For example, choosing A_1 = 1 gives the array [0, 1, 1, 0, M-1, M-1, \ldots] which works.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

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

    int t; cin >> t;
    while (t--) {
        int n, m; cin >> n >> m;
        if ((n+1) % 3 != 0) {
            cout << -1 << '\n';
            continue;
        }

        vector ans(n+1, 0);
        ans[1] = 1;
        for (int i = 2; i <= n; ++i) {
            ans[i] = (ans[i-1] - ans[i-2] + m) % m;
        }

        for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
        cout << '\n';
    }
}