This question was asked in Kaleyra Recruitment Challenge on HackerEarth which is now completed. The question was as follows:
How many distinct ways are there such that (i+2j+k)%(x+y+2z) = 0.
Condition:
1<=i,j,k,x,y,z<=n
1<=test_cases<=10
1<=n<=1000
For n =1, ans was 1
For n=2, ans was 15
For n=3, ans was 117
Bruteforce was an obvious no as complexity was going to n^6.
The answer probably lies in using permutation taking into consideration some cases but I wasn’t able to find all cases as my answer was not correct for n=3 and beyond.
As you can see the numerator and denominator are basically the same expression i.e. i+2*j+k
The possible values of this range from 4 to 4*n. Let’s denote arr[x] be the number os ways of getting the i+2*j+k = x. Now for each possible x such that sum arr[x]*arr[y] such y%x==0.
Pseudocode:
ans = 0
for all x such that arr[x]>0:
y = 1
while x*y <= 4*n
ans += arr[x]*arr[x*y]
y++
PS : dont forget the mod
Also finding no of ways of getting i+2*j+k = x is just an extension of getting x+y+z=n you can google that. or just comment below I’ll explain it.
i+2*j+k = x is the same as finding the coefficient of y^x in the sequence(y + y^2 + .., + y^n)*(y^2 + y^4 + ... + y^2n)*(y + y^2 + .., + y^n). The mathematical concept you’ll need to solve this efficiently is negative binomial theorem.
Id3GlG - Online C++0x Compiler & Debugging Tool - Ideone.com, you should notice that it is type of dp consider possible values using i,j and then possible value and k in n^2, and then find modulo intersection using sieve. without sieve i got tle in main problem, hence i guess sieve is necessary, or u could use gcc optimizer.