VOWMTRX - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: starc15
Tester: jay_1048576
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Basic combinatorics

PROBLEM:

Given a string S of length N, find the number of ways of partitioning it into substrings such that each resulting substring has exactly k vowels.

EXPLANATION:

Let \text{pos}_i denote the position of the i-th vowel in string S.

Let’s look at how we can partition S into substrings containing exactly k vowels.

  • The first k vowels must be in the same substring; and this substring cannot include the (k+1)-th vowel.
    So, the first ‘cut’ must be made after \text{pos}_k, but before \text{pos}_{k+1}.
    There are \text{pos}_{k+1} - \text{pos}_k such choices.
  • The next consecutive k vowels must be in the same substring.
    By the same reasoning as above, the second cut must thus be made after \text{pos}_{2k}, but before \text{pos}_{2k+1}.
    There are \text{pos}_{2k+1} - \text{pos}_{2k} choices here.
  • More generally, it’s easy to see that for the i-th cut, there are \text{pos}_{ik+1} - \text{pos}_{ik} choices.

Finally, note that each cut is independent of the others.
So, the total number of ways is just the product of all these numbers.

In particular, if the string has x\cdot k vowels, we need exactly x-1 cuts to separate them.
So, the answer will be

\left( \text{pos}_{k+1} - \text{pos}_k \right) \cdot \left( \text{pos}_{2k+1} - \text{pos}_{2k} \right) \cdot \ldots \cdot \left( \text{pos}_{(x-1)k+1} - \text{pos}_{(x-1)k} \right)

The \text{pos}_i values can be computed by just iterating across the string, so this algorithm takes \mathcal{O}(N) time.

TIME COMPLEXITY

\mathcal{O}(N) per testcase.

CODE:

Setter's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const ll M=1e9+7;

int main() {
    ll t; cin>>t;
    map<char,ll>vow={{'a',1},{'e',1},{'i',1},{'o',1},{'u',1}};
    while(t--){
        ll n,k; cin>>n>>k;
        string s; cin>>s;
        ll ans=1;
        ll prev=-1;
        ll ct=0;
        for (int i = 0; i < n; ++i)
        {
            if(vow[s[i]]){
                if(ct==0){
                    if(prev!=-1){
                        ans=(ans*(i-prev))%M;
                    }
                }
                ct++;
                if(ct==k){
                    ct=0;
                    prev=i;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
Tester's code (C++) 
/*...................................................................*
 *............___..................___.....____...______......___....*
 *.../|....../...\........./|...../...\...|.............|..../...\...*
 *../.|...../.....\......./.|....|.....|..|.............|.../........*
 *....|....|.......|...../..|....|.....|..|............/...|.........*
 *....|....|.......|..../...|.....\___/...|___......../....|..___....*
 *....|....|.......|.../....|...../...\.......\....../.....|./...\...*
 *....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
 *....|.....\...../.........|....|.....|.......|.../........\...../..*
 *..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
 *...................................................................*
 */
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007

void solve(int tc)
{
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> idx;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='a' || s[i]=='e' || s[i]=='i' || s[i]=='o' || s[i]=='u')
            idx.push_back(i);
    }
    int ans = 1;
    for(int i=k;i<idx.size();i+=k)
        ans = (ans*(idx[i]-idx[i-1]))%MOD;
    cout << ans << '\n';
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc=1;
    cin >> tc;
    for(int ttc=1;ttc<=tc;ttc++)
        solve(ttc);
    return 0;
}
Editorialist's code (Python) 
mod = 10**9 + 7
for _ in range(int(input())):
    n, k = map(int, input().split())
    ans, vowels, curlen = 1, 0, 0
    for c in input():
        if c in 'aeiou':
            if vowels%k == 0 and vowels > 0:
                ans *= curlen
                ans %= mod
            curlen = 1
            vowels += 1
        else:
            curlen += 1
    print(ans)
1 Like
2

what’s wrong in this code, it is showing RE (SIGSEGV) error can someone please help:

#include <bits/stdc++.h>
using namespace std;

using ll = long long int;

const ll mod = 1e9 + 7;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

ll t;
cin>>t;
while(t--){
    ll n,k;
    cin>>n>>k;
    
    string s;
    cin>>s;
    
    vector<ll> v;
    
    ll count = 0;
    for(ll i=0; i<n; i++){
        if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u'){
            count++;
            if(count == k){
                count = 0;
                i++;
                ll in_between = 0;
                while(s[i] != 'a' && s[i] != 'e' && s[i] != 'i' && s[i] != 'o' && s[i] != 'u' && i<n){
                    in_between++;
                    i++;
                }
                if(i<n){
                    v.push_back(in_between+1);
                }
                i--;
            }
        }
    }
    
    // cout<<"vector : ";
    // for(int i=0; i<v.size(); i++){
    //     cout<<v[i]<<" ";
    // }
    // cout<<endl;
    
    int ans = v[0];
    for(int i=1; i<v.size(); i++){
        ans = ((ans%mod) * (v[i]%mod))%mod;
    }
    
    cout<<ans<<endl;
    
}
return 0;

}

4

You are getting RE on this TC
1 1
a

6

Acc to me you are getting RE for (int ans = v[0]). What if your vector is empty.

7

The solution to this code is slightly incorrect. For the case where the number of vowels is exactly equal to k, the answer should be 0. But the answer according to editorial code, comes out to be 1 which is clearly incorrect since you cannot slice the string into 2 pieces when there are exactly k vowels.
My code didn’t get accepted yesterday for the same reason :slightly_frowning_face:

1 Like