November 22, 2018 Problem Of The Week: Greedy Algorithms, Math And Permutations

This week, we’ll analyze a problem from SRM 497. This problem featured as the Division I Level One problem and the Division II Level Two problem.
The summary of the problem is as follows –
Given a string S of size N consisting of “I”s and “D”s, where an “I” denotes a pair in ascending order, and a “D” denotes a pair in descending order, construct the lexicographically smallest permutation of size N+1 consisting of the first N+1 natural numbers that match the string’s characters, if possible.
For example,
“DDI” would generate “3 2 1 4” as when we check every adjacent pair, the order is “decreasing-decreasing-increasing”
Similarly, “IID” would generate “2 3 4 1” or “1 2 4 3” — so our answer here would be “1 2 4 3” as we need to generate the lexicographically smallest result.
Let’s break the problem into two parts –
1. What do we if we encounter “I” –
Since we’re dealing with a permutation of numbers, we can’t repeat numbers and so the smartest move we can make is assign the new number to the value of the smallest number larger than all current numbers.
Thus, if we’re looking at the Xth index, the smallest number larger than all previous numbers in our current permutation will be X. This statement can be proved by induction.
2. What do when if encounter “D” –
A “D” implies the next number in the permutation is smaller than the current number at the end of the permutation, implying that we need to insert a smaller number.
Upon inserting this smaller number, we’ll have to iterate over the permutation again and make sure we increment every element greater than or equal to this new number to “make space” for it and preserve the uniqueness of each element.
So the question now comes down to “which number to insert?”
Let us re-insert the current last number and then iterate over all previous elements and increment only those elements greater than or equal to the new last element.
The reason this mathematically works is because for all previous elements greater than or equal to the new last element –

• If X < Y then X+1 < Y+1
• Similarly, if X > Y, then X+1 > Y+1

Thus we are allowed to add 1 to all numbers greater than or equal to the new last number.
And as to WHY we’re adding 1 only to the elements greater than or equal to the new last number, is because we want to maintain our lexicographically least permutation while still maintaining the validity of the input string.
If we were to insert any other smaller element at the end, more previous elements would be incremented and thus our permutation may not be the lexicographically smallest.
And thus, we can solve the problem in O(|S|^2)
The fastest solution in Div 2 was by HDU_Lost who solved it in a little over 8 minutes.
The fastest solution in Div 1 and overall, was by UdH-WiNGeR who solved in just a little over 3 minutes!
His implementation follows the same algorithm mentioned above – https://community.topcoder.com/stat?c=problem_solution&cr=22221928&rd=14426&pm=11115