VOWELDP - editorial

chandubaba
dynamic-programming
easy
editorial
keteki
simple
voweldp

#1

PROBLEM LINK:

Practice
Contest

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*=Int32.Parse(ss*+"");
				}
				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*==0)continue;//if there is no vowel then we continue
					tt*=solve(given*,arr*);//here given* is count of slots (places) for that vowel and arr* 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.


#2

Here’s a much simpler solution . :slight_smile:

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.


#3

For speedup in calculation of nCr look at this tutorial of Dynamic Programming Solution specially for Python users :stuck_out_tongue:


#4

nice man! I don’t have enough reputation to upvote, though I would like to :slight_smile:


#5

Good alternate solution :stuck_out_tongue: