SMILEY - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: ro27
Tester: jay_1048576
Editorialist: iceknight1093

DIFFICULTY:

1371

PREREQUISITES:

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