Magarr - editorial

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Danya Smelskiy
Tester: Lewin Gan and Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY:

Medium

PREREQUISITES:

Implementation, Observations.

PROBLEM:

Given an array A of length N, a magical sequence is defined as the sequence where either of the following is true for all elements of the sequence.

  • The element is zero.
  • The element is equal to the minimum distance from the current element to the nearest zero in the array.

Also, sequences having no zeroes are considered non-magical.

Find out any permutation of A which is a magical sequence, or determine if it doesn’t exist.

QUICK EXPLANATION

  • Let us call an x-straight as sequence 1,2,\ldots (x-1), x. We can see that if we can use all elements of the array A to make some straights, it is not possible to make a magical sequence.
  • Now, between any consecutive pair of zeroes, the elements are of form 1,2,\ldots (x-1), x, (x-1) \ldots,2,1 or 1,2,\ldots (x-1), x, x (x-1) \ldots,2,1 (due to first x elements being near to zero to left and vice versa). We try to make pairs from largest to smallest, trying to make as many even pairs. If we are not able to pair all the straights, it is impossible to make magical sequence (exception in next point).
  • Now, Considering borders, we see, that we can place one straight at one border. This allows us to place two unpaired straights without affecting other pairs.
  • If we made x pairs and have at most two terminals, we need at least x+1 zeroes. Edge case might be when we have all straight paired with no terminals and number of zeroes to be exactly equal to the number of pairs, in which case, we need to split one pair, and use both the straights at either end.

EXPLANATION

Let us define an x-straight as the set of elements from 1 to x. If we cannot split all the elements of input array into a number of straights, (which happens only when the frequency of i+1 > frequency of i for some i \geq 1), we can never obtain a magical sequence. The reason is, if a position is at distance x from nearest zero, at least one of the adjacent position is at distance x-1 from nearest zero. So, for every occurrence of x, we need one occurrence of x-1.

Finding the number of straights can be easily done in a single loop, give it a try, or refer the secret box below.

Click to view

In decreasing order of i, set f[i] = f[i]-f[i+1] while i \geq 1, where f[i] denote frequency of i in input array A.

Now, after checking the above condition, we need to pair them. Considering only the elements between two consecutive zeroes for now.

Let us observe some example magical sequences.


0 1 2 3 4 4 3 2 1 0		
0 1 2 3 4 5 4 3 2 1 0		
3 2 1 0 1 2 3 2 1 0 0 0 1 2 3 4

In the first example, we have paired two 4-straights, one in increasing order and one in decreasing order, and we can see, that all the values are valid. In the second example, we have paired one 4-straight with one 3-straight, and still, the distances are correct. If we try to pair x-straight with some y-straight (|x-y| \geq 2, The distance in at least one of the straight would go wrong, so we can only pair an x-straight with another x-straight or an (x-1)-straight.

Now, since we want to pair as many straights as possible, it makes sense to pair x-straights with itself as many times as we can. (Though other pairings may also work). So, while f[i] \geq 2, pair two straights. Now, if we have an i-straight try to pair it with (i-1) straight. If we can, well and good, otherwise let us add this straight to a special set called terminal. (I’ll discuss it).

After making all pairings, we need to consider borders now. See the third example above. Before first 0, we have an unpaired straight and after last zero, we have another unpaired straight. So, this implies we can use the unpaired straights at the border.

So, final construction looks like to make as many pairs as possible, make pairs and add remaining into our special set. We have to satisfy two conditions now.

  • The number of straights in the terminal set is less than or equal to two.
  • The number of zeroes in the input array is at least one more than the number of pairs. (Because we need two zeroes at either end of pair.)

The only adjustment we can make is by considering the 1-straights, which are a special case since magical sequence 0 1 0 is valid. So, a 1-straight can be used as terminal as well as an odd pair in itself. We can make an appropriate choice here so as to satisfy both conditions. If we satisfy, we can construct the magical sequence from these pairs and information, otherwise, the solution is impossible.

The construction is easy and can be referred from solutions below.

Time Complexity

Time complexity is O(N*log(N)) (May also come out to be O(N) depending upon implementation).

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: