Suppose, you have N consecutive numbers. You need to arrange them in such a way that, after arranging, subtraction between any two adjacent number will not be same. Numbers at index 1 and N will be considered adjacent. And also, you must put number 1 at index 1. For example, when N=4, [ 1 ] , [ 3 ]<---(+2), [ 4 ]<---(+1), [ 2 ]<---(-2), [ 1 ]<---(-1)
this is a valid arrangement.
Is there any approach to find a O(N * log N) solution? Thanks in advance.
Without the constraint that $$$N$$$ and $$$1$$$ are considered adjacent, you can do this in $$$O(N)$$$ by going to $$$1 \rightarrow N \rightarrow 2 \rightarrow (N-1) \rightarrow 3 \rightarrow \ldots$$$.
To see that the differences are all distinct, consider the subsequence of positive differences and note that it's strictly decreasing. Similarly, if you consider the subsequence of negative differences, their absolute value is strictly decreasing as well.
By the way, this is a simplified (1D instead of 2D) version of a recent Codeforces problem, 1179B - Tolik and His Uncle.
Maybe this idea for a construction leads to a solution for your problem?
You are right! I wanted to solve exactly that problem and found this problem. In the mentioned problem, you could use 0 as the subtraction, but not in this case. I haven't seen the editorial of that contest since I wanted to solve that problem. But my approach requires this above problem to be solved. I just wanted to know if this above problem can be solved or not. I necessarily didn't ask for the solution.
Thanks for your time brother :D
If you say that the elements at index 1 and n are adjacent that means we want a total of n distinct adjacent differences. If the sequence was needed to be strictly increasing, The minimum difference is 1 and maximum is n — 1. So we can have only n — 1 distinct differences whereas the problem requires n differences. So the problem seems unsolvable. But here the differences can be negative as well.
The differences can be positive or negative, as in the example.