My algorithm was fairly simple and done in haste.
Let N = 5, M = 3, S = âabcdeâ, PrettyMelodies = [(âaaâ, 3), (âbbâ, 4), (âcccâ, 5â)].
My algorithm was basically two different algorithms merged together.
If A == 0,
My target string would be PPP⌠where, P is the prettiest string available.
In this example, my target String is: âcccdeâ, because âcccâ is the prettiest among the given pretty melodies. This is done until the target is achieved or the budget is exhausted.
If A > 0 and GoodStrings = [(âaabâ, 1), (âbbcâ, 2)],
Here, I tried to find the prettiness to cost ratio for each good string, which would be 3/1 for âaabâ and 4/2 for âbbcâ.
Now, my target string would be QQQ, where Q is the good string having the highest prettiness to cost ratio, which is âaabâ here.
So, here my target string is âaabaabaabaabaabâ
Lastly, if I still had >= R coins left with me, I copied the whole string using the third operation.
Luckily, this solution managed to fetch me 12 points.
My best solution: CodeChef: Practical coding for everyone