TRISWP - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: mexomerf
Tester: jay_1048576
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You have a string S.
In one move, you can choose an index i (1 \leq i \leq |S|-2), and left-rotate the substring S_iS_{i+1}S_{i+2}, turning it into S_{i+1}S_{i+2}S_i.

How many distinct strings can be obtained by performing this operation exactly once?

EXPLANATION:

Let’s look at three consecutive characters starting from index i, and how rotating them changes the string.
There are three cases.

  • S_i = S_{i+1} = S_{i+2}, i.e all three are the same.
    In this case, rotating them effectively changes nothing.
  • S_i, S_{i+1}, S_{i+2} are all distinct (for example abc).
    In this case, a left rotation will change the values at all three indices.
  • Some two of the three characters are equal, and the third is not equal to them.
    In this case, there are again three possibilities:
    1. S_i = S_{i+1}, like aab. In this case, a left rotation changes the values of indices i+1 and i+2.
    2. S_i = S_{i+2}, like aba. In this case, a left rotation changes the values of indices i and i+1,
    3. S_{i+1} = S_{i+2}, like baa. In this case, a left rotation changes the values of indices i and i+2.

Analyzing all the cases, it can be seen that:

  • The “all three equal” case doesn’t change S at all, and is the only type that can attain this.
    However, applying it at different indices give the same final string; so this case adds either zero or one to the answer, depending on whether such a triple exists at all.
  • The “all distinct” case is the only one that changes three indices; and each such one will result in a different string since a different set of indices will be changed.
    So, for each such type, add 1 to the answer.
  • The baa case is the only one that changes two spaced-out indices (i and i+2).
    So, for each such type, add 1 to the answer.
  • The aba and aab cases can overlap - for example as seen in aaba, where rotating either the first or the second length-3 substring will result in abaa.
    If there is no overlap, each occurrence of this type will result in a distinct final string.
    To account for this,
    • Add 1 to the answer for each occurrence of type aba.
    • Add 1 to the answer for each occurrence of type aab that’s not immediately followed by aba.
      This ensures that for each ‘overlap’, we add only 1 to the answer and not 2.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Tester's code (C++) 
/*...................................................................*
 *............___..................___.....____...______......___....*
 *.../|....../...\........./|...../...\...|.............|..../...\...*
 *../.|...../.....\......./.|....|.....|..|.............|.../........*
 *....|....|.......|...../..|....|.....|..|............/...|.........*
 *....|....|.......|..../...|.....\___/...|___......../....|..___....*
 *....|....|.......|.../....|...../...\.......\....../.....|./...\...*
 *....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
 *....|.....\...../.........|....|.....|.......|.../........\...../..*
 *..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
 *...................................................................*
 */
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007

string shift(string s,int i)
{
    char a=s[i],b=s[i+1],c=s[i+2];
    s[i]=b,s[i+1]=c,s[i+2]=a;
    return s;
}

void solve(int tc)
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans=n-2,cnt=0;
    for(int i=0;i<n-2;i++)
    {
        if(i<n-3 && s[i]==s[i+1] && s[i]==s[i+3])
            ans--;
        else if(s[i]==s[i+1] && s[i]==s[i+2])
        {
            ans--;
            cnt++;
        }
    }
    cout << ans+min(1ll,cnt) << '\n';
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc=1;
    cin >> tc;
    for(int ttc=1;ttc<=tc;ttc++)
        solve(ttc);
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    ans = 0
    same = 0
    for i in range(n-2):
        st = {s[i], s[i+1], s[i+2]}
        if len(st) == 1: same = 1
        elif len(st) == 3: ans += 1
        else:
            if i == 0 or s[i] != s[i+2] or s[i] != s[i-1]: ans += 1
    print(ans+same)
1 Like
2

So sad, I thought we didn’t need to add string in which we can’t shuffle when s[i] = s[i+1] = s[i+2] since that’s the initial string and that was not counted in example test cases but it is actually also generated after operation -_-

2 Likes
4

same bro :cry:

2 Likes
5

Problem: Triangular Swaps

My Approach: increase ans++ in only two cases not matched. Case:1 → s[i] == s[i+1] && s[i] == s[i+2] and Case:2 → s[i] == s[i+1] && s[i] == s[i+3]. It’ll not get SIGSEV because that edge case has been taken care of.

Issues: It just got wrong on the second answer. What’s wrong in my approach? Can anyone help me to identify?

Code:

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

int n;
bool skip(string &str, int i)
{
    if (str[i] == str[i + 1] && str[i] == str[i + 2])
        return 1;

    if (i < n - 3 && str[i] == str[i + 1] && str[i] == str[i + 3])
        return 1;

    return 0;
}

void solve()
{
    cin >> n;

    string str;
    cin >> str;

    vector<string> strings;
    strings.push_back(str);

    int ans = 0;
    for (int i = 0; i < n - 2; i++)
    {
        if (!skip(str, i))
             ans++;
    }

    cout << ans;
}

int main()
{
    int t;
    cin >> t;

    while (t--)
    {
        solve();
        cout << '\n';
    }

    return 0;
}
1 Like
6

I got my answer. Actually, aaa is also a distinct string. I ignore this case. so for every s1 == s2 == s3, need to count just 1. That’s it.

Updated Code:

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

int n;
bool skip(string &str, int i)
{
    if (str[i] == str[i + 1] && str[i] == str[i + 2])
        return 1;

    if (i < n - 3 && str[i] == str[i + 1] && str[i] == str[i + 3])
        return 1;

    return 0;
}

void solve()
{
    cin >> n;

    string str;
    cin >> str;

    vector<string> strings;
    strings.push_back(str);

    int ans = 0, addOne = 0;
    for (int i = 0; i < n - 2; i++)
    {
        if (str[i] == str[i + 1] && str[i] == str[i + 2])
            addOne = 1;
        if (!skip(str, i))
            ans++;
    }

    cout << ans + addOne;
}

int main()
{
    int t;
    cin >> t;

    while (t--)
    {
        solve();
        cout << '\n';
    }

    return 0;
}
7

baoooo niice question just missed that edge case of all equalssss