Fast combinatorics, iterative
Intuition\nWe can calculate positions of each \'V\' by iteratively using "stars and bars" theorem of combinatorics.\n\n# Complexity\nO(n+m), n - number of H\'s,
# Intuition\nWe can calculate positions of each \'V\' by iteratively using "stars and bars" theorem of combinatorics.\n\n# Complexity\nO(n+m), n - number of H\'s, V - number of V\'s.\n\n# Code\n```\nclass Solution {\npublic:\n    long long stars_and_bars (long long n, long long k)\n    {\n        int result = 1;\n        int dev = 1;\n        for (int i = n + 1; i <= n+k-1; ++i)\n        {\n            result *= i;\n            if (result % dev == 0 && dev <= n+k-1 - n)\n            {\n                result /= dev;\n                ++dev;\n            }\n        }\n        return result;\n    }\n\n    string kthSmallestPath(vector<int>& destination, int k) {\n        std::vector<int> v_positions(destination[0], destination[1]);\n        \n        for(int i = 0; i < v_positions.size(); ++i)\n            v_positions[i] += i;\n        \n        int result = 1;\n        int leftmost_pos = -1;\n        for(int i = 0; i < v_positions.size(); ++i)\n        {\n            int j = v_positions[i];\n            int new_iteration_result = 0;\n            for (; j > leftmost_pos && i < v_positions.size() - 1; --j)\n            {\n                int peregorodki = v_positions.size() - i;\n                int stars = v_positions[i+1] - j;\n                \n                new_iteration_result = stars_and_bars(v_positions.size() - i - 1, stars);\n\n                if(result + new_iteration_result >= k)\n                { \n                    if (result + new_iteration_result == k)\n                    {\n                        result += new_iteration_result;\n                        v_positions[i] = j - 1;\n                    }\n                    else\n                        v_positions[i] = j;\n                    break;\n                }\n                else\n                    result += new_iteration_result;\n            }\n            for (int j = v_positions[i]; j > leftmost_pos && i == v_positions.size() - 1; --j)\n            {\n                if (result + new_iteration_result == k)\n                {\n                        result += new_iteration_result;\n                        v_positions[i] = j;\n                        break;\n                }\n                ++new_iteration_result;\n            }\n            leftmost_pos = v_positions[i];\n            if (result == k)\n                break;\n        }\n\n        std::string path_string(destination[1] + destination[0], \'H\');\n        for (auto e: v_positions)\n            path_string[e] = \'V\';\n        return path_string;\n    }\n};\n```
['C++']