Can anyone please provide detailed explanation of how to solve this problem.
problem link : https://szkopul.edu.pl/problemset/problem/4CirgBfxbj9tIAS2C7DWCCd7/site/?key=statement
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
Some solutions are discussed here, but I couldn’t grasp that. Can you make sense out of it.
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[0] then we can make any number of the form y+(x * a[0]) where x>=0. Now if we cannot make y by a[0], then it would give some remainder r when we divide it by a[0], 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[0]=r and z%a[0]=r and z<=y and z can be in A’ (as z could be made using the numbers in A)
so y= a[0] * p + r and z = a[0] * q + r (for some p and q).
substracting these y-z=p * a[0]-q * a[0] + r - r =(p-q)*a[0] where(p>=q since y>=z) so,
y=z + (p-q) * a[0] where (p-q>=0) so y can be made by adding a[0] 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[0]. So we only need to find the smallest value z where a[0]%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[0] for all i from 1 to n-1 (for 0-based indexing 
) and dis[x] = minimum number z such that z%a[0]=x. as you can see dis[0]=0;
now all we need to do is that get input of b[i] check if dis[b[i]%a[0]]<=b[i] or not if it is then ans would be TAK,as dis[b[i]%a[0]] is the smallest number that can achieve remainder b[i]%a[0] and it is smaller than b[i] so we can add a[0] to it some number of times and achieve b[i] so b[i] can be in A’ else remainder b[i]%a[0] 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