MRCHORD - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Given a string S consisting of only L and R, we have the following movement rules from position x:

  • If S_x = L, move two steps left.
  • If S_x = R, move one steps right.

You’re given an array A of length N such that A_i denotes your ending position, if you start at i and follow the movement rules exactly N times.
Determine if there exists any valid string S such that S_1 = S_2 = R and S_N = L such that following it results in A.

EXPLANATION:

We want S_1 = S_2 = R and S_N = L.

Let’s look at what happens if we start from x = 1.
From them, we’ll repeatedly move one step right over and over again, till we reach an index i such that S_i = L.
At that point, we’ll move two steps left to i-2; and then we’ll end up in a cycle because from i-2 and i-1 we’ll move right, while from i we move two steps left.
So, if i is the first index such that S_i = R, starting at 1 we’ll end up in the cycle i \to (i-2) \to (i-1) \to i \to \ldots

We must move exactly N times, so it’s easy to compute where we end up: we require i-1 moves to reach i; and then we cycle through (i, i-2, i-1) so we know need to know the number of remaining moves modulo 3 (that is, (N-i+1) \bmod 3).

Next, let’s look at starting from x = 2.
Observe that the same analysis as starting from x = 1 holds here: we’ll move right till i is reached, and then repeatedly follow the cycle (i, i-2, i-1).
The one difference is that we’re always exactly one step ‘ahead’ of where we’ll be if we’d started at 1.
That is, if when starting at 1 we end up at i, then starting at 2 we’ll be one step ahead and end up at (i-2) instead; and so on.

Similar analysis applies to starting from x = 3: we’ll end up in the same (i, i-2, i-1) cycle, but one step ahead of starting from x = 2 (and so two steps ahead of x = 1).

Next, consider x = 4 (for now, assume i \ge 4).
Note that here we’ll again end up in the same (i, i-2, i-1) cycle; in fact we’ll end up exactly where we ended up when starting from x = 1.

This should showcase what the general pattern on the prefix till i (recall that i is the leftmost L in the string) looks like:
A_1, A_2, A_3 will all be distinct (and consecutive) positions on the cycle (i, i-2, i-1), depending on the value of (N-i+1) \bmod 3.
Thereafter, for each 4 \le j \le i, we’ll simply have A_j = A_{j-3}, i.e. the pattern is periodic with length 3.

We now know that some prefix has to be periodic with length 3.
However, we only know A - luckily, it’s quite easy to deduce i, since it’ll simply equal \max(A_1, A_2, A_3).

So, knowing A_1, A_2, A_3, we can find the first occurrence of L in the string; and also verify validity upto this point (via periodicity modulo 3).

Let this first occurrence of L be at index i_1.
We now need to analyze values at indices \gt i_1.
Observe that:

  • If S_{i_1 + 1} = L, then from i_1 + 1 we’d move two steps left to end up at i_1 - 1, at which point we end up in the cycle [i_1-2, i_1-1, i_1] anyway.
    Since this is after one step, this is equivalent to starting from index i_1 - 2 instead.
    So, in this case, we’d just have A_{i_1+1} = A_{i_1 - 2}.
  • If S_{i_1 + 1} = R, then we’d move one step right.
    Let’s then look at index i_1 + 2.
    • If S_{i_1 + 2} = L, we move two steps left, ending up at index i_1 (which is part of the 3-cycle).
      This is after two steps; so it’s equivalent to starting from index i_1-2 instead.
      Again, we obtain A_{i_1+1} = A_{i_1-2}.
    • If S_{i_1 + 1} = R instead, we take another step right.
      Observe that after this, we’ll never return to the [i_1-2, i_1-1, i_1] cycle again - we’ll end up in some cycle to its right instead.

So, either we must have A_{i_1+1} = A_{i_1-2} (which, you might notice, continues the periodicity modulo 3); or we break out of the [i_1-2, i_1-1, i_1] cycle entirely.

Further, if we do have A_{i_1+1} = A_{i_1 - 2}, the exact same analysis can be applied to the next index too: that is, we’ll either have A_{i_1 + 2} = A_{i_1-1}, or we’ll end up breaking out of the cycle.

More generally: the periodicity modulo 3 will continue on for a while after index i_1; till we eventually break out of it.

The next question is: what happens when we break out of the cycle containing i_1?
It’s not hard to see that this happens exactly when we have two consecutive occurrences of R, i.e S_j = S_{j+1} = R for some index j \gt i_1.
However, observe that now the suffix S[j, N] of S is essentially an independent problem, since we can never move from any point there to a location \lt j.
So, we can simply treat this suffix as a new problem, and solve that!

This means we immediately obtain the following solution:

  • Look at \max(A_1, A_2, A_3) to obtain the first index in S that must contain L.
    Let this be i_1.
  • Then, find the largest integer k such that [A_1, A_2, \ldots, A_k] is 3-periodic; while also checking if (A_1, A_2, A_3) are the appropriate positions along the cycle [i_1-2, i_1-1, i_1].
  • Note that k \ge i_1 must hold, otherwise we run into issues.
  • If all the checks so far have passed, note that the suffix S[k+1, N] is now an independent problem; so just solve for the suffix, and so on.

This can be implemented in linear time, since we’re really just splitting the array A into several contiguous segments that are each 3-periodic, and checking the appropriate cycle condition for each one.

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; cin >> n;
        vector a(n, 0);
        for (int &x : a) {
            cin >> x;
            --x;
        }

        auto solve = [&] () {
            for (int i = 0; i < n; ) {
                if (i+2 >= n) return false; // Too few elements
                
                // check cycle
                for (int j = 0; j < 3; ++j) {
                    int d = a[i+(j+1)%3] - a[i+j];
                    if (d != 1 and d != -2) return false;
                }
                
                // check validity
                int pos = min({a[i], a[i+1], a[i+2]});
                if (pos < i) return false;
                
                // reach pos, then cycle
                int rem = n - (pos - i);
                rem %= 3;
                if (a[i] != pos + rem) return false;

                // check for periodic
                i += 3;
                while (i < n) {
                    if (a[i] != a[i-3]) break;
                    ++i;
                }
                
                // didn't reach cycle
                if (i <= pos+2) return false;
            }
            return true;
        };
        if (solve()) cout << "Yes\n";
        else cout << "No\n";
    }
}
1 Like
2
Forgot to check, 3-period elements should have gap of 1. Found error.

I have done exactly as editorial. can’t figure out error still …



#include <iostream>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <deque>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>


using namespace std;

#define F first
#define S second
#define MP make_pair
#define PB push_back
#define UB upper_bound
#define LB lower_bound
#define ER erase
#define EN end()
#define B begin()
#define I insert
#define OPTIMIZE ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int ll
#define endl "\n"
#define CO cout <<
#define CI cin >>
#define NL cout << endl;
#define DBG {int debug ; cin >> debug;}
#define AND &&
#define OR ||
#define XOR ^
#define OFLUSH fflush(stdout);
#define IFLUSH fflush(stdin);
#define LEN(x) ((int)x.length())

#define rep(i,x) for(int i = 0 ; i < x ; i++)
#define rep1(i,x) for(int i = 1 ; i <= x ; i++)

#define repl(var,start_val,limit_val) for(int var = start_val ; var <= limit_val ; var++)
#define perl(var,start_val,limit_val) for(int var = start_val ; var >= limit_val ; var--)

#define y1 qwert
#define y2 trewq
#define x1 asdfg
#define x2 gfdsa

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector< ii > vii;
typedef set<int> si;
typedef multiset<int> msi;
typedef long double ld;

const ll maxn = 5e5+6 ;
const ll MOD = 1e9 + 7 ;

/////////////////////////
// declaration section //
/////////////////////////
int n , m, k, H, a[maxn], ans[maxn];
int fact[1], ifact[1];

string s;
vi g[maxn];

set<string> ms;

void getInput() {
    cin >> n;
    repl(i,1,n) cin >> a[i];
}

ii getSegmentFromIndex(int startIndex) {
	/*
		Step 1 : Find 3-periodicity range, and 3 periodic elements
		Step 2 : Check if these elements are repeating as expected [small, mid, large, small, mid, large .... ] ( it can start from mid / large also )
		Step 3 : last, we find the sinkNode ( which is first L in range )
		Step 4 : effective steps are basically N % 3 . 
	*/

	set<int> s;
	ii ret = MP(-1,-1);
	// our expected 3-periodic range from [startIndex,lastGoodIndex], which we verify later
	int lastGoodIndex;

	// keep pushing in set, until size of set is within 3
	repl(i,startIndex,n) {
		if(s.size() < 3) s.I(a[i]);
		else if (s.find(a[i]) == s.end()) break;
		lastGoodIndex = i;
	}

	// if final set must be of size 3, otherwise, it is never possible.
	if (s.size() != 3) {
	return ret;
}

	// check if the pattern exists , converting set to vector.
	vi v(s.B,s.EN);

	int cur = 0;

	// found the Checking 3-periodicity from [startIndex, lastGoodIndex]
	while(v[cur] != a[startIndex])cur++;

	repl(i,startIndex,lastGoodIndex) {
		if(v[cur] != a[i]) return ret;
		cur++;
		if(cur == 3) cur = 0;
	}

	int sinkIndex = *s.rbegin();
	int effectiveSteps = n % 3;
	if(effectiveSteps == 0 && a[sinkIndex] != sinkIndex) return ret;
	if(effectiveSteps == 1 && a[sinkIndex] != sinkIndex-2) return ret;
	if(effectiveSteps == 2 && a[sinkIndex] != sinkIndex-1) return ret;
	if(sinkIndex <= startIndex+1 || sinkIndex > lastGoodIndex) return ret;

	ret.F = startIndex;
	ret.S = lastGoodIndex;

	return ret;
}

void solve() {
	repl(i,1,n) {
		auto p = getSegmentFromIndex(i);
		if (p.F == -1) {
			cout << "No" << endl;return;
		}
		i = p.S;
	}
	cout << "Yes" << endl;
}

signed main() {
    // factinit();
    // generatePrimes();

    // OPTIMIZE
    // freopen("in.txt" , "r" , stdin) ;
    //freopen("out.txt" , "w" , stdout) ;

    int t=1;
    cin >> t;
    while(t--)
        getInput() , solve();

	return 0;
}

Update : Found mistake, Darn it. I just had to check 3-period elements have gap of 1 consecutively… below check fixes the issue.

if(v[2]-v[0] != 2) {
		return ret;
	}