Link : GONESORT
Category : Sequences, ad-hoc
Hint : What are the books that need not be moved. Try to find maximum set of such numbers.
Solution : Let the sequence be of N numbers, a1,a2,a3 . . . aN, and let the sorted sequence be b1,b2,b3 . . . bN. Suppose the numbers bi,bi+1,bi+2. . . bj are such that in sequence {a}N, they appear in same order (bi+k occurs before bi+k+1, but there can be other numbers apart from bi to bj in between them). In this case, all numbers apart from this subsequence can be put to order in N-(j-i+1) steps.
Category : Sequences, ad-hoc
Hint : What are the books that need not be moved. Try to find maximum set of such numbers.
Solution : Let the sequence be of N numbers, a1,a2,a3 . . . aN, and let the sorted sequence be b1,b2,b3 . . . bN. Suppose the numbers bi,bi+1,bi+2. . . bj are such that in sequence {a}N, they appear in same order (bi+k occurs before bi+k+1, but there can be other numbers apart from bi to bj in between them). In this case, all numbers apart from this subsequence can be put to order in N-(j-i+1) steps.
Now the problem is to find maximum contiguous increasing sequence in given set (maximum length sequence such that it appears continuously in sequence {b}N and appears in increasing order in {a}N It can be easily done in O(N2)
Code:
No comments:
Post a Comment