can someone please explain the solution to this problem?

help
, ,
1

Can someone please explain to me what the logic behind the solution to this problem is:

“A Simple Equation” - http://www.codechef.com/problems/EQUATION

I looked at a few solutions that produced the correct answer and I still cannot figure out why it works.

For example:

#include <stdio.h>

long long f(long long n)
{
	long long r;
	if (n<0)
		return 0;
	r = ((n + 1)*(n + 2)*(n + 3));
	return r / 6;
}
main()
{
	int t;
	long long n, a, b, c, ct;
	scanf("%d", &t);
	while (t--){

		scanf("%lld%lld%lld%lld", &n, &a, &b, &c);
		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);
		printf("%lld\n", ct);

	}
	return 0;
}

http://www.codechef.com/viewsolution/340267

2

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

2 Likes
3

#include<stdio.h>
void main()
{
int n,t,a,b,c,A,B,C,count=0;
while(t–)
{ scanf("%d%d%d%d",&n,&A,&B,&C);
for(a=0;a<A+1;a++)
{ for(b=0;b<B+1;b++)
{
for(c=0;c<C+1;c++)
{ int k=a+b+c;
if(k<n && k==n)
count++;

         }
       }

}
printf("%d \n",count);
count=0;
}

}

Why do this show runtime error

4

you’re not reading ‘t’

5

This code wont work as it will get tle due to the complexity…!! and yes as @mogers said you are not taking in the test cases t.