MAXCYCSHIFT - Editorial

kuroni · June 19, 2022, 2:04pm

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Yahor Dubovik
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

2444

PREREQUISITES:

XOR, Two Pointers

PROBLEM:

EXPLANATION:

As with any cyclic shift problem, let’s duplicate the array A so that A_{N + i} = A_i for every 1 \le i \le N. We create the array B on this duplicated A similarly: B_i = A_1 \oplus A_2 \oplus \dots \oplus A_i for all 1 \le i \le 2N.

Claim: The number of distinct values on the subarray B_{[i , i + N - 1]} is the value of the array A left-shifted by i - 1 (for any 1 \le i \le N).

To see why, note that the elements of this subarray is [X \oplus A_i, X \oplus A_i \oplus A_{i + 1}, \dots, X \oplus A_i \oplus A_{i + 1} \oplus \dots \oplus A_N \oplus A_1 \oplus \dots \oplus A_{i + N - 1}], where X = B_{i - 1}. We notice that XOR-ing every element in an array does not change the number of distinct elements in this array, so the number of distinct elements in B_{[i , i + N - 1]} is the number of distinct elements in [A_i, A_i \oplus A_{i + 1}, \dots, A_i \oplus A_{i + 1} \oplus \dots \oplus A_N \oplus A_1 \oplus \dots \oplus A_{i + N - 1}], which is exactly the value of A left-shifted by i - 1.

Therefore, the problem becomes simple: we need to find the largest number of distinct elements on all subarrays of size N in B, which can easily be done using sliding window and some straightforward data structure storing occurences of values (such as std::map).

TIME COMPLEXITY:

Time complexity is O(N \log N).

SOLUTION:

Setter's Solution

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int maxN = 1e6 + 10;
ll a[maxN];
ll pref[maxN];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "r", stdin);
    int tst;
    cin  >> tst;
    while (tst--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            pref[i + 1] = pref[i] ^ a[i];
        }
        map<ll,int> mp;
        int mx = 0;
        int dist = 0;
        for (int i = 1; i <= n; i++) {
            dist += (mp[pref[i]] == 0);
            mp[pref[i]]++;
        }
        mx = dist;
        for (int i = 1; i <= n; i++) {
            dist -= (mp[pref[i]] == 1);
            mp[pref[i]]--;
            dist += (mp[pref[i] ^ pref[n]] == 0);
            mp[pref[i] ^ pref[n]]++;
            mx = max(mx, dist);
        }
        cout << mx << '\n';
    }
    return 0;
}

Tester's Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=2e5+1;
const int iu=30;
map<ll,int>mp;
int n;
ll a[N];
ll ans=0;
ll f=0;
void solve(){
	cin >> n;
	mp.clear();
	ans=f=0;
	for(int i=1; i<=n ;i++){
		cin >> a[i];
		a[i]^=a[i-1];
		f+=mp[a[i]]++==0;
	}
	ans=f;
	for(int i=1; i<=n ;i++){
		f-=--mp[a[i]]==0;
		f+=mp[a[i]^a[n]]++==0;
		ans=max(ans,f);
	}
	cout << ans << '\n';
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;while(t--) solve();
}

Editorialist's Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<long long> a(n);
        map<long long, int> occ;
        int cnt = 0;
        long long prf = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            prf ^= a[i];
            if (occ[prf]++ == 0) {
                cnt++;
            }
        }
        long long tot = prf;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            prf ^= a[i];
            if (occ[prf]++ == 0) {
                cnt++;
            }
            if (--occ[prf ^ tot] == 0) {
                cnt--;
            }
            ans = max(ans, cnt);
        }
        cout << ans << '\n';
    }
}

aging1986 · June 20, 2022, 4:07am

I would like to share my solution, although the solution in editorial is much easier and clearer than mine…

Let’s check how the number of distinct prefix XOR decreases. Suppose we start from A_i, and have same prefix XOR for A_i, ..., A_j and A_i, ..., A_k. It could be directly derived that XOR of A_{j + 1}, ..., A_k is 0. So, what we need to find out is, starting from each i, how many segments have XOR = 0.
However, naive approach of this idea costs O(N^2). Let’s now think about it reversely. If we find a range XOR of A_{j + 1}, ..., A_k is 0, how many shiftings are impacted? Answer is k + 1, ..., N, 1,..., j. So we can use a difference array to speedup. Be careful for the ranges crossing the boundary. The time complexity is O(NlogN).

shubhamjr · June 20, 2022, 12:09pm

Can anyone explain what this actually means??

neaj_morshad · June 20, 2022, 3:13pm

“We notice that XOR-ing every element in an array does not change the number of distinct elements in this array.” Proof should be added to this editorial.

xaier310 · June 20, 2022, 3:20pm

We notice that XOR-ing every element by a number in an array does not change the number of distinct elements in this array
That’s what I got

abhishek_sz · June 21, 2022, 8:05am

Not able to understand editorial, if anyone have time please explain the editorial with examples. Thanks a lot

shubhamjr · June 22, 2022, 4:49am

@ abhishek_sz

let’s take n = 3 and A = [ a1 , a2 , a3 ]
then , B = [a1 , a1^a2 , a1^a2^a3 ]

We have to perform right shift and find the maximum distinct element.

Observation 1 : Right shift and left shift, both operations gives the same result.

We take left shift because it is easy to understand and well formated.
Note: Ai means array after i shifts.

Now let’s example to understand the observation 1
( left shift )
A0 = [ a1 , a2 , a3 ] and B0 = [a1 , a1^a2 , a1^a2^a3 ]
A1 = [ a2 , a3 , a1 ] and B1 = [a2 , a2^a3 , a2^a3^a1 ]
A2 = [ a3 , a2 , a1 ] and B2 = [a3 , a3^a2 , a3^a2^a1 ]

( right shift )
A0 = [ a1 , a2 , a3 ] and B0 = [a1 , a1^a2 , a1^a2^a3 ]
A1 = [ a3 , a1 , a2 ] and B1 = [a2 , a3^a1 , a3^a1^a2 ]
A2 = [ a2 , a3 , a1 ] and B2 = [a2 , a2^a3 , a2^a3^a1 ]

Now, we can see clearly that right and left shifts both gives same results

Now, before moving to observation 2 we have to see the brute force approach

In Brute force approach you simply perform the shift one by one and make it’s corresponding B array, and then find count of distinct elements in that array.

Let’s do it
Note : We are doing the left shift here

A0 = [ a1 , a2 , a3 ] and B0 = [a1 , a1^a2 , a1^a2^a3 ]
A1 = [ a2 , a3 , a1 ] and B1 = [a2 , a2^a3 , a2^a3^a1 ]
A2 = [ a3 , a2 , a1 ] and B2 = [a3 , a3^a2 , a3^a2^a1 ]

Now if you observe B1, the elements are
a2
a2^a3
a2^a3^a1

Now if we XOR the whole array B1 with B[0], which is a1 then,
a1^a2
a1^a2^a3
a1^a2^a3^a1 = a2^a3

let X = XOR of all elements of array A. Here, X = [ a1^a2^a3 ]

Now , you can observe that the first two elements of B1 was already present in B0
The only new element which we found here is a2^a3, which is formed by taking the XOR of a1 ^ X means a1 ^ ( a1 ^ a2 ^ a3 )

Now, the count of distinct elements in B1 = count( distinct elements of B[0] ) + no. of distinct elements in B[1] - the elements which present in B[0] but not in B[1].

Now, similarly for B2 , the elements are
a3
a3^a2
a3^a2^a1

Now, if we XOR the whole array B2 with B[1] which is a1^a2 then,
a1^a2^(a3)
a1^a2^(a3^a2) = a1^a3
a1^a2^(a3^a2^a1) = a3.

Here, the distinct elements are a1 ^ a3 and a3

Observation 2 : You can find the distinct elements by taking X ^ B[ i ]

kskheni · June 24, 2022, 4:56am

I am assuming that you understood everything till the point where we append the array to itself.

Now what “We notice that XOR-ing every element in an array does not change the number of distinct elements in this array” this particular line means is that if there is an array say
A = [1, 2, 3, 4, 3, 5]
then if you XOR all the elements in this array by a particular number say X, then whatever resultant array you get will have same number of distinct elements as the original array.

Why? What happens when we XOR two numbers, a and b?
For all the positions at which b is set to 1, a’s value will flip,
and for positions where b is set to 0, a will stay it is.

All in all, when we XOR all elements of array A with X, the positions where X is set to 1 will flip for all the elements of array, which will not affect the number of distinct elements in array.
X = 4 = 100, the 3rd position from right will get flipped for all members of array.
X = 7 = 111, all 3 positions from right will get flipped.

If you are still having difficulty understanding it, then try doing a dry run on the given array by taking some values of X.

Now coming to the solution of this problem:

append the array to itself.
A = [1, 2, 3, 4, 3, 5, 1, 2, 3, 4, 3, 5]
calculate B for this array where B[i] = XOR of all elements till i.
A = [1, 2, 3, 4, 3, 5, 1, 2, 3, 4, 3, 5]
B = [1, 3, 0, 4, 7, 2, 3, 1, 2, 6, 5, 0]
now if we take a subset of B which starts from index i and has length N, then we get i-1 times left-shifted B which has been XORed by the same number B[ i-1 ], so as we discussed earlier, the number of distinct elements in this subarray will not get affected by that XOR operation.
Hence all we have to do now is take all N-sized subarrays of the B, and find largest number of distinct elements from all those subarray. The methods for doing that are mentioned in the editorial.

Hope this helps!!!

yadavlav7978 · June 24, 2022, 5:02am

Let we have an array {a,b,c,d} where all are distinct element.
and if we xor of all element with some elemnt X then all xoring comes distinct;
a^x
b^x
c^x
d^x
all are distinct.
because when we xor two distinct number with same elemnt x then they always comes distinct
(a^x and b^x) both are distinct.

keshav_kaal · June 24, 2022, 5:02am

why can’t you use simple language. what do you mean by duplicate array in first line. why are you taking duplicate array with same name as original array as Ai…
I am able to get first paragraph itself. disgusting…

flying_rhin_o · June 24, 2022, 5:02am

“We notice that XOR-ing every element in an array does not change the number of distinct elements in this array”

By this do you mean Xor-ing every element of prefix xor array from Ai to A(i +N-1) with some number let’s say X, doesn’t change the number of distinct elements in prefix xor array?

mihir_314 · June 25, 2022, 5:19am

Good problem. I don’t know why i thought of some complex data structure for update and all. I had made the observation that xoring with constant prefix doesn’t change the distinct values but was unable to proceed further.