# SMILEY - Editorial

Author: ro27
Tester: jay_1048576
Editorialist: iceknight1093

1371

None

# PROBLEM:

A Schrödinger’s Smiley is a string that consists of a ':', followed by several ')' (but at least one), followed by another ':'.
For example, :):, :))):, :))))): are Schrödinger’s Smileys.

Given a string S, find the number of its strings that are Schrödinger’s Smileys.

# EXPLANATION:

This is, for the most part, an implementation task — checking each substring in \mathcal{O}(N^2) will be too slow, so a faster solution is necessary.

There are a couple of different observations that can be made here, leading to different implementations.

Method 1

One observation that can be made is that is two adjacent characters in the string are equal, we can remove one of them: it won’t affect the answer at all since smileys don’t care about how many ')' there are.

So, we can create a reduced string R with the same answer as the original string, which has the property that no adjacent characters are equal.
To create R in \mathcal{O}(N), the following algorithm can be used:

• Initially, let R be empty.
• For each i from 1 to N:
• If R is not empty and S_i equals the last character of R, do nothing.
• Otherwise, append S_i to R.

Computing the answer on this reduced string in \mathcal{O}(N) is easy: notice that the only possible Schrödinger’s Smiley in it is :):, so just check every substring of length 3.

Method 2

Another observation that can be made is that a Schrödinger’s Smiley can only occur between two consecutive occurrences of ':' in S.

So, we can store the positions of all the occurrences of ':' in S, then only check substrings that are between consecutive occurrences.
That is,

• Let \text{pos} be a list of positions of occurrences of ':' in S.
• Then, check the substrings [\text{pos}_1, \text{pos}_2], [\text{pos}_2, \text{pos}_3], [\text{pos}_3, \text{pos}_4], \ldots

This obviously takes \mathcal{O}(N) time since all the substrings we’re checking are disjoint.

# TIME COMPLEXITY

\mathcal{O}(N) per testcase.

# CODE:

Author's code (Method 1 - C++)
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key(a)  -> gives index of the element(number of elements smaller than a)
// find_by_order(a) -> gives the element at index a
#define accelerate ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int        long long int
#define ld         long double
#define mod1       998244353
#define endl       "\n"
#define ff         first
#define ss         second
#define all(x)     (x).begin(),(x).end()
#define ra(arr,n)  vector<int> arr(n);for(int in = 0; in < n; in++) {cin >> arr[in];}

const int mod = 1e9 + 7;
const int inf = 1e18;
int MOD(int x) {int a1 = (x % mod); if (a1 < 0) {a1 += mod;} return a1;}
int power( int a,  int b) {
int p = 1; while (b > 0) {if (b & 1)p = (p * a); a = (a * a)  ; b >>= 1;}
return p;
}

void lessgoo()
{
int n;
cin >> n;
string s;
cin >> s;
string ans = "";
ans += s[0];
for (int i = 1; i < s.size(); i++) {
if (s[i] != ans.back()) {
ans += s[i];
}
}
int cnt = 0;
if (ans.size() < 3) {
cout << 0 << endl;
return;
}
// cout << ans << endl;
for (int i = 0; i <= ans.size() - 3; i++) {
if (ans[i] == ':' && ans[i + 2] == ':' and ans[i + 1] == ')')cnt++;
}
cout << cnt << endl;
}
signed main()
{
accelerate;

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

int test = 1;
cin >> test;
for (int tcase = 1; tcase <= test; tcase++)
{
// cout << "Case #" << tcase << ": ";
lessgoo();

}
return 0;
}

Tester's code (Method 2 - C++)
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007

void solve(int tc)
{
int n;
cin >> n;
string s;
cin >> s;
int ans = 0;
for(int i=0;i<n;i++)
{
if(s[i]==':')
{
bool ok = true;
int j = i+1;
for(;j<n;j++)
{
if(s[j]==':')
break;
else if(s[j]=='(')
ok = false;
}
if(j<n && j!=i+1 && ok)
ans++;
}
}
cout << ans << '\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 (Method 1 - Python)
for _ in range(int(input())):
n = int(input())
s = input()
reduced = ''
for c in s:
if not reduced or c != reduced[-1]: reduced += c
ans = 0
for i in range(len(reduced)):
if i+3 > len(reduced): break
ans += reduced[i:i+3] == ':):'
print(ans)

3 Likes