Can any one please provide an approach to solve above mentioned problem in given limit of time. Please!! Problem link: http://www.codechef.com/problems/EQUATION
1 Like
Ok, lets start with some common observations we can make by seeing the nature of the problem:-
1.) If u have two numbers say a and b and if you are given to find a and b such that their sum is less than or equal to c, then you can do it easily. i.e. you can solve this problem easily for two numbers a and b. However with 3 it becomes a tad more complicated.
2.) Even with three numbers a, b, c where a can be less than or equal to A, b to B and c to C, if A+B+C <=N , then you observe that you can take any value of a, b and c and it’ll solve this equation. Now we use these two conditions to solve this problem.
We start by varying a from 0 to A and then find the number of ways we can choose b and c such that their sum is less than or equal to N (because a+b+c<=N) given the condition that b<=B and c<=C. This approach will be an O(n^2) time complexity solution, but given the small nature of inputs, it’ll suffice. Thus you reduce this problem from three variables to two variables by using this condition for every a from 0 to A and solve it easily. I have implemented the same in my solution http://www.codechef.com/viewsolution/4928259 . Please go through it for the implementation. I’ll be more than happy to help if you have trouble understanding any part of it.
2 Likes
The concept of The Inclusion-Exclusion used for this problem is as follows:-
ct=f(n)-f(n-a-1)-f(n-b-1)-f(n-c-1)+f(n-a-b-2)+f(n-b-c-2)+f(n-a-c-2)-f(n-a-b-c-3);
where f(n) denotes
long long f(long long n)
{
long long r;
if(n<0)
return 0;
r=((n+1)*(n+2)*(n+3));
return r/6;
}
Although assuming you already know the concept of Inclusion-Exclusion, lets consider the case
4 3 2 1
here given n = 4, a = 3, b = 2, c = 1
denotation of f(n) shows all the possible cases that can occur for all n = 1,2,3,…n
if n = 4, f(n) = 35, where various combinations will be(in sequence a,b,c)
0(combinations 1) = 0 0 0
1(combinations 3) = 1 0 0, 0 1 0, 0 0 1
2(combinations 6) = 2 0 0, 0 2 0, 0 0 2, 1 1 0, 1 0 1, 0 1 1
3(combinations 10) = 3 0 0, 0 3 0, 0 0 3, 2 1 0, 2 0 1, 1 2 0, 1 0 2, 0 1 2, 0 2 1, 1 1 1
4(combinations 15) = 4 0 0, 0 4 0, 0 0 4, 3 1 0, 3 0 1, 1 0 3, 1 3 0, 0 1 3, 0 3 1, 2 2 0, 2 0 2, 0 2 2, 2 1 1, 1 2 1, 1 1 2
but as asked in the question, we have to restrict a, b, c with 3, 2, 1 respectively, for that we exclude all the undesired cases which can be done easily with Inclusion-Exclusion Principle
f(n-a-1) = f(4-3-1) = f(0) = 1 (combinations (4 0 0))
f(n-b-1) = f(4-2-1) = f(1) = 4 (combinations (0 3 0, 0 4 0, 1 3 0, 0 3 1))
f(n-c-1) = f(4-1-1) = f(2) = 10 (combinations (0 0 2, 0 0 3, 1 0 2, 0 1 2, 0 0 4, 1 0 3, 0 1 3, 2 0 2, 0 2 2, 1 1 2))
f(n-a-b-2) = f(4-3-2-2) = f(-3) = 0
f(n-b-c-2) = f(4-2-1-2) = f(-1) = 0
f(n-a-c-2) = f(4-3-1-2) = f(-2) = 0
f(n-a-b-c-3) = f(4-3-2-1-3) = f(-5) = 0
so, by the Principle of Inclusion we get
ct = 35 - 1 - 4 - 10 = 20
2 Likes
Thankz topcoder_7
Thankz pranjalranjan…
1 Like
@rishabhprsd7: Thanks for bringing this into my attention 
My first approach was (while A, B, C, N <= 2500), that O(N2) should be ok
res = 0
for a in 0..A
for b in 0..B
res += intersectionOf( [a+b, a+b+c], [0, N] );
idea is, that while we have fixed a and b, the left side of the equation is in range/interval of a+b+0…a+b+c, while right side is in range 0…N.
Then I spent some to time (8 submissions) to overcome TLE.
It seems, that one important idea is to modify loop conditions to
for a in 0..min(A, N)
for b in 0..min(B, N-A)
1 Like
Yes thats the crunch!
No, i am sorry i am finding it a bit difficult to understand this approach.
Can you please elaborate it please?
solution :- ans is coefficient of sum of exponents in d eqtn st a+b+c<=n (1+x^1+x^2+x^3+…+x^A)(1+x^1+x^2+x^3+…+x^B)(1+x^1+x^2+x^3+…+x^C)
=(1-x^(A+1))(1-x^(B+1))(1-x^(C+1)) / (1-x)^3 // using binomial series expansion
now (1-x)^-3=1+ 3C1 x + 4C2 x2 + 5C3 x3 +… (r+2)C2 x^r //x2 is x^2
=Summation (r+2)C2 x^r for 0<=r<=n
//since we want sol for a+b+c<=n hence ans is coefficient of dis such that x^(k) for all k<=n ->
( 1-x^(A+1)-x^(B+1)-x^(C+1)+x^(A+B+2)+x^(B+C+2)+x^(A+C+2)-x^(A+B+C+3) ) * Summation term as above
Now summation (r+2)C2 x^r for 0<=r<=n ->
(3C2 +4C2) +5C2 +…+(r+2)C2
= (4C3 +5C2) +…+(r+2)C2
= 5C3 +…+(r+2)C2
=…=(r+3)C3
here r refers to coefficient of x …now after multiplying terms we get …r-A-1,r-B-1,r-C-1 nd so on take r=n
we get ans=f(n)-f(n-a-1)-f(n-b-1)-f(n-c-1)+f(n-a-b-2)+f(n-b-c-2)+f(n-a-c-2)-f(n-a-b-c-3); where f(n) is (n+3)C3
1 Like
I am dumb in algorithms…
So let me tell you first about my approach…
Simplest Approach but results time out :
for a in (0,A)
for b in (0,B)
for c in (0,C)
checking the condition
Now can you tell me ohh I am sorry… i didnt understood both approach… really sorry for that…
As it looks you had a brain storming for this question so can you please explain me both of your approaches…
Thanks in advance and really sorry . . .!