Topcoder SRM 531

O boy! This was a tough SRM. In DIV2, only a small number of participants could solve the medium problem, and even fewer could get the hard one right. But problems were nice overall.

DIV-2 Easy; UnsortedSequence:

This one was pretty easy and race was on to get it right as fast as possible to get a better position in the final result table. What the problem asks for is the lexicographically smallest permutation of the sequence, which is not sorted in ascending order. We need to check for special cases when it isn’t possible to not have the sequence sorted in ascending order, that is a sequence having one element only, or having all elements equal. Otherwise, just sort the sequence in ascending order, which gives us the lexicographically smallest permutation of the sequence, and now swap only two elements in it so that the sequence isn’t sorted anymore. The elements to swap are the rightmost neighboring elements which aren’t equal.

DIV-2 Medium; NoRepeatPlaylist:

This was a tough one for div2 medium, and thus given a score of 600 compared to a normal medium score of 500. It can be solved using DP. Say dp[i][j] is the number of playlists that can be formed according to the rules, whose length is i, given j songs. It can be obtained by calculating the number of ways we can form a new list, by adding a new song to a playlist of length i-1, using j-1 songs, plus, the number of ways we can add an already used song to a playlist with length i-1 using j songs. The recurrence is

dp[i][j] = dp[i-1][j-1]*(N-(j-1)) + dp[i-1][j]*max(j-M, 0)

The reason for using max(j-M, 0) is that when we are selecting a previously played song, we can not select the last M songs as we must keep a gap of M songs between the same song getting played twice. For lists formed by dp[i-1][j], any M songs could be the last songs played from the total list of j songs, and we are left with only j-M songs to choose from.

Conclusion:

Was an ok SRM for me. Gained +10 in rating. I only tried hard problem after solving the easy one as it was a graph problem and I thought I would get it, but I couldn’t finalize my solution for it. Solved medium in practice room. I might update the post later to add solution for hard problem.

Be Sociable, Share!

2 thoughts on “Topcoder SRM 531

Leave a Reply