DIFSUBARRAYS Editorial

DIFFICULTY:

2145

Let’s make several observations:

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

1 Like

Another Approach:

  • Make vector<pair<freq, number> > V //pair<freq[a[i],a[i]>

  • sort it with decreasing order in freq

  • if(V[0][0] > (n/2) || v.size()<=2) → not possible //max freq allowed is (n/2)

  • First array = V[0…] in expanded form. (print v[i][1] as v[i][0] times)

  • Second array = V[1…] V[0] in expanded form

e.x original - 1 1 2 2 3 3 4 4 4
V = {3, 4}, {2,3}, {2,2}, {2,1}. //freq, num
A = expanded(3, 4}, {2,3}, {2,2}, {2,1}) - 4 4 4 4 3 3 2 2 1 1
B = expanded({2,3}, {2,2}, {2,1}, {3, 4}) - 3 3 2 2 1 1 4 4 4 4

11 Likes

Easy to understand:

store a in b and sort b(sorting is done according to value, by frequency is not necessary). Find the maximum frequency of element, call it mx;

if mx > n/2 or different integers == 2 then answer is not possible.

Otherwise, store b in c, and rotate c mx times(left or right both works).

b and c are the required arrays

4 Likes

what is wrong with my approach ?
(Solution: 64019582 | CodeChef)

@trygub_adm already gave that hint in the samples :smiling_imp:.

Screenshot from 2022-05-02 08-13-57

2 Likes

https://www.codechef.com/viewsolution/64064566

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.

A = [1,1,2,2] Correct answer = NO, your code gives YES 1 1 2 2
2 2 1 1
take i = 1, j = 2 (0-based indexing)

First of all you are not printing “YES”. And your solution fails for this case: A = [1,1,2,2]

congrats for 5 star @suman_18733097 .

1 Like

Hi , can you provide a test case where my code fails Here is my code.

i was thinking in a similar manner, you made it very clear :slight_smile: thank you

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])]]))



A  hide corner case 

different integers == 2 then answer is not possible

Your code will fail for even size array with only two distinct elements. e.g.

1
4
4 4 5 5

Expected Output:

NO

Your Output:

YES
4 4 5 5 
5 5 4 4 
1 Like

Okay, got it.

can you elaborate a little why the ans is no.

sorry for mentioning wrong URL , link updated.

For the given array [2 2 3 3] the only possible permutation such that B[i] != C[i] (i.e. trivial case) is:

[2 2 3 3]
[3 3 2 2]

But this is not a valid B,C since B[1:2], C[1:2] are permutations of each other.
Therefore, the answer will be “NO”.

@trygub_adm

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?