SEDPASS - Editorial

PROBLEM LINK:

Contest

Setter : Bhavyesh Desai
Tester : Rahul Dugar
Editorialist : Rajarshi Basu

DIFFICULTY:

Easy

PREREQUISITE:

Bitmasks

PROBLEM:

The notorious hacker group “Sed” managed to obtain a string S from their secret sources. The string contains only lowercase English letters along with the character ‘?’.

A substring of S is a contiguous subsequence of that string. For example, the string “chef” is a substring of the string “codechef”, but the string “codeh” is not a substring of “codechef”.

A substring of S is good if it is possible to choose a lowercase English letter C such that the following process succeeds:

  • Create a string R, which is a copy of the substring, but with each ‘?’ replaced by the letter c. Note that all occurrences of ‘?’ must be replaced by the same letter.
  • For each lowercase English letter:
    • Compute the number of times it occurs in S and the number of times it occurs in R; let’s denote them by A and B respectively. The ‘?’ characters in the original string S are ignored when computing A.
    • Check the parity of A and B. If they do not have the same parity, i.e. one of them is even while the other is odd, then this process fails.
  • If the parities of the number of occurrences in S and R are the same for each letter, the process succeeds.

For different substrings, we may choose different values of C.

Help Sed find the number of good substrings in the string S.

Constraints

  • 1 \le T \le 10^5
  • 1 \le S \le 10^5
  • S contains only lowercase English letters (‘a’ through ‘z’) and ‘?’
  • the sum of |S| over all test cases does not exceed 10^5

BRIEF EXPLANATION:

sm0l s0lution

Essentially, we check for all substrings. We keep track of the prefix parity using a bitmask. For every right index, we essentially want to count possible left indices. That can be done by just getting the number of prefix parity bitmasks that, when xorred with the current prefix bitmask, gives the bitmask of the parity of characters of entire string.

EXPLANATION:

Observation 1

First, we can represent all the parity information using a simple bitmask. One for each character, and one extra for parity of question marks.

Observation 2

Bitmasks also give us another advantage — we can xor them, which is commutative. Hence, we can keep track of prefix parities.

Observation 3 - Final Solution

Let the prefix bitmasks be represented by bitmask[i] meaning parity of all characters in s[1…i].

Checking for even occurances of ?

For checking substring with even number of ?, we just check how many occurances of the same bitmask[i] have occurred before …. but not exactly. What should we do?

Details

We should actually query with bitmask[i] \oplus bitmask[n] since we want our bitmask to match that of the entire string.

Checking for odd occurances of ?

Here, try to replace which each character (think how the bitmask to query changes, also remember to flip the bit representing the ?).

Intuition on why the methods are different

Essentially, the reason is even if we tried replacing in the bitmask while doing for even occurances, it would have given the same bitmask since we would not be changing any parities (even occurances of ? remember?). Hence, we would repeatedly count the same bitmasks again and again, which is overcounting. This will not happen in the odd case.

See Codes for exact implementation details.

SOLUTION:

Tester’s Code
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
 
int suss=0;
void solve() {
	string s=readStringLn(1,100000);
	suss+=sz(s);
	assert(suss<=100000);
	int btc=0;
	for(char i:s) {
		assert(('a'<=i&&i<='z')||i=='?');
		if(i!='?')
			btc^=(1<<(i-'a'));
	}
	map<int,int> socool;
	int xooo=0;
	socool[0]=1;
	int ans=0;
	for(char i:s) {
		if(i!='?')
			xooo^=(1<<(i-'a'));
		else
			xooo^=(1<<26);
		ans+=socool[xooo^btc];
		for(int i=0; i<26; i++)
			ans+=socool[xooo^(1<<26)^(1<<i)^btc];
		socool[xooo]++;
	}
	cout<<ans<<endl;
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(7);
	int t=readIntLn(1,100000);
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
#ifdef rd
//	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}

VIDEO EDITORIAL:

6 Likes

A comparatively neater implementation for anyone interested :

AC_CODE
#include<bits/stdc++.h>
using namespace std ;
void solve(){
  string s ;
  cin >> s  ;
  long long n = s.size(),t=0,ans=0,p=0;
  map<int,int>mp ;mp[0]++;
  for(char x:s)
    if(x!='?')
      t^=(1<<(x-'a')) ;
  for(int i=0;i<n;i++){
    p^=((s[i]=='?')?(1<<26):(1<<(s[i]-'a')));
    for(int j=0;j<26;j++)
      ans+=mp[t^p^(1<<j)^(1<<26)] ;
    ans+=mp[t^p] ;mp[p]++ ;
  }
  cout << ans<< '\n' ;
}
signed main(){
  int TC  ;
  cin >> TC;
  while(TC--)
    solve() ;
}
8 Likes

Bro , can you explain the logic explained in editorial with the help of the test case. I am having hard time understanding the editorial.

https://www.codechef.com/viewsolution/40667452
One may also look at this implementation. Used bitset instead of int.

awesome video tutorial @bharatSingla

Can someone tell me why there are only 2 good substrings for

asfhaslskfak

I can find more than 2.
ex- ‘a’,‘l’,'h’etc

1 Like

“a” is not good because the number of ‘s’ is 0 (Even), while the number of ‘s’ in the main string is 3 (Odd). Similarly, you can see for other examples as well.

1 Like

How is it possible ?
I submitted my code during contest and it got TLE.
Today I submitted the same code in practice and it showed AC .
Can someone tell me what happened here ?
@rajarshi_basu ?

A relatively neat implementation of the above idea with intuitive C++ implementation using std::

1 Like

Thanks bro for the explanations.
Now I got it

‘asfhaslskfak’ I find only one good sub string which is ‘asfhaslskfak’ it self but why the answer is two …any one can explain regarding this

I guess “hasl” also satisfies.

Yes u r right I also observed that…thanks a lot bro

can some body help why this is giving WA
Code : Solution: 41137097 | CodeChef