AOC05-Editorial

editorial
, ,
1

PROBLEM LINK:

contest

Author: Dharsan R

DIFFICULTY:

EASY

PREREQUISITES:

Dynamic Programming

PROBLEM:

Given two strings S and P,you have to find the parity of the number of substrings T in S such that T and P are Twins. Two strings are said to be twins if the sum of value of the letters in the string are same. The value of a letter is their respective postion in the list of 26 alphabets

EXPLANATION:

The naive approach to this problem is to perform brute force and consider all (N*(N-1))/2 substrings in S. Find the value of each substring and compare with the value of P,and increment the counter accordingly. This can be done in O(N^3) complexity, with some preprocessing , the same can be done in O(N^2).

An efficient way to solve this is to use Dynamic programming (DP).Let K be the value of the string P. K can be obtained in O(|P|) time complexity.Now the idea is to initialize an array A where A[i] stores the sum of values of first i letters of string S.
Declare a map or dictionary M.Now for each i such that 1<=i<=N, update the value for A[i] as 1 in dictionary M with A[i] as the key. Also make the value for 0 in dictionary M as 1 with 0 as key.
Now let us consider two valid indices i and j (1<=i<=j<=N),the value of the substring T starting from i and ending at j is A[j]-A[i-1] if i!=1,otherwise the value will be A[j].
Using the above idea, let us consider a substring T ending at position j in S.The value of string T is A[j].Suppose A[j]>=K and if M[A[j]-K] is 1, it means that there is an index i such that 1<=i<=j and A[i]=A[j]-K, therefore the substring R in S starting from i+1 and ending at j will have an value of K (i.e; R is a twin string of P). Now declare and initialize a counter C as 0 and run a loop for all 1<=j<=N, if there exists an R ending at position j satisfying the above conditions, then increment the counter C by 1.The counter variable C will give us the number of twin strings of P in S and check the parity of C.

TIME COMPLEXITY

O(|S|+|P|)=O(N) as |S|=N and |P|<=|S|.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
#include<math.h>
#include<string.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t,n,k,x;
	string s,p;
	cin>>t;
	while(t--)
	{
	    cin>>n;
	    cin>>s;
	    cin>>p;
	    map<int,int> m;
	    int a[n],k=0,c=0;
	    for(int i=0;i<p.length();i++)
	        k+=p[i]-96;
	    a[0]=s[0]-96;
	    if(a[0]==k)
	        c++;
	    m[a[0]]++;
	    m[0]++;
	    for(int i=1;i<n;i++)
	    {
	        a[i]=a[i-1]+(s[i]-96);
	        m[a[i]]++;
	        if(a[i]>=k)
	            if(m[a[i]-k]>0)
	                c++;
	    }
	    if(c%2==0)
	        cout<<"GRYFFINDOR\n";
	    else
	        cout<<"SLYTHERIN\n";
	}
	return 0;
}
4 Likes