Problem Link : CodeChef: Practical coding for everyone
First, notice the fact that changing the direction of word doesn’t affect the number of individual characters in a row.
In a particular row, the pattern of string that can be possible are-
1)s[x,…,j], some part of a total string, or
2)s[x,…,end] + y * s[start,…,end] + s[start,…z], this can be other row pattern.
For eg, if the word would be CODE, then the 12th row of the pyramid would be:
DECODECODECO = DE + 2 * CODE + CO = s[3,…,end] + 2 * s[start,…,end] + s[1,…,2]
To implement this and to avoid TLE we will implement an array of size (length of string) * 26 to store the frequency of the characters for a particular substring.
Here is the code,
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll row; //height of pyramid
cin >> row;
string str;
cin >> str; //string with which pyramid is made
ll queries;
cin >> queries; //number of queries
ll len = str.length(); //length of string
ll arr[len][26]; //array in which frequency of each character upto a certain height is stored
memset(arr, 0, sizeof(arr));
for (ll i = 0; i < len; i++)
{
arr[i][str[i] - 'A']++;
}
for (ll i = 1; i < len; i++)
{
for (ll j = 0; j < 26; j++)
{
arr[i][j] += arr[i - 1][j];
}
}
while (queries--)
{
ll x;
char ch;
cin >> x >> ch;
ll char_num = 1;
if (x % 2 == 0)
{ //as x can be 10^18 so multiplication is not as such possible
ll a = x / 2;
ll b = x - 1;
a %= len; //so firstly modulus is taken
b %= len;
char_num = (a * b) % len;
}
else
{
ll a = (x - 1) / 2;
ll b = x;
a %= len;
b %= len;
char_num = (a * b) % len;
}
ll ind = (char_num % len) + 1;
ll ans = 0;
ll min_ = min(len - ind, x - 1);
ans += arr[min_ + ind - 1][ch - 'A']; //end substring i.e. s[x,...,end]
if (ind >= 2)
{
ans -= arr[ind - 2][ch - 'A'];
}
x -= (min_ + 1);
ll q = x / len;
ans += q * arr[len - 1][ch - 'A']; //number of strings present i.e. w * s[start,...,end]
q = x % len;
if (q != 0)
ans += arr[q - 1][ch - 'A']; //start of a string i.e. s[start,...,y]
cout << ans << "\n";
}
return 0;
}