https://www.codechef.com/TNP32020/problems/TNP303

PROBLEM LINK: https://www.codechef.com/TNP32020/problems/TNP303

Practice

Author: Setter’s name

Tester: Tester’s name

Editorialist: Editorialist’s name

DIFFICULTY : EASY

PREREQUISITES:

Nill

PROBLEM:

Given a string S consisting of only uppercase letters, find the number of substrings which start and end both in X.

QUICK EXPLANATION:

Since all the substrings (which should be counted) begin and end with ‘X’, we can ignore all the other characters. So just count the number of ‘X’s and print the number of subsets possible from the set of ‘X’s.

EXPLANATION:

We just want to know the number of substrings beginning and ending with ‘X’. That means we do not care for other characters. For any 2 ‘X’s we can make a substring, by making one the beginning element and other the end. So we need to find how many different pairs of ‘X’s can we find, for making substrings. It is directly connected with the number of ‘X’s we have.

For 0 ’X’s we can make 0 pairs. For 1 ’X’ we can make 0 pairs. For 2 ’X’ we can make 1 pair,

3 ‘X’s => 3 pairs

4 ’X’s => 6 pairs

and so on…

So for k ‘X’s we can make 1+2+3+…+(k-2)+(k-1) pairs.
But now we only consider those substrings which start with one ‘X’ and end with different ‘X’. But substrings starting and ending with the same ’X’ are possible. Infact, for every ‘X’, that itself will become a valid substring. So we have to add the number of ‘X’s to the answer we got earlier.

i.e. the total number of valid substrings is 1+2+3+…+ (k-2) + (k-1) + k (k=number of ‘X’s).

(You can use the equation n*(n+1)/2 to calculate the above result).

If you examine the answer, you will realise that it is same as the total number of substrings in a set of length k (excluding void subset).

SOLUTIONS:

Setter's Solution

#include

#include

#include

using namespace std;

int main() {

int T;

cin>>T;

while(T>0)

{

int n,ans=0,count=0; // count=number of ‘X’s

cin>>n;

string st;

cin>>st;

for(int i=0;i<n;i++)

{

if(st[i]==‘X’)

count++;

}

ans=count*(count+1)/2;

cout<<ans<<"\n";

T–;

}

return 0;

}

Tester's Solution

Same Person

Editorialist's Solution

Same Person