[C++] In-Depth Explanation, How to Calculate Permutation Rank, Beats 100%
Problem:\n\n- We have 2 choices for which letter we want to add: H or V.\n- We have destination[0] amount of V and destination[1] amount of H.\n- The total numb
# Problem:\n\n- We have 2 choices for which letter we want to add: `H` or `V`.\n- We have `destination[0]` amount of `V` and `destination[1]` amount of `H`.\n- The total number of combinations possible is determined by `nCr`, where `n = H_amount + V_amount`, and `r = H_amount (or V_amount)`. For `r`, either `H_amount` or `V_amount` can be used, and **you will still get the same number.**\n- `k` is guaranteed to be in the range `1 <= k <= nCr`.\n\n# Intuition:\n\n- We need to find the k-th largest permutation of a string that consists of `H_amount` of `H` and `V_amount` of `V` in the range `1 <= k <= nCr`.\n- We can build this string letter by letter, starting from left and going to the right.\n- It has been established that, given an `H_amount` and `V_amount`, we can find the total combinations possible.\n- Using this, we can figure out how many `ranks` we jump forward when we select `V` as the next character in the string. Since `V` is larger than `H`, when we select `V` as the next letter in our string, our string will become **larger than `n` other strings that don\'t have `V` in this position.**\n\n# Example:\n\nSay, for example, we have the testcase `destination = {3,2}`, `k = 8`. We have 3 `V` and 2 `H` to work with.\n\nLets start with an empty string:\n\n    _ _ _ _ _\n\nGiven 3 `V` and 2 `H`, we have $$_{(3+2)}C_{(2)} = 10$$ combinations to work with.\n\nPretend, for one second, that we have placed a `V` in the first position of the string:\n\n    V _ _ _ _\n\nWe now have 2 `V` and 2 `H`, $$_{(2+2)}C_{(2)} = 6$$ combinations. When we placed `V` into the string, we suddenly had 6 combinations remaining.\n\nThis means that, after placing `V` in this position, whatever string built off of this one will be lexicographically larger than **AT LEAST** $$10 - 6 = 4$$ strings. To prove it, here are those 4 strings:\n\n    HHVVV\n    HVHVV\n    HVVHV\n    HVVVH\n\nAny other combination you can make with 3 `H` and 2 `V` will have `V` in the first index, thus making that string larger than these 4.\n\n**NOW**, we have established that string base `V _ _ _ _` is larger than **AT LEAST** $$4$$ strings. Therefore, the current rank for this unfinished string will be greater than or equal to $$4+1=5$$.\n\nMoving on, we can try placing in another `V` into the next free slot:\n\n    V V _ _ _\n\nThere are $$6$$ combinations left to work with. However, if we place a `V`, we now only have $$_{(1+2)}C_{(2)} = 3$$ combinations to work with. These are all the combinations that are smaller than `V V _ _ _`. Since we have already established that there are $$4$$ strings smaller than `V _ _ _ _`, we know now that there are $$7$$ strings smaller than `V V _ _ _`. They are all shown below:\n\n    HHVVV   VHVVH\n    HVHVV   VHVHV\n    HVVHV   VHHVV\n    HVVVH\n\nNow, `V V _ _ _` has a rank of $$7+1=8$$. This is our `k`. Therefore, we now want to find the lexicographically smallest string that starts with `V V V _ _ _`. Continuing to add `V` will obviously increase the rank past $$8$$, so we add `H` instead. Once we run out of `H`, we finally add the `V`.\n\nThe resulting string is `V V H H V`, which is, in fact, the 8th largest string consisting of 3 `V` and 2 `H`.\n\n# Important: \n\nWhen adding `H`, we have to decrease the total number of combinations left to work with:\n\n- We add to base rank when adding `V`.\n- When we add `H`, we maintain the current rank.\n- However, since that `H` is no longer being used, we need to decrease the total amount of combinations left we can use. Simply $$_{current(n) - 1}C_{current(r) - 1}$$ works for updating total combinations.\n\n# Code:\n```\nusing ll = long long;\nclass Solution {\nprivate:\n    // variables for calculations later\n    ll total_combinations;\n    ll base_rank = 0;\n    // combination calculation\n    ll combination(ll a, ll b) {\n        if(b > a-b) b = a-b;\n        ll ret = 1;\n        for(ll higher = a-b+1, lower = 1; higher <= a; ++higher, ++lower)\n            ret *= higher, ret /= lower;\n        return ret;\n    }\npublic:\n    string kthSmallestPath(vector<int>& destination, int k) {\n        // init starting combinations\n        total_combinations = combination(destination[0]+destination[1],destination[1]);\n        string ret = "";\n        solve(k,ret,destination[1],destination[0]);\n        return ret;\n    }\n\n    void solve(const int& k, string& ret, ll H_count, ll V_count) {\n        // base case, can\'t add any more\n        if(!H_count && !V_count) return;\n        // if you can\'t add H, add V\n        if(!H_count) {\n            ret.push_back(\'V\');\n            solve(k,ret,H_count,V_count-1);\n            return;\n        // if you can\'t add V, add H\n        } else if(!V_count) {\n            ret.push_back(\'H\');\n            solve(k,ret,H_count-1,V_count);\n            return;\n        }\n        // calculate string rank if V is inserted here\n        ll V_rank = total_combinations - combination(H_count+V_count-1,H_count) + 1;\n        // if new rank is out of bounds, add H to preserve old rank\n        // update number of possible combinations\n        if(V_rank > k) {\n            ret.push_back(\'H\');\n            total_combinations = base_rank + combination(H_count+V_count-1,H_count-1);\n            solve(k,ret,H_count-1,V_count);\n        // if new rank is within bounds, add V to increase rank\n        // update base rank for future operations\n        } else if(V_rank <= k) {\n            ret.push_back(\'V\');\n            base_rank = V_rank - 1;\n            solve(k,ret,H_count,V_count-1);\n        }\n    }\n};\n```\n
['Math', 'Recursion', 'C++']