再帰的で記録を使う魔法

本日トップコーダーのアルゴリズムを解けて一つな驚きがありました。ただの再帰関数で行けると思ったけど時間的に遅すぎた。However, recursive search on the string (converted to a char vector) with memorization (string->optimal string) succeeded with a worst-case latency of 1.2s. This seems to be because, although the recursive complexity is not prohibitive O(50*25*13*7*4*2) = O(91000) , assuming L>=1, the cost per search visit of nlog(n) or O(50*6)=300 makes the total complexity be O(30*10^6). However, with memorization, some paths through state space need not be traversed. Namely any two paths which result in the same output string are considered identical. Thus:
TWCABCE L=2
TWCABCE->TWCAB = TWCABCE->TWCABC->TWCAB
While increasing the per-call overhead somewhat (as the vector must be converted to a string to store in the unordered_map), the number of branches in the search tree pruned more than compensates. However, the exact number of "unique" paths is unclear. For example, if L is 3 and the string is of length 50, sort from 47, then sort from 0 equals sort from 20, then sort from 0, equals sort from 5 then stort from 0, etc. So, as L>=2, 49 first indices, then (L-1) second indices, third indices, etc. This still leaves a complexity of something like O(49*2^25)>o(49*32*10^6), but, due to attrition of left-side nodes (as, after splitting at node 1, no further splitting is possible), the branch factor is not exactly two, and it is expected that the number of recursive calls is less than 90000. In fact, for L=2, the number is much smaller, as the branch factor is 1. For L=3, the branch factor is 2, but the depth is at most 17 (2^17<200000), and with attrition the cost is expected to be much less. For L=3, it seems that the number of nodes is 1+3+5+...+ 33 = 33*34/2=561.