×

# CARDMGK - EDITORIAL

Tester: Misha Chorniy
Editorialist: Taranpreet Singh

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

• If $x$ is index of leftmost occurence of smallest element, we remove the prefix $[1, x-1]$ (Nothing if $x$ is 1.) and append it to end of array.
• If this array is sorted, answer is YES, otherwise it can be proven that we cannot sort the array by sqapping prefix.

# EXPLANATION

Let 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 Complexity

Time complexity is $O(N*logN)$ due set operations.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

4.0k31104
accept rate: 22%

19.8k350498541

 1 It can be done in $O(n)$ as well. My Soln. answered 21 Oct '18, 19:36 2.7k●1●6●18 accept rate: 10% Yes, I know. Simple idea, count number of unbalance positions. Editorial is detailed to make it understandable for beginners. (21 Oct '18, 19:49)
 0 The problems for practise aren’t up yet answered 21 Oct '18, 19:52 3★druh 1●2 accept rate: 0%
 0 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 1 accept rate: 0% Did you find the error I too was having the same problem? (25 Oct '18, 18:47)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,820
×801
×727
×267
×39
×36
×3

question asked: 19 Oct '18, 04:48

question was seen: 817 times

last updated: 15 Feb, 11:23