@rajat..
First of all.. sorry for the late reply :)
Below i have explained the dp approach by taking.. Once u trace it u
will be able to understand the code..
Lets denote the no. of digits by K..
Now when K = 1, then the no. of digits that can formed is 10 i.e 0 to
9...
Say, P(K) denotes the no. of integers that can be formed using K
digits..
Hence, when K = 2, the digits would be :
00 01 02 03 04 05 06 07 08 09 - Line 1
For simplicity lets remove all leading 0's from Line 1..Hence we will
get,
0 1 2 3 4 5 6 7 8 9 - Line 1
Now, we can assume to put the first integer 0 in a separate line
called Line 0, as its the only integer whose value is 0 after removing
all leading 0's.
0 - Line 0
1 2 3 4 5 6 7 8 9 - Line 1
11 12 13 14 15 16 17 18 19 - Line 2
22 23 24 25 26 27 28 29 - Line 3
................continued...
88 89
99 - Line 10
Total no. of integers from Line 0 to Line 10 = 1+ 9 + 9 + 8 + 7 + ...
+ 1 = 55
Let Q(K) be defined as the no. of integers that can be formed by using
K digits where each integer has size K.
Hence, we reduce P(K) as shown below:
P(K) = 1 (for the first 0 integer) + Q(1) + Q(2) + Q(3) + .... + Q(K)
For K=2, as in the above example..
P(2) = 1 + Q(1) + Q(2)
= 1 + ( 9 ) + (9 + 8 + ...+ 1)
= 1 + 9 + 45 = 55
If you observe closely then u will see that Q(2) i.e Line 2 to Line 10
has been generated based on Q(1) i.e Line 1.
Here, is where DP comes into play. If we can find a way to generate
Q(i) given Q(i-1) then we are done.
// Lets look at array A with 1-based indexing for simplicity
Now, say if we have an array A[9], such that A[i] is used to keep
track of no. of integers of size 'L' which start with digit 'i'.
Now, say for size 'L+1' we need to calculate new value for A[9] ( say
we store the new values in A(new)[9]
The no. of integers that can be formed of size 'L+1' having the
leading digit as 9 is same
as the no. of integers starting with 9 of size 'L'.
Therefore,
A(new)[9] = A[9].
Now,
The no. of integers that can be formed of size 'L+1' having the
leading digit as 8 is equal to
the no. of integers starting with 8 of size 'L'
+
the no. of integers starting with 9 of size 'L'
A(new)[8] = A[8] + A[9]
Similarly,
A(new)[1] = A[1] + A[2] + ...+ A[9]
If you observe closely u will see that all we are doing is taking the
cumulative sum from A[9] to A[1]
Hence, we can modify the same array as follows:
// for size 'L+1', given A which stores the information for size
'L'...
// After executing the following code, A will store information for
size 'L+1'
for (int i = 8; i >=1 ; --i)
A[i] += A[i+1];
Hence, all we need to do is run the for loop for K - 1 times for K>1
and at the end of each loop record the sum of entire array and add it
to the totalSum. Also add 10 to totalSum at the beginning of the
entire algo, as we know that for K=1 the no. of integers are 10..
Now array A needs to be initialized as follows:
Q(1) = 9 and the corresponding array values would be as follows:
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]
1 1 1 1 1 1 1 1 1
Now, Q(2) = 45 and the corresponding array values would be as follows:
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]
9 8 7 6 5 4 3 2 1
Q(3) = 165 and the corresponding array values would be as follows:
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]
45 36 28 21 15 10 6 3 1
// Q(i) is nothing but the sum of the entire array..
Hence, P(3) = 10 ( 1+ 9 for K =1) + 45 ( Q(2) ) + 165 ( Q(3) )
= 220.
------------------------------------------
On Dec 28, 1:21 pm, sourabh singh <singhsourab...@gmail.com> wrote:
> @All are these output's correct ??
>
> 288230376151711744 20164264869698944
> 144115188075855872 5130634330054016
> 72057594037927936 5130634330054016
> 36028797018963968 1306288411057536
> 18014398509481984 1306288411057536
> 9007199254740992 332818957147520
> 4503599627370496 332818957147520
> 2251799813685248 84859707399552
> 1125899906842624 84859707399552
> 562949953421312 21654400343424
> 281474976710656 21654400343424
> 140737488355328 5530598972800
> 70368744177664 5530598972800
> 35184372088832 1413883960704
> 17592186044416 1413883960704
>
> On Tue, Dec 27, 2011 at 11:20 PM, sourabh singh
> <singhsourab...@gmail.com>wrote:
>
>
>
>
>
>
>
> > @all
>
> > plz point out wat's wrong with this code. works for small numbers but
> > fails for large number's
>
> > #include<conio.h>
> > #include<iostream>
> > using namespace std;
> > unsigned int find_nCp(unsigned int n,unsigned int p)
> > { unsigned int j=p;
> > unsigned int num=1,den=1;
> > for(;j;j--)
> > num*=n--;
> > for(;p;p--)
> > den*=p;
> > return (num/den);
> > }
>
> > unsigned int num(unsigned int n,unsigned int k)
> > {
> > if(n==1 || k==0)
> > return 1;
> > return find_nCp(n,k) + num(n-2,(n-1)/2);
> > }
> > main()
> > { uint64_t n,p,test=1;
> > unsigned int t,i,sum,j;
> > scanf("%u",&t);
> > while(t--)
> > { n=test<<t;
> > scanf("%llu",&n);
> > if(n<4)
> > cout<<0<<endl;
> > else
> > { for(p=1,i=0;p<=n;p=p<<1,i++);
> > i=i-2;
> > if(i%2==0)
> > {
> > i--;
> > }
> > cout<<num(i,i/2)<<endl;
> > getch();
> > }
> > }
> > return 0;
> > }
>
> > On Tue, Dec 27, 2011 at 10:33 AM, kumar rajat <thebossku...@gmail.com>wrote:
>
> >> *I am not able to follow..
>
> >> On Tue, Dec 27, 2011 at 11:47 PM, kumar rajat <thebossku...@gmail.com>
> >> wrote:
> >> > @Lucifier:
> >> > Thanks a lot..
> >> > But,I am able to follow the code that u posted for Non-Decreasing
> >> Digits.
> >> > Can u jus explain ur algo instead of givin the code directly?
> >> > Thanks once again.
>
> >> > On Tue, Dec 27, 2011 at 10:44 PM, Lucifer <sourabhd2...@gmail.com>
> >> wrote:
> >> >> @ Special Nos..
> >> >> Well the actual logic would be :
> >> >> int count = 0;for ( int i = 2; i <= LOGbase2(N) ; i+=2) count+=
> >> >> [ (i-1) C (i/2) ] ; // here xCy is nothing but the no. of ways y items
> >> >> can be selected from a collection of x items.
> >> >> Hence, the working code:
> >> >> int totalCount = 0;
> >> >> int interCnt = 1;
>
> >> >> if ( LOGbase2(N) > 1)
> >> >> {
> >> >> totalCount = 1; // for LOGbase2(N) = 2...
>
> >> >> for ( int i = 4; i <= LOGbase2(N) ; i+=2)
> >> >> {
> >> >> interCnt = (i-1)*(i-2) * interCnt / ( i/2 * (i/2 -1));
> >> >> totalCount += interCnt;
>
> >> >> }
> >> >> printf("%d", totalCount);
> >> >> }
> >> >> else
> >> >> printf("%d", 0);
> >> >> On Dec 27, 7:38 pm, Tasvinder Singh <tasvinde...@gmail.com> wrote:
> >> >>> I think the first problem involves some mathematics...
> >> >>> In this we fix the first bit and if the remaining no. of bits are odd
> >> then
> >> >>> we calculate the no. as follows
>
> >> >>> If we have 2^4=16 then total bits 5 so we do not include this.
> >> >>> Total no. of bits in one less than the given no. (in this eg. 15) is
> >> 4.
> >> >>> Fix first bit, no. of bits remaining = 3
> >> >>> Now let 2 bits are 0 and one bit 1. We have total 3!/(2!*1!) = 3
> >> >>> combinations.
>
> >> >>> Now go for next even no which is 2 in this case again do the same
> >> >>> Fix first bit, no. of bits remaining = 1
> >> >>> Now let 1 bit is 0. We have total 1!/(0!*1!) = 1 combinations.
>
> >> >>> Next even 0. stop here.
> >> >>> You can go for this by starting from 2 till no. is less than given N
>
> >> >>> On Tue, Dec 27, 2011 at 7:28 PM, kumar rajat <thebossku...@gmail.com>
> >> wrote:
> >> >>> > Hi
> >> >>> > I have jus started to learn DP and I have coded the standard
> >> >>> > algorithms(LCS,etc).
> >> >>> > I have been trying these problems in SPOJ:
>
> >> >>> >http://www.spoj.pl/problems/NOVICE63/
> >> >>> >http://www.spoj.pl/problems/NY10E/
>
> >> >>> > I understand these may be solved elegantly using DP,but I dont get
> >> to
> >> >>> > code the same.
> >> >>> > Can any1 help me how to solve these types of problems using DP?
> >> >>> > Any help regarding the same will be greatly appreciated.
>
> >> >>> > --
> >> >>> > You received this message because you are subscribed to the Google
> >> Groups
> >> >>> > "Algorithm Geeks" group.
> >> >>> > To post to this group, send email to algogeeks@googlegroups.com.
> >> >>> > To unsubscribe from this group, send email to
> >> >>> > algogeeks+unsubscr...@googlegroups.com.
> >> >>> > For more options, visit this group at
> >> >>> >http://groups.google.com/group/algogeeks?hl=en.
>
> >> >>> --
> >> >>> Tasvinder Singh
> >> >>> B.Tech Final Year,
> >> >>> Department of Computer Engineering,
> >> >>> Malaviya National Institute Of Technology, Jaipur.
> >> >>> Contact: +91-9460627331
>
> >> >> --
> >> >> You received this message because you are subscribed to the Google
> >> Groups "Algorithm Geeks" group.
> >> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
