You are not logged in. Please login at www.codechef.com to post your questions!

×

VOWELDP - editorial

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[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.

asked 30 Mar '16, 16:18

chandubaba's gravatar image

2★chandubaba ♢
1398
accept rate: 0%

edited 20 May '16, 11:40

admin's gravatar image

0★admin ♦♦
19.5k348496535


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.

link

answered 27 Aug '17, 20:15

rohan_bose95's gravatar image

5★rohan_bose95
60215
accept rate: 8%

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

(20 Sep '17, 09:38) chandubaba ♢2★

Good alternate solution :p

(25 Mar, 17:10) harrypotter02★

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

link

answered 25 Mar, 18:35

harrypotter0's gravatar image

2★harrypotter0
22810
accept rate: 2%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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