Solution of Light OJ - 1102 - Problem Makes Problem

Problem Statement :

        As I am fond of making easier problems, I discovered a problem. Actually, the problem is 'how can you make n by adding k non-negative integers?' I think a small example will make things clear. Suppose n=4 and k=3. There are 15 solutions. They are

1.      0 0 4

2.      0 1 3

3.      0 2 2

4.      0 3 1

5.      0 4 0

6.      1 0 3

7.      1 1 2

8.      1 2 1

9.      1 3 0

10.  2 0 2

11.  2 1 1

12.  2 2 0

13.  3 0 1

14.  3 1 0

15.  4 0 0

As I have already told you that I use to make problems easier, so, you don't have to find the actual result. You should report the result modulo 1000,000,007.

Problem Logic :
    
 1.    Note that a similar classic problem is the following:

 2.  How many ways can 10 pieces of candy be divided among 4 children?

3. For this case we need to find the number of solutions to the equation

                                i+j+k+l = 10

                                where i, j, k, and l are non-negative integers. 

 4. We can find the answer using a technique popularly known as "stars and bars".  

5. The idea behind this method is the following:

                (*) We represent the objects to be divided by "stars": ****
                (*) To indicate dividing the object into groups, we use bars as "divider" symbols:  |||

6.For our problem, we have ten pieces of candy:

                          **********

7. To divide these ten objects into four groups, we need three dividers:

                          **********|||

8. The particular arrangement of the "stars and bars" shown above 
specifically represents the case where the first child gets all ten 
pieces of candy.  

9.  Each different arrangement of these stars and bars represents a distinct distribution of the ten pieces of candy among the four children.  

10. For example, the arrangement represents the case where the first child gets 3 pieces,


                                             ***|*|**|****

 the second child 1, the third child 2, and the fourth child 4.

11. So the number of different ways of distributing 10 pieces of candy 
among 4 children is the number of distinct arrangements of the stars 
and bars.  

12. With 10 stars and 3 bars, this number is, as you probably 
know,

                            (10+3)!                                 13*12*11
                          --------- = "13 choose 3" = -------- = 13*2*11 = 286
                           (10!)(3!)                                   3*2*1

13. So the number of terms in the expansion of (a+b+c+d)^10 is 286.

14. If we are raising an expression with "m" terms to the "n"th power, 
then we have n "stars" and (m-1) "bars"; the number of terms in the 
expansion is then

  (n+(m-1))!
  ---------- = "(n+m-1) choose (m-1)"
  (n!)(m-1)!


15. Note this agrees with what you noted about the number of terms in the 
expansion of (a+b)^n.  Here the number of terms, "m", is 2; so the 
number of terms in the expansion of (a+b)^n is

  "(n+m-1) choose (m-1)" = "n+1 choose 1" = n+1

Solution of Light OJ 1038 - Race to 1 Again

                 শীতের সকালে সুন্দর রোদের আলো থাকে । সেই আলো তির্যকভাবে পড়ে ঘাসের ডগায় জমে থাকা শিশিরের উপর ।  শিশির থেকে সেই আলো বিচ্ছুরিত হয়ে ফিরে আসে আমাদের চোখে এবং মুখে । তখনকার চাঙ্গা অনূভব সবার মধ্যে সর্বদা বজায় থাকুক - এই প্রত্যাশায় চল বন্ধুরা আমরা শুরু করি আমদের নবজীবনের গান ।  

                 শুরুতেই বলে নেই আজকের সমস্যার Topics হল Probability/Expected Value । সমস্যার  সারসংক্ষেপ নিচে প্রদান করা হল ।

      ১। Rimi  integers  সম্পর্কে  নতুন একটা জিনিস জানল আর তা হল 
                  - any positive  integer greater than 1 can be divided by its  
              divisors. 
  

    ২।  Integer এর property  কে নিয়ে সে খেলা শুরু করল ।  

    ৩।  সে যে কুন একটা  number N নিল  এবং এইটার নাম দিল  D .

     ৪। In each turn he randomly chooses a divisor of D (1 to D). 
    
   ৫। Then he  divides D by the number to obtain new D. 

   ৬। He repeats this procedure until D becomes 1. 

What is the expected number of moves required for N to become 1.

Solution hints :

      1.  Suppose we want to calculate E(N) where N is a number,k is the number of it’s distinct prime factors and p is the number of primes < n

                                                                                                 E(N)=1+(1/p)*(E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak)) + ((p-k)/p) * E(N)


     2. It means after one step we can choose a correct prime numbers(from the factors of N) or one of the wrong ones from (p-k) ones


    3. Such a recurrence can be changed to


       E(N) – ((p-k)/p) * E(N) = 1+(1/p)*(E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak)) 
        
      E(N)*(k/p) = 1+(1/p)*(E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak))


    4. We can apply dynamic programming then.

U can Alo try UVA ACM 11762 

1090 - Trailing Zeroes (II)

Number theory এর খুব সুন্দর একটি সমস্যা । আগ্রহীরা আগে নিজে চেষ্টা করে দেখতে পার ।

Problem Statement:
       Find the number of trailing zeroes for the following function: mCn * p^q

Solution :

     ১। যেহেতু mCn = m!/(n!)/(m-n) ! কাজেই প্রথমে m!  ,n! এবং (m-n)! এ কতটি ২ আছে তা বের কর    
      ২ ।  মনে কর তাদের মধ্যে ২ আছে যথাক্রমে a2,b2,c2
      ৩। তাহলে mCn এ ২ আছে no_of_2 = a2-(b2+c2)
      ৪।  একই ভাবে  mCn এ ৫ আছে no_of_5 = a5-(b5+c5)
      ৫। নিচের Algorithm follow করে P এর মধ্যে ২ কতবার আছে তা বের কর । মনে কর P তে ২ আছে n1 বার ।

Algorithm:
     while( n>0 && !(n%2) )
    {
            n=n/n1;
            ++no;
    }

   ৬।  কাজেই mCn*p^q এ total 2 আছে  no_of_2 += n1 * q

    ৭। একই ভাবে  mCn*p^q এ total 5 আছে  no_of_5 .

   ৮।   এইবার নিচের step টি খেয়াল করে দেখ ।

Algorithm :

if(no_of_2<no_of_5)
            zero=no_of_2;
        else
            zero=no_of_5;

৯। বাহ এইতো খুব সুন্দর মতই শেষ করতে পেরেছ এই সমস্যার সমাধান ।

Code :

#include<iostream>
using namespace std;

int no_of_2,no_of_5;

int  no_of_zero_in_factorial(int  n,int n1)
{
    int  number=0;
    while(n>0)
    {
        number+=n/n1;
        n/=n1;
    }
    return number;
}

void  calculate_zero(int  m,int  n)
{
    int a2,a5,b2,b5,c2,c5;
    a2 = no_of_zero_in_factorial(m,2);
    a5 = no_of_zero_in_factorial(m,5);
    b2 = no_of_zero_in_factorial(n,2);
    b5 = no_of_zero_in_factorial(n,5);
    c2 = no_of_zero_in_factorial(m-n,2);
    c5 = no_of_zero_in_factorial(m-n,5);

    no_of_2=a2-(b2+c2);
    no_of_5=a5-(b5+c5);

}

int prime_factorize(int n,int n1)
{
    int no=0;
    while( n>0 && !(n%n1) )
    {
            n=n/n1;
            ++no;
    }
    return no;
}

int  main()
{
     int  i,test,n,m,p,q,zero;
    cin>>test;
    for(i=1;i<=test;i++)
    {
        cin>>m>>n>>p>>q;

        calculate_zero(m,n);

        no_of_2+=prime_factorize(p,2)*q;
        no_of_5+=prime_factorize(p,5)*q;

        if(no_of_2<no_of_5)
            zero=no_of_2;
        else
            zero=no_of_5;
        cout<<"Case "<<i<<": ";
        cout<<zero<<endl;

        no_of_2 = 0;
        no_of_5 = 0;
    }
    return 0;
}

সবশেষে তোমার জন্য রইল অনেক শুভকামনা । ভাল থেক সব-সময় ।