Hello Everyone :) As there is no editorial for the challenge problem I request anyone who solved the Feb19 Challenge problem Chef with Orchestra in the Kitchen to tell about there approach which they used and how did they manage to get high scores . This discussion will benefit everyone and will allow other coders to learn and get good scores in the challenge problems. I request all the people who got very high points in the challenge problem to discuss about there approach , so that we can learn and get better. Thank You :) asked 16 Feb, 14:04

As @rahuldugar said, first operation was pretty useless due to it's cost and no of operations. Even I didn't bother much about them in my approach. I did a random approach. Imagine you have original string S and a good string G with a particular pretty value (say PV) with Cost Q. As you have x coins.
I CONSIDERED THE ABOVE TWO CASES FOR EVERY GOOD STRING AND FINALLY CHOSE THE BEST ONE OUT OF THOSE. NOTE 
But I did considered the possibility of this approach, getting a TLE for N=20000, due to its TimeComplexity taking 10^9 operations in the worst case. I implemented the KMP algorithm to reduce the time comlexity. Surprisingly, the code without it also got an AC. :) I got 18 points for the above approach. Links to my best Solution: answered 17 Feb, 15:25
1
KMP doesn't have better time complexity on randomly generated strings. The naive method will be $O(n) time complexity because the degenerate cases are nearly impossible, and KMP will only get a linear speed up.
(17 Feb, 17:56)
@bad_jim My intention was to get a linear speed up only. In order to count the number of occurrences of a pretty string in a good string, Suppose size of good string is N and pretty string is M. Earlier I was counting it's occurence in O(N*M) but after KMP, it was just O(N+M). Actually As there are 10000 good strings and 100 pretty strings, the complexity was O(10000 x 100 x N*M), originally.
(17 Feb, 18:46)

First operation was useless in my approach as it is prohibitively expensive and takes too much operations. My approach was to pick prefixes and combination of prefixes which were feasible i.e., had low cost and compute how much gain we can get by repeating them. To compute the gain fast so that I could try more combinations, I made a trie of all pretty strings. By carefully fixing parameters(cost of the feasible good strings) I was able to get 92 points by it. My best solution link: https://www.codechef.com/viewsolution/23022212 answered 17 Feb, 14:54

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, If A > 0 and GoodStrings = [('aab', 1), ('bbc', 2)], Now, my target string would be QQQ, where Q is the good string having the highest prettiness to cost ratio, which is 'aab' here. 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: https://www.codechef.com/viewsolution/23070455 answered 16 Feb, 15:13

Even I agree that the first operation was pretty useless, so I focused on the second and third operations. My approach was very random, and I believe I was pretty lazy to optimize code (which I could have done, but when I saw I was getting fairly high scores as compared to others, I felt even lazier!). I just fine tuned my existing code every time to see the change in score. I sorted the Good Melodies in decreasing order of length (with minimum cost first), because I thought that it is more probable for a Pretty Melody to overlap with a long string than a short string (I also tried with short strings but this one did fairly better, so I thought my assumption was right). if (A == 0) Replace the current string with copies of a Pretty Melody of shortest length with highest pretty value using the first operation (short length because you can have more of them in the string then). And at the end try to do the third operation if possible. else Keep on pumping the string with the first good melody (in the way I sorted them) till the string length becomes at most half of the given limit $(10^6)$, so that I can force the third operation (also spending at most $X  R$ coins for the second operation), and then do the third operation at the end. The major thing I did was to kept a track of the scores for the initial string, and for the first $3$ Good Melodies according to my sorting. If in case the initial string was better and it's score was positive, I tried to do the third operation on it (if possible), and printed the steps for it, otherwise whichever of those $3$ were better was printed. I could have done much better but I made a very haphazard code and due to my laziness, I even skipped various approaches which came to my mind. But still I somehow managed to get a score: 3555850.97, which is 12.72046 points relatively according to Division 1. Here's my best solution link: https://www.codechef.com/viewsolution/23054854 answered 17 Feb, 17:13

I just repeated some pretty string a few times and used DP to calculate the minimum cost of creating it using prefixes of good strings. I tried all possible pretty strings. A further improvement of 20% was yielded by doing DP to minimize the number of operations. This yielded me about 0.539 pts (i.e. my score was 53% of the max score). The main thing is to use Type 2 operations as much as possible. The bottleneck in my solution was the number of operations. Type 3 operation was used at the end to double the score. answered 18 Feb, 17:23
