PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: mhndalaa
Preparation: jay_1048576
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Dynamic programming
PROBLEM:
Chef earns X for each hour he works.
There are N gifts, the i-th has price A_i. Each gift can be bought at most once.
Find the minimum number of hours Chef needs to work so that he can buy some (possibly empty) subset of gifts and be left with exactly Z afterwards.
EXPLANATION:
Suppose Chef works for k hours, and buys gifts worth S in total.
We want the condition k\cdot X - S = Z to hold, or k\cdot X = S + Z.
Our aim is to minimize k, which as you can see is the same as minimizing S (provided S+Z is a multiple of X, of course).
That is, our objective is to find the smallest number S such that S can be written as the sum of some subset of A_i, and S+Z is a multiple of X.
Now, finding all values of S (i.e, all possible subset sums) is a classical dynamic programming task, the subset sum problem.
Unfortunately, its complexity of \mathcal{O}(N\cdot sum(A)) is too slow for us.
However, it can be modified to fit our use-case.
Notice that we don’t care about the actual sum too much: we’re more concerned about whether S+Z is a multiple of X or not (and only then, minimization).
So, it’s enough to keep information about the subset sums modulo X.
That is, define f(i, j) to be the smallest subset sum from the first i numbers, such that this sum is j modulo X.
Then, we can either take A_i into the subset or not, so we have:
where the second argument is always taken modulo X (so consider (j-A_i)\mod X in the second function call).
The base cases are, of course, f(0, 0) = 0 and f(0, j) = \infty for j\gt 0.
Notice that this gives us \mathcal{O}(N\cdot X) states, with \mathcal{O}(1) transitions from each, so dynamic programming gives us a complexity of \mathcal{O}(N\cdot X) overall.
Now, the optimal value of S is just f(N, j), where j is the unique remainder modulo X such that (j+Z) \equiv 0 \pmod X.
If this f(N, j) is \infty no solution exists (so print -1), otherwise the answer is \frac{Z + f(N, j)}{X}.
TIME COMPLEXITY:
\mathcal{O}(N\cdot X) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, x, z = map(int, input().split())
a = list(map(int, input().split()))
dp = [10**16]*x
ndp = [0]*x
dp[0] = 0
for y in a:
for i in range(x): ndp[i] = dp[i]
for i in range(x): ndp[i] = min(ndp[i], dp[(i-y)%x] + y)
for i in range(x): dp[i] = ndp[i]
want = (-z) % x
if dp[want] > 10**15: print(-1)
else: print((dp[want] + z)//x)