New answers tagged

0

Since your question is about Memory Limit Exceed. And the most memory consumed item is dp. You are going to make your dp matrix smaller. Your current memory usage is \$O(2^{log_{10}n}\cdot n) = O(n^2)\$. And you need to reduce it to \$O(n)\$. Let's write down your current dp function: $$ dp_{i,j} = \min \{ dp_{i-1,j}, dp_{i, j-usable_i}+1 \} $$ First, ...


3

It is not necessary to make a copy of seen when making a recursive call. Change seen before the recursive calls and then undo the change afterward. def dfs(x, y, seen, word = ''): """ Recursive Generator that performs a dfs on the word grid seen = set of seen co-ordinates, set of tuples word = word to yield at each recursive ...


3

Pre-compute your offset tuples for possible_directions Use type hints Use strings instead of character lists for immutable data Those aside, you should really consider avoiding printing every single line of output if possible. The printing alone, at this scale, will have a time impact. Suggested: from typing import Set, Tuple, Iterable Coords = Tuple[int, ...


4

This is fairly tight; I don't think there's much more performance to pull out without dropping into C. That said: possible_directions First, I would rename this to neighbors or successors; it's not really about direction but about the nodes in the graph that come next or are adjacent to your current node. Second, you can reduce the number of branches and ...


Top 50 recent answers are included