Divisibility and recurrence

this is the question http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=977%20UVa%20Online%20Judge%20uva.onlinejudge.org

the brute force will give 2^n solution n=10^4 so there should have to be a dynamic programming solution

can anyone help me to make the dynamic equation of this problem

a) For each number, we add add it or subtract it to the current result.
b) We’re interested in divisibility by K. In other words, we want to know if the remainder is zero.

So, the search state is the current number and the remainder of our expression divided by K. N <= 10^4 and K <= 10^2 yields 10^6 states which is fine as we only need O(1) per state (add and subtract the number to current remainder).

A simple pseudo-c++ would be

bool seen[N][K];  // init to false
bool IsDivisible(pos, remainder) {
    if seen[pos][remainder]
       return false  // we've seen before this state leads nowhere
   if pos == N
       return remainder == 0
   seen[pos][remainder] = true
   if IsDivisible(pos+1, (remainder + number[pos]) % K)
       return true
   if IsDivisible(pos+1, (remainder - number[pos] + K) % K)
      return true
   return false
}
// call it with IsDivisible(0, 0)
1 Like