How to solve this mathematical question?

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.

2 Likes

This was from Kaleyra challenge from Hackerearth which was completed.

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

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.

3 Likes

Hi! can you explain how to find solutions for i + 2j + k = x.

Yup, the first line already stated that.

1 Like

Thanks for the reply, let me analyze this.

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.

1 Like