Feb19 Challenge Problem Discussion

general
, , ,
1

Hello Everyone :slight_smile:

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 :slight_smile:

3 Likes
2

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. :slight_smile:

My best solution: https://www.codechef.com/viewsolution/23070455

1 Like
3

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

2 Likes
4

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.

  1. Then if you perform only operations
    of type 2    , you can replace at-most
    x/Q substrings of S with G to get a
    total pretty value = PV*(x/Q)

  2. Then I also considered operations of type 3. Then you reserve R coins for type 3 operation. Remaining (x-R) coins were used for type 2 operations, as in previous points to get total Pretty Value = PV * [(x-R)/Q]. Then, type 3 operation to get Final Pretty Value = 2 * PV * [(x-R)/Q]

I CONSIDERED THE ABOVE TWO CASES FOR EVERY GOOD STRING AND FINALLY CHOSE THE BEST ONE OUT OF THOSE.

NOTE -

  1. I ignored the possibility of overlap, as I said I also mentioned in the beginning, it’s just a random approach.
  2. Beware of the size of the original string N. If (x/Q)>N, you can’t atmost apply N operations of type 2 on the string. And do check separately, if Q=0.

But I did considered the possibility of this approach, getting a TLE for N=20000, due to its Time-Complexity 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. :slight_smile:

I got 18 points for the above approach.
Links to my best Solution:-

Without KMP

With KMP

3 Likes
5

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

1 Like
6

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.

1 Like
7

@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.

8

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.

https://www.codechef.com/viewsolution/23020150

1 Like