If more than half of the elements of A are equal to some x, then there will exist some i such that B_i = C_i = x, and the condition won’t be satisfied.
Suppose that there are only 2 distinct values in A. Then N is even, both values appear exactly \frac{N}{2} times, and B_i \neq C_i for each i. Let i be any index such that B_i \neq B_{i+1}. Then B[i:i+1] has the same multiset of values as C[i:i+1].
Otherwise, there always exists a solution. Let’s sort A, and let K = \lfloor \frac{N}{2} \rfloor. Then B = A, C = [A_{K+1}, A_{K+2}, \ldots, A_N, A_1, A_2, \ldots, A_K] works.
Suppose it doesn’t, and multiset(B[L:R]) = multiset(C[L:R]). Consider three possibilities.
R \le N-K. Then both B and C are sorted, and we get A_L = A_{L + K}, so at least K+1 values in A are equal, which is false.
L > N-K. Then both B and C are sorted, and we get A_L = A_{L - (N - K)}, so at least N - K + 1 values in A are equal, which is false.
L \le N-K < R.
Then we get A[L+K:N] = C[L:N-K] = B[L + R - (N - K):R] = A[L + R - (N - K):R], A[1: R - (N - K)] = C[N-K+1:R] = B[L : L + R - (N - K) - 1] = A[L : L + R - (N - K) - 1]. Again, A[L+K:N] = A[L + R - (N - K):R], A[1: R - (N - K)] = A[L : L + R - (N - K) - 1].
If L \neq 1, then from A[1: R - (N - K)] = A[L : L + R - (N - K) - 1] we get that all elements in A[1: L + R - (N - K) - 1] are equal.
If R \neq N, then from A[L+K:N] = A[L + R - (N - K):R] we get that all elements in A[L + R - (N - K) : N] are equal.
So, if both L \neq 1 and R \neq N, there are at most 2 distinct elements in A. Otherwise, WLOG L = 1, R \neq N. Then all N - (L+R - (N-K)) + 1 elements in A[L + R - (N - K) : N] are equal, that is, N - 1 - R + N - K + 1 = 2N - K - R > K elements, which isn’t possible. Case L \neq 1, R = N is similar.
What is wrong with my implementation/approach?
Approach: If the frequency of any element is > n/2 then we cannnot have an answer.
Let sort the array which will be B
Left shift B with max_freq number of steps. That is array C.
Can any one tell me the incorrectness in my code -
tc = int(input())
for t in range(0, tc):
length = int(input())
nums = list(map(int, input().split()))
Map = {}
for n in nums:
Map[n] = Map.setdefault(n, 0) + 1
if Map[n] > length // 2:
print("NO")
break
else:
freqs = sorted(set(Map.values()), reverse=True)
ans = []
# print(freqs)
for freq in freqs:
for key, value in Map.items():
if value == freq:
ans += ([str(key)] * value)
print("YES")
print(' '.join(ans))
print(' '.join(ans[Map[int(ans[0])]:] + ans[: Map[int(ans[0])]]))
For example, take a array as N = 6, A = [1, 2, 3, 4, 5, 6]. Now, K = 3. Assume a case where L = 2 and R = 4. Therefore, A is [1, 2, 3, 4, 5, 6] and B = [1, 2, 3, 4, 5, 6] and C = [4, 5, 6, 1, 2, 3]. A[L+K:N] => [5, 6], C[L:N-K] => [5, 6], B[3: 4] => [3, 4]. According to this, condition A[L+K:N]=C[L:N−K]=B[L+R−(N−K):R]=A[L+R−(N−K):R] is not satisfied. Similarly, other conditions is also not satisfied. Am I missing something?