PATTERNG - Editorial

Problem Link : https://www.codechef.com/LICO2020/problems/PATTERNG

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;
}
1 Like