BLAST3 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: pols_agyi_pols
Tester & Editorialist: iceknight1093

DIFFICULTY:

1699

PREREQUISITES:

Observation

PROBLEM:

You’re given a string S of length N.
In one move, you can delete a substring of length 3 from it.
Is it possible to obtain a non-empty palindrome by performing this operation several times?

EXPLANATION:

Let’s think about this problem in reverse: suppose we end up with a palindrome — can we say anything about it?

In particular, suppose we end up with a palindrome P of length K. Then,

  • If K \geq 7, we can use our operation to delete the first 3 and last 3 characters of P to obtain a shorter one, of length K - 6.
    This means it’s enough to check if it’s possible to obtain a palindrome of length \leq 6.
  • In fact, we can reduce this even further:
    • If K = 4, delete the first three characters and we’re left with a length-1 string; which is a palindrome.
    • If K = 5, delete the middle three characters to obtain a length-2 palindrome.
    • If K = 6, delete the second, third, fourth characters to obtain a length-3 palindrome.
  • Together, this tells us that we only really need to check whether a palindrome of length \leq 3 can be obtained.

Now, notice that the length of the string doesn’t change modulo 3, since we delete three characters at a time.
So, whether we need to check for length = 1, 2, or 3 is uniquely determined by the value of N modulo 3.
Let’s look at what happens for different values of N. There are three cases here.

Case 1

Case 1: N = 3x+1 for some x
Here, it’s always possible to obtain a palindrome: keep the first character and delete the remaining ones.

Case 2

Case 2: N = 3x+2 for some x.
Here, we need to check whether a length-2 palindrome can exist.
Suppose i and j are the indices remaining in the end, and everything else is deleted. Then,

  • We should have S_i = S_j.
  • Everything before i has to be deleted, so the number of characters before i should be a multiple of 3.
    That is, i = 3k_1 + 1 for some integer k_1, or i \bmod 3 = 1.
  • Everything after j has to be deleted, so the number of characters after j should also be a multiple of 3.
    That is, j \bmod 3 = N\bmod 3.
  • If the above two conditions are satisfied, the condition N = 3x+2 means that the number of
    characters between i and j will also be a multiple of 3, so everything inbetween can be deleted.

Checking whether some valid i and j exist isn’t too hard.

  • First, fix a character c, and consider only positions containing c.
  • Find the leftmost i such that S_i = c and i\bmod 3 = 1.
  • Find the rightmost j such that S_j = c and j\bmod 3 = N\bmod 3.
  • If i \leq j, we’ve found a valid pair for this character.

This can be implemented in \mathcal{O}(N), though straightforward \mathcal{O}(26\cdot N) is also fast enough.

If a valid pair is found for any character, the answer is Yes.
If the check fails for all characters, the answer is No.

Case 3

Case 3: N = 3x for some x.
This is in fact basically the same as case 2 above.

Here, we need to check whether a valid length-3 palindrome can be formed.
However, the middle character doesn’t matter much - it can be anything.
So, once again if we’re able to find indices i and j such that:

  • i \leq j and S_i = S_j
  • Everything before i and everything after j can be deleted

we’ll be done, because the number of characters between such i and j will be 1 modulo 3; meaning we can delete all but one of them.

The exact same \mathcal{O}(26\cdot N) algorithm to compute i and j as case 2 will work here.

As for implementation, note that the actual algorithm is exactly the same across all three cases: so you don’t actually need to perform any casework to implement it.

TIME COMPLEXITY

\mathcal{O}(N) or \mathcal{O}(26\cdot N) per testcase.

CODE:

Author's code (C++, O(26N)) 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    ll kitne_cases_hain;
    kitne_cases_hain=1;
    //freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
    cin>>kitne_cases_hain;
    while(kitne_cases_hain--){          
        ll n;
        cin>>n;
        string s;
        cin>>s;
        if((n%3)==1){
            cout<<"YES\n";
            continue;
        }
        ll flag=0;
        ll l,r;
        for(int i=0;i<26;i++){
            l=0;r=0;
            for(int j=0;j<n;j++){
                if((s[j]-'a')==i && (j%3)==0){
                    l=j+1;
                    break;
                }
            }
            for(int j=n-1;j>0;j--){
                if((s[j]-'a')==i && ((n-1-j)%3)==0){
                    r=j+1;
                    break;
                }
            }
            if(r>l && l!=0){
                flag=1;
                break;
            }
        }
        if(flag){
            cout<<"YES\n";
        }else{
            cout<<"NO\n";
        }
    }
	return 0;
}
Editorialist's code (Python, O(N)) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    left, right = [n]*26, [-1]*26
    for i in range(n):
        ch = ord(s[i]) - ord('a')
        if i%3 == 0: left[ch] = min(left[ch], i)
        if (n-1-i)%3 == 0: right[ch] = i
    print('Yes' if sum(left[i] <= right[i] for i in range(26)) > 0 else 'No')
2 Likes