CARDMGK - EDITORIAL

general
, , , , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

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

  • 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. :stuck_out_tongue:

To avoid this, here’s the explanation. :smiley:

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:

Setter’s solution
Tester’s solution
Editorialist’s solution

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

2

It can be done in O(n) as well. My Soln.

1 Like
3

Yes, I know.

Simple idea, count number of unbalance positions.

Editorial is detailed to make it understandable for beginners.

4

The problems for practise aren’t up yet

5

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

6

Did you find the error I too was having the same problem?