3 ms·

It's not a typo - specifically the time complexity is O(n^22^n2^n) = O(n^24^n). This is faster than your O(N!N!) proposal. https://www.wolframalpha.com/input?i

It's not a typo - specifically the time complexity is O(n^22^n2^n) = O(n^24^n). This is faster than your O(N!N!) proposal. https://www.wolframalpha.com/input?i=plot+%28n%21%29%5E2+vs+n%5E2+*+2%5En+*+2%5En+for+n+%3D+1+to+30 https://www.wolframalpha.com/input?i=plot+%28n%21%29%5E2+vs+... To be more specific - you get to O(n^22^n*2^n) by doing dynamic programming, which lets you avoid recomputing extra work for considering future ordering possibilities. This approach still implicitly considers all possible future orderings and acts optimally with respect to that. You can read the original post for more details - at a high level you are building a cache of win probabilities assuming optimal play, starting from the base case of 1-player crew battles, and extending it by 1 match per step of the recursion until you get back to the top-level problem. It is sufficient to only do computation 1 step ahead if you have a cache for how to act optimally for all n future steps.

jvanderbot 3y ago
Oh shit I read that as n^{24^n} I was like what are these kids smoking nowadays. Yes dynamic programming is indeed faster than brute force and I think I can convince myself this is the same approach with a little thought. I think everything we said here was correct (yes both of us) but I was responding to an incorrect understanding of your strategy (you aren't doing one step ahead you are indeed calculating total expectations). The brute force was just to show that the overall problem size was small when n is 6, in spirit of the original comment, and that brute force was just fine.
- Someone 3y ago
  > Oh shit I read that as n^{24^n} I was like what are these kids smoking nowadays That is the standard interpretation of x^y^z. Interpreting it as (x^y)^z doesn’t make sense as that is equal to the simpler and shorter x^(yz) (https://math.stackexchange.com/a/1633800 https://math.stackexchange.com/a/1633800)
  - jvanderbot 3y ago
    Well, he was saying n^24^n = (n^2)(4^n) which makes sense when rendered in latex, but not here. Clearly, I saw n^(24^n)
    - reaperman 3y ago
      The formatting along this entire thread is so bad due to accidental asterisk-induced italics that I cant follow much of it at all. It would help posters to learn that you can force a * without any risk of italics if you put a backslash in front of the asterisk to escape it. You can also put four spaces in front of the line to automatically escape all formatting characters. *this has four spaces in front of it and no escape characters*
      - jvanderbot 3y ago
        The authors would like to thank the reviewer for their insightful comments, while the edit window has passed for this particular thread, future work will make use of this trick.

jvanderbot 3y ago

Oh shit I read that as n^{24^n} I was like what are these kids smoking nowadays. Yes dynamic programming is indeed faster than brute force and I think I can convince myself this is the same approach with a little thought. I think everything we said here was correct (yes both of us) but I was responding to an incorrect understanding of your strategy (you aren't doing one step ahead you are indeed calculating total expectations). The brute force was just to show that the overall problem size was small when n is 6, in spirit of the original comment, and that brute force was just fine.

Someone 3y ago
> Oh shit I read that as n^{24^n} I was like what are these kids smoking nowadays That is the standard interpretation of x^y^z. Interpreting it as (x^y)^z doesn’t make sense as that is equal to the simpler and shorter x^(yz) (https://math.stackexchange.com/a/1633800 https://math.stackexchange.com/a/1633800)
- jvanderbot 3y ago
  Well, he was saying n^24^n = (n^2)(4^n) which makes sense when rendered in latex, but not here. Clearly, I saw n^(24^n)
  - reaperman 3y ago
    The formatting along this entire thread is so bad due to accidental asterisk-induced italics that I cant follow much of it at all. It would help posters to learn that you can force a * without any risk of italics if you put a backslash in front of the asterisk to escape it. You can also put four spaces in front of the line to automatically escape all formatting characters. *this has four spaces in front of it and no escape characters*
    - jvanderbot 3y ago
      The authors would like to thank the reviewer for their insightful comments, while the edit window has passed for this particular thread, future work will make use of this trick.