×

# VOWELDP - editorial

Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah

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
class some
{
public static int[]arr;
public static long[,]dp;
public static int mod;
public static void Main()
{
mod=1000000007;//mod value
for(int t=0;t<n;t++)//run on test cases
{
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.

1398
accept rate: 0%

19.5k348496535

 3 Here's a much simpler solution . :) Think of it like this - You have M balls and you have to distribute them into n boxes such that each box gets atleast one ball. What is the number of ways you can do this ? After a bit of thinking you will come up with an answer as C(M-1,N-1). (Here C(a,b) represents number of Combinations of a items taken b at a time.) Example- 5 2 1 2 1 babababa Now relate this problem with the above Contest Problem . So in the string G (in the example provided above) you have 4 places where there is 'a' and you have 5 'a' in your hand to distribute them . Thus 5 'a' has to be distributed among 4 places such that each place has atleast 1 'a' . In how many ways can you do this ? C(5-1,4-1) = C(4,3) Similarly find for e,i,o,u and take their product . Remember to Keep the Mod. Edge But what if you have M balls and no places to keep it ... for this nothing is to be multiplied with the product. i.e. you dont need to find C(M-1,0) coz it will be 1 If the number of places is 1 and the number of balls is also 1 ? in this case also you dont need to find the number of combinations as it will be 1 only . i.e. C(1,1)=1 So you only need to C(a,b) for this whose a>=1 && b>=2 . (This has been done to reduce the number of computations). Here is My solution - https://www.codechef.com/viewsolution/15142052 If you like my Solution, Give a THUMBS UP. answered 27 Aug '17, 20:15 602●1●5 accept rate: 8% nice man! I don't have enough reputation to upvote, though I would like to :) (20 Sep '17, 09:38) Good alternate solution :p (25 Mar, 17:10)
 0 For speedup in calculation of nCr look at this tutorial of Dynamic Programming Solution specially for Python users :p answered 25 Mar, 18:35 228●10 accept rate: 2%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,026
×3,458
×1,897
×1,082
×161
×18
×3

question asked: 30 Mar '16, 16:18

question was seen: 1,335 times

last updated: 25 Mar, 18:35