PROBLEM LINK:
Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah
DIFFICULTY:
SIMPLE
PREREQUISITES:
Dynamic Programming,
PROBLEM:
Given a word without contiguous vowels, you have to print the count of ways to write the word by repeating the vowels in the positions. The count of vowels to be repeated would be given.
QUICK EXPLANATION:
You can calculate for each vowel the count of ways to write them and multiply each. The count of each vowel can be calculated using dp wherein you have slots and count of the current vowel as states, adding every time a new way is found.
EXPLANATION:
Given a word without contiguous vowels, you have to print the ways in which you can print the word repeating the vowels contiguously, so that all vowels given are used up, except those not present in the word. Now, you can count the ways to use a then e then i then o then u whichever is present and multiply the result in each case which would be the answer. How would you calculate the ways to use each vowel. A possible solution is doing a dp and taking two states, one of how many slots or positions within consonants is there and how many total vowels are there. Then have a counter and add to the counter using up available vowels using a for loop. Refer code below
using System;//headers
using System.Collections.Generic;//headers
class some
{
public static int[]arr;
public static long[,]dp;
public static int mod;
public static void Main()
{
int n=Int32.Parse(Console.ReadLine());
mod=1000000007;//mod value
for(int t=0;t<n;t++)//run on test cases
{
string[]ss=Console.ReadLine().Split();//input
arr=new int[5];//array arr contains count of each vowel
for(int i=0;i<ss.Length;i++)
{
arr[i]=Int32.Parse(ss[i]+"");
}
string word=Console.ReadLine();//word is the word G
int[]given=new int[5];//given is the count of each vowel in given word G, each would be separated by a consonant, since there wouldn't be any repeated contiguous vowels.
char[]vowels="aeiou".ToCharArray();
foreach(char c in word)//in this loop we count the vowels in G
{
if(Array.IndexOf(vowels,c)<0)continue;
given[Array.IndexOf(vowels,c)]++;
}
long tt=1;
dp=new long[500,500];
for(int i=0;i<500;i++)for(int j=0;j<500;j++)dp[i,j]=-1;//initializing dp array
for(int i=0;i<given.Length;i++)
{
if(given[i]==0)continue;//if there is no vowel then we continue
tt*=solve(given[i],arr[i]);//here given[i] is count of slots (places) for that vowel and arr[i] is the count of that vowel available...please look at solve function
tt%=mod;//we mod it
}Console.WriteLine(tt);//print the value
}
}
public static long solve(int slots,int total)//slots is the count of places for the vowel and total is count of the vowel available
{
if(slots==1)return 1;//if there is only 1 slot left we return 1 cause all vowels need to be used up
if(dp[slots,total]!=-1)return dp[slots,total];//standard dp memory returning
long count=0;//count is the count of ways we can print that vowel
for(int i=1;i<=total-slots+1;i++)//we iterate from 1 to total-slots left
{
count+=solve(slots-1,total-i);//we decrease the slot and decrease total by i and add every possible way to do it.
count%=mod;//we mod here too
}
return dp[slots,total]=count;//return the count and store value in dp memory too
}
}
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found above.
Tester’s solution can be found above.
