# How to solve Task sums?

Can anyone please provide detailed explanation of how to solve this problem.

@vivek_1998299

Can you please look into this one.

@vijju123

I really couldn’t think of any simple solution

One solution is:-

let max(ai)=x

dp[n] denotes if n belongs to A’,if it doesnt ,dp[n]=0

dp[n]=sum(dp[n-i]*f(i)) for all i from 1 to x

for n>x

and

dp[n]=f(n) for n<=x

where f(n)=1 if n belongs to A,else it is 0

After this,

refer this

@vivek_1998299

Some solutions are discussed here, but I couldn’t grasp that. Can you make sense out of it.

@vivek_1998299

Did you understand the approach explained there.

@l_returns

Can you please look into this.

Okay, I will try to keep it simple. As you know that max b[i] is 10^9 so it is not efficient to loop till b[i] and check whether b[i] can be in A’ or not. So we need to be cleverer here.
Observe that the highest limit on A[i] is 50000 which is quite low let’s make use of this fact to solve this question.
The key observation here is if we can make a number y with a then we can make any number of the form y+(x * a) where x>=0. Now if we cannot make y by a, then it would give some remainder r when we divide it by a, then to check if y can be in A’ we only need to check the smallest number z that can be made using the numbers given in A. if z<=y then y too can be in A’. Lets proof this
We know that, y%a=r and z%a=r and z<=y and z can be in A’ (as z could be made using the numbers in A)
so y= a * p + r and z = a * q + r (for some p and q).
substracting these y-z=p * a-q * a + r - r =(p-q)*a where(p>=q since y>=z) so,
y=z + (p-q) * a where (p-q>=0) so y can be made by adding a p-q times to z and since z is in A’ y will be too!!.
Now observe there are only 49999 posible values for remainder of a. So we only need to find the smallest value z where a%z=r for all r which can be done easily with dijkstra’s algorithm(in case you doesn’t know it https://en.wikipedia.org/wiki/Dijkstra’s_algorithm ).
here nodes are the possible remainders and there are n-1 edges outgoing from each node v to vertices (v+a[i])%a for all i from 1 to n-1 (for 0-based indexing ) and dis[x] = minimum number z such that z%a=x. as you can see dis=0;
now all we need to do is that get input of b[i] check if dis[b[i]%a]<=b[i] or not if it is then ans would be TAK,as dis[b[i]%a] is the smallest number that can achieve remainder b[i]%a and it is smaller than b[i] so we can add a to it some number of times and achieve b[i] so b[i] can be in A’ else remainder b[i]%a is not achievable before that so ans would be NIE.
complexity would be O(N * max(A[i]) * log max(A[i])) since complexity of dijkstra is O(ElogV) where E is the number of edges and V is the number of vertices.
My AC code- https://ideone.com/3GVmv1
Hope You Understand, comment your doubt if not