HackerRank - "String Modification" - Tonix - 博客园
An ACM-level problem because it involves "advanced maths". It should not be marked as "Moderate". Other than that, it is a medium level DP one.
*Math modeling in your mind: can you see through the problem statement and figure out that it isa DP-style letter choice process? I couldn't.. This is so crucial, however.
*DP Part: there is dependency between letters: you should pick higher chars then lower chars, and DP choice occurs during this process.
*Maths Part: C(m + n, n) is used, but the numbers are huge, so regular combination formula is not working here. Lucas Theorem is necessary here (http://en.wikipedia.org/wiki/Lucas%27_theorem), which I will try to understand later..
I checked Editorials, understand it and then rewrite their Jave code into my solution in C++ (it looks almost the same).
Read full article from HackerRank - "String Modification" - Tonix - 博客园
No comments:
Post a Comment