PROBLEM LINK:Setter: Hasan Jaddouh DIFFICULTY:Easy PREREQUISITES:Prefix, Just Oberervation. Understanding of sort will be helpful. PROBLEM:Given array $A$ of length $N$, determine, whether by removing a prefix of array $A$ and appending it at the end (called a move), can we make the array sorted SUPER QUICK EXPLANATION
EXPLANATIONLet us consider a slow solution first. Assume $N = 1000$. There are $N$ prefix we can choose any one to remove from front and append to end of array. So, for every prefix, we try to remove it from front, append it at back (using additional array) and check if we got the sorted sequence. If the sequence is sorted for any prefix, answer is YES, Otherwise answer is NO. Clearly, we make a move in $O(N)$ time and for each move, checking if sequence is sorted, takes $O(N)$ time, resulting in $O(N^2)$ time, which passes all but last subtask. For last Subtask, we need to do some work. Suppose we have a set of pair of adjacent positions. Set contains pair (i, i+1), if $A[i]>A[i+1]$. (Consider cyclic array. That is, Last element is adjacent to First element of given array) If size of set is greater than 1, answer is always NO. Otherwise YES. That's all. I know you guys are saying like, how does this editorialist not explain this statement. :P To avoid this, here's the explanation. :D If set is empty, this means all elements are same (Set will be empty when case like 2 2 2 2 2 occur.) Otherwise, size of set is guaranteed to be greater than or equal to 1. Because there will exist atleast one position such that $A[i]>A[i+1]$. Answer in this case is YES, since all elements are in sorted order. Think about some examples when the size of set will be 1. After you have thought enough, It can be seen, that only a Cyclic Shift of a sorted array can have only 1 position pair (x, x+1) (Where $A[x]$ is the last position of sorted array, while $A[x+1]$ is first element of sorted array before shift. For such case, we can just take prefix $[1, x]$ and put it at end of array to get the sorted array, thus answer is YES in this case too. Now, If size of such set is above 1, There are atleast 2 position pairs where $A[i]>A[i+1]$. We can see that by no matter what prefix we choose, we cannot get sorted array, since by taking one prefix, we can reduce count of such position by one in final array. Also, a Sliding window implementation is also possible using same idea of set of position pairs, which is left as an exercize. Time ComplexityTime complexity is $O(N*logN)$ due set operations. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 19 Oct '18, 04:48

I used an approach where I check for the first occurrence of the minimum element in the array, then iterate over the loop starting from that position in a cyclic fashion, checking whether the preceding element is more than the succeeding element. But I'm getting a WA. Can anyone tell me what's wrong with my approach? Here's my solution answered 23 Oct '18, 09:37
