Need Editorial for problem: A Simple Equation(EQUATION) [Easy]

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 :wink:

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?

@rishabhprsd7: First part or second “optimized” part?

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

@betlista

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