Dynamic Programming solution for one pile nim game

I have solved the following problem using dynamic programming: Little Deepu and his Girlfriend 1. To paraphrase,

We have two players Little Deepu and Kate and M items in the bag B, also we have a game set S with N elements, each element of game set is an integer. The game is played as follows, each player takes turn to pick an element from the game set S and removes that number of items from the bag, the player that is unable to remove the items from the bag looses the game. Little Deepu start the game ,If both Little Deepu and Kate play the game optimally, your task is to determine who wins the game.

Input: First line contains a integer T , number of test cases. Each test case contain two lines , first line contain two integer M and N and second line contain elements of S.

Output: For each test case print name of the winner of the game .

Though correct, my solution is exceeding time limit for large inputs. Please tell me where I am going wrong.

def winner(n_i, n_t, t_k):
output = [False]*(n_i + 1)
for j in t_k:
output[j    ] = True
print(output)
for i in range(1, n_i + 1):
if not output[j]:
for j in t_k:
if j > i:
continue
val = output[i - j]
if not val:
output[i] = True
break
return 'Little Deepu' if output[n_i] else 'Kate'

num_test = int(input())

for i in range(num_test):
num_items,num_take_outs = map(int, input().split())
take_outs = list(map(int, input().split()))
print(winner(num_items, num_take_outs, take_outs))

• I'm not sure why this question is not well received. time-limit-exceeded is a valid concern for CodeReview which doesn't mean the code is broken. – IEatBagels Sep 25 '18 at 13:25

The key insight is that I didn't have to check if any of the choices made at current position, say x, from game set S lead to a position, say x -Si , that will guarantee a loss for the opponent.Rather for any position that leads to loss I had to mark all further positions reachable from the current position using all the selections from the subset S as winning positions. Following is the code:

def winner(n_i, n_t, t_k):
output = [False]*(n_i + 1)
for j in t_k:
output[j] = True
for i in range(1, n_i + 1):
if output[i]:
continue
for j in t_k:
if i+j < n_i +1:
output[i+j] = True
return 'Little Deepu' if output[n_i] else 'Kate'

num_test = int(input())

for i in range(num_test):
num_items,num_take_outs = map(int, input().split())
take_outs = list(map(int, input().split()))
print(winner(num_items, num_take_outs, take_outs))