Unexpected output

[dev-rish]

I know this might not be the right place to ask this but still hoping I could get some help.

I am trying this but end up with an error which I dont fully understand. Also I have to use yield from instead of yield to remove the error but end up getting the wrong answer. Also is it possible to use lru_cache with this setup?

Expected/Correct Output: 2

Output: 0

Problem Link: https://codeforces.com/problemset/problem/1343/C

My Code

from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
            else:
                stack.pop()
                if not stack:
                    break
                to = stack[-1].send(to)
        return to

    return wrappedfunc

def get_sum(arr):
    n = len(arr)

    memo = dict()

    @bootstrap
    def rec(i, is_prev_pos):
        if i >= n:
            yield (0, 0)
        else:
            key = (i, is_prev_pos)

            if key in memo:
                yield memo[key]
            elif is_prev_pos == (arr[i] > 0):
                # yield from rec(i + 1, is_prev_pos)
                yield rec(i + 1, is_prev_pos)
            else:
                # l1, s1 = yield from rec(i + 1, arr[i] > 0)
                # l2, s2 = yield from rec(i + 1, is_prev_pos)
                l1, s1 = yield rec(i + 1, arr[i] > 0)
                l2, s2 = yield rec(i + 1, is_prev_pos)

                memo[key] = max((1 + l1, arr[i] + s1), (l2, s2))

                yield memo[key]

    return max(rec(0, True), rec(0, False))[1]

get_sum([1, 2, 3, -1, -2])

[bjorn-martinsson]

Your bug is caused by

elif is_prev_pos == (arr[i] > 0):
    yield rec(i + 1, is_prev_pos)

What you should have is

elif is_prev_pos == (arr[i] > 0):
    yield(yield rec(i + 1, is_prev_pos))

As for lru_cache, unfortunately I think that bootstrap is incompatible with lru_cache. So if you want memoization, you have to manually code it.

[dev-rish]

Your bug is caused by

elif is_prev_pos == (arr[i] > 0):
    yield rec(i + 1, is_prev_pos)

What you should have is

elif is_prev_pos == (arr[i] > 0):
    yield(yield rec(i + 1, is_prev_pos))

Thanks a lot for the help.

Can you please explain as to why that is required. Does it have to do something with tuple as the return value. Also do i need to consider yield from considering this is the typical recursive structure I use. It would be great if you can point me to some resource which I should familiarize myself with in order to understand this better.

[bjorn-martinsson]

Your bug is caused by

elif is_prev_pos == (arr[i] > 0):
    yield rec(i + 1, is_prev_pos)

What you should have is

elif is_prev_pos == (arr[i] > 0):
    yield(yield rec(i + 1, is_prev_pos))

Thanks a lot for the help.

Can you please explain as to why that is required. Does it have to do something with tuple as the return value. Also do i need to consider yield from considering this is the typical recursive structure I use. It would be great if you can point me to some resource which I should familiarize myself with in order to understand this better.

The reason I made bootstrap is that recursion in Python has its fair share of issues. Most of the time, you really want to avoid doing deep recursion in Python. This is very unfortunate, because many problems are naturally solved using recursion. One thing you can do in Python is to manually simulate recursion using your own stack. This works, but it is very bothersome to code. This issue is what lead me to come up with the idea for bootstrap.

The idea behind bootstrap is to use use "recursive" generators instead of recursive functions.

Whenever you want to do a recursive call in a "recursive" generator, you make it yield that recursive call. That is what you did here

l1, s1 = yield rec(i + 1, arr[i] > 0)

Finally, when you want to make your "recursive" generator return a value, then you yield that return value. This is what you did here

yield memo[key]

bootstrap is the machinery that takes care of the rest. Whenever a "recursive" generator wants to call another "recursive" generator, then bootstrap simulates that call with its own stack. This lets you completely avoid using the built in recursion in Python.

---

It would be great if you can point me to some resource which I should familiarize myself with in order to understand this better.

bootstrap is my own idea. I don't think there is any resource out there that explains how it works.

Also do i need to consider yield from considering this is the typical recursive structure I use.

There is not reason to use yield from together with bootstrap.

Does it have to do something with tuple as the return value.

No. The inner yield is a recursive call, the outer yield is the return value.

yield(yield rec(i + 1, is_prev_pos))

It is probably easier to follow what is happening if you rewrite it like this

ret = yield rec(i + 1, is_prev_pos)
yield ret

Your original code only used 1 yield, which meant that you were missing the return statement yield ret.

[Mukundan314]

You can use the AST version of bootstrap to have more familiar syntax (i.e. return and direct calls instead of yield)

But it comes with caveats:

• Code at top level (i.e. outside of functions) is executed twice.
• @bootstrap decorator does not work in nested functions
  • This can be fixed by running bootstrap.bootstrap.add("<function name>") in top level
• renaming bootstrapped function does not work
• all limitations of regular bootstrap, so you still can't use @lru_cache

Code you provided converted to use bootstrap ast (click to show)

```python import ast import inspect import sys from types import GeneratorType class Bootstrap(ast.NodeTransformer): def __init__(self): self.active = [False] self.bootstrap = set() @staticmethod def resolve(to): stack = [] while True: if type(to) is GeneratorType: stack.append(to) to = next(to) else: stack.pop() if not stack: break to = stack[-1].send(to) return to def __call__(self, func): self.bootstrap.add(func.__name__) def visit_Call(self, node): self.generic_visit(node) if getattr(node.func, "id", None) in self.bootstrap: if self.active[-1]: return ast.Yield(node) else: return ast.Call( ast.Attribute(ast.Name("Bootstrap", ast.Load()), "resolve", ast.Load()), [node], []) return node def visit_Return(self, node): self.generic_visit(node) return ast.Expr(ast.Yield(node.value)) if self.active[-1] else node def visit_FunctionDef(self, node): new_decorator_list = [ decorator for decorator in node.decorator_list if getattr(decorator, "id", None) != "bootstrap" ] self.active.append(len(new_decorator_list) != len(node.decorator_list)) node.decorator_list = new_decorator_list self.generic_visit(node) self.active.pop() return node bootstrap = Bootstrap() bootstrap.bootstrap.add("rec") def get_sum(arr): n = len(arr) memo = dict() @bootstrap def rec(i, is_prev_pos): if i >= n: return (0, 0) else: key = (i, is_prev_pos) if key in memo: return memo[key] elif is_prev_pos == (arr[i] > 0): # yield from rec(i + 1, is_prev_pos) return rec(i + 1, is_prev_pos) else: # l1, s1 = yield from rec(i + 1, arr[i] > 0) # l2, s2 = yield from rec(i + 1, is_prev_pos) l1, s1 = rec(i + 1, arr[i] > 0) l2, s2 = rec(i + 1, is_prev_pos) memo[key] = max((1 + l1, arr[i] + s1), (l2, s2)) return memo[key] return max(rec(0, True), rec(0, False))[1] def main(): print(get_sum([1, 2, 3, -1, -2])) if __name__ == "__main__": source = inspect.getsource(sys.modules[__name__]) tree = bootstrap.visit(ast.parse(source)) ast.fix_missing_locations(tree) # print(ast.unparse(tree)) # for debugging exec(compile(tree, __file__, "exec"), {}) elif __name__ == "builtins": main() ```

[dev-rish]

@bjorn-martinsson Thank a lot for the explanation. Unfortunately I ended up with TLE of which I am not sure why considering the complexity is linear and had to change the same solution to iterative (exactly same logic) to get it accepted. I did read somewhere that generators are slow but still expected the solution (with bootstrap) to pass.

@Mukundan314 Thanks for suggesting. I will give that a shot. Though it looks a little scary 😅.

[Mukundan314]

AC (just barely though): https://codeforces.com/contest/1343/submission/203865461 by memoizing is_prev_pos == (arr[i] > 0) case as well

[dev-rish]

AC (just barely though): https://codeforces.com/contest/1343/submission/203865461 by memoizing is_prev_pos == (arr[i] > 0) case as well

Wow..its interesting. Never thought 1 function call in itself could be be that expensive lol. Thanks for sharing...

[bjorn-martinsson]

@bjorn-martinsson Thank a lot for the explanation. Unfortunately I ended up with TLE of which I am not sure why considering the complexity is linear and had to change the same solution to iterative (exactly same logic) to get it accepted. I did read somewhere that generators are slow but still expected the solution (with bootstrap) to pass.

The real issue is that your solution is really slow to begin with. My guess is that even your iterative solution is like 20 times slower than the intended solution https://codeforces.com/contest/1343/submission/203907285 . You are using hashmaps, tuples, comparisions between tuples, keying hashmaps using tuples, and a ton of if-statements. All of this makes your solution unnecessarily slow.

This problem has a relatively tight TL of 1s for n = 2e5, and you using Python. Don't expect your solution to not TLE just because it technically has the correct time complexity. For problems like this, the best way to solve them is to come up with simple for loop solutions. There is a time and place for recursion, memoization and bootstrap, but this problem is not it.

[dev-rish]

The real issue is that your solution is really slow to begin with. My guess is that even your iterative solution is like 20 times slower than the intended solution https://codeforces.com/contest/1343/submission/203907285 . You are using hashmaps, tuples, comparisions between tuples, keying hashmaps using tuples, and a ton of if-statements. All of this makes your solution unnecessarily slow.

The iterative sol got accepted easily https://codeforces.com/contest/1343/submission/203760212. I know the runtime can be brought down further if I switch hashmap with 2D array like so https://codeforces.com/contest/1343/submission/204072861

This problem has a relatively tight TL of 1s for n = 2e5, and you using Python. Don't expect your solution to not TLE just because it technically has the correct time complexity. For problems like this, the best way to solve them is to come up with simple for loop solutions. There is a time and place for recursion, memoization and bootstrap, but this problem is not it.

Usually with other codejudges the recursive solutions are accepted as long as the complexity is fine & there isn't a large constant factor but since codeforces is pretty strict (+ slow python speed) I am forced to optimize (which is good). With this problem I was just testing out a recursive template which might come in handy for some future graph problems which require DFS. I still doubt if I can get away with this template. As of now I dont want to start with C++.

I know my solutions aren't the best but since its pretty early as of now my aim is to get solutions accepted. Hopefully with time & practice I can improve 😅. Thanks for pointing to a better/cleaner sol. though.