LOSTARRAY_ - Editorial

PROBLEM LINK:

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

Setter: Jeevan Jyot Singh
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

1889

PREREQUISITES:

XOR

PROBLEM:

JJ had an array A of length N such that 0 \le A_i \lt 2^{30} for all 1 \le i \le N.
He listed down the XOR of all the subsequences of A of size \ge (N - 1) in some random order. Let’s call the XOR of these (N + 1) subsequences as B_1, B_2, \ldots, B_{N+1}.

Unfortunately, he lost the initial array A. Can you help him recover it?

EXPLANATION:

If we can recover XOR of all elements (which I will denote as X), then we can solve the problem easily: apart from one B_i that is equal to X, the elements of the arrays are B_j \oplus X. For example, if B = [27, 15, 23, 30, 29, 31] and X = 31, then A = [27 \oplus 31, 15 \oplus 31, 23 \oplus 31, 30 \oplus 31, 29 \oplus 31].

Let’s divide into two cases (the pretests even hinted us to do this!):

  • When N is odd, X is actually equal to XOR of all B's. This is because each A_i is included in an odd amount of B_j's, so when we XOR B's together A_1 \oplus A_2 \oplus \dots \oplus A_N remains.
  • When N is even, notice that the XOR of all B's is equal to 0, so we can’t easily recover an X. However, we can simply let X to be any B in this case, and the resulting construction will work. We can verify this by calculating the XOR of all subsequences of A with size no less than (N - 1), and see that this coincides with B.

DETAILED EXPLANATION

Case 1: When N is odd:

Let S = A_1 \oplus A_2 \oplus \dots \oplus A_N.

We note that each of the N+1 inputs is either S, or A_1 \oplus A_2 \oplus \dots \oplus A_{j-1} \oplus A_{j+1} \oplus \dots \oplus A_N, for some j. We also note that A_1 \oplus A_2 \oplus \dots \oplus A_{j-1} \oplus A_{j+1} \oplus \dots \oplus A_N = S \oplus A_j.

So the N+1 inputs are \{ S, S \oplus A_1, S \oplus A_2, \ldots ,S \oplus A_N\}, in some jumbled order.

Claim 1:

When N is odd, B_1 \oplus B_2 \oplus \dots \oplus B_N \oplus B_{N+1} = S.

Proof

B_1 \oplus B_2 \oplus \dots \oplus B_N \oplus B_{N+1} = S \oplus (S \oplus A_1) \oplus (S \oplus A_2) \oplus \ldots \oplus (S \oplus A_N).
This was just replacing the elements as noted above.

S occurs N+1 times in that XOR. And since N is odd, N+1 is even, and all those S s cancel out each other (since a \oplus a = 0, for any a). Hence we are left with A_1 \oplus A_2 \oplus \dots \oplus A_N = S.

Hence proved.

And so, we can find S by just XOR-ing all the N+1 inputs.

We are also guaranteed that S is one of the N+1 inputs. So we can ignore that element. And so now we have N inputs, which are \{S \oplus A_1, S \oplus A_2, \ldots ,S \oplus A_N\}, in some jumbled order. We XOR each of those N elements with S, to get the set \{A_1, A_2, \ldots, A_N\} and output them. And we are done.

Case 2: When N is even:

Claim 2:

When N is even, B_1 = B_2 \oplus B_3 \oplus \dots \oplus B_N \oplus B_{N+1}.

Proof

Similar to the proof of Claim 1, we end up with N+1 S s, but since N is even, the XOR of them is S. And the other elements also XOR to S, and so S \oplus S = 0. So, we have that B_1 \oplus B_2 \oplus \dots \oplus B_N \oplus B_{N+1} = 0$.

Since the XOR of all input elements is 0, we know that any single input element is equal to the XOR of all the other N input elements. (ie. if a \oplus b = 0, we can XOR b on both sides and conclude that a = b).
In particular, we have that B_1 = B_2 \oplus B_3 \oplus \dots \oplus B_N \oplus B_{N+1}.
Hence proved.

Claim 3:

The array ( (B_1 \oplus B_2), (B_1 \oplus B_3), (B_1 \oplus B_4), \ldots, (B_1 \oplus B_N), (B_1 \oplus B_{N+1})) is a valid initial array A, which we can output.

Proof

To show that this is a valid output, we need to show that set of XORs of all the N+1 subsequences of size \ge N-1 of this array is equal to the given input set \{B_1, B_2, \ldots , B_{N+1}\}.

The XOR of the subsequence of size N is ( (B_1 \oplus B_2) \oplus (B_1 \oplus B_3) \oplus (B_1 \oplus B_4) \oplus \ldots \oplus (B_1 \oplus B_N) \oplus (B_1 \oplus B_{N+1})). Here, we see that B_1 occurs N times, and since N is even, they all cancel out each other. So we are left with B_2 \oplus B_3 \oplus \dots \oplus B_N \oplus B_{N+1}, which according to Claim 2, is just B_1.

Each of the N-1 sized subsequences will have an XOR of the form ( (B_1 \oplus B_2) \oplus (B_1 \oplus B_3) \oplus \ldots \oplus (B_1 \oplus B_{j-1}) \oplus (B_1 \oplus B_{j+1}) \oplus \ldots \oplus (B_1 \oplus B_{N+1})), for some 2 \le j \le N+1.
We see that B_1 occurs N-1 times, which is odd, and so B_1 will exist once. So we are left with B_1 \oplus B_2 \oplus B_3 \oplus \ldots \oplus B_{j-1} \oplus B_{j+1} \oplus \ldots B_{N+1}. Now, we replace B_1 with B_2 \oplus B_3 \oplus \dots \oplus B_N \oplus B_{N+1} (due to Claim 2), and so everything cancels out except for B_j.

Thus, each of the N-1 sized subsequences will have an XOR of the form B_j for some 2 \le j \le N+1.
So along with the B_1 that we got above, we see that the set that we get if we start out from this N sized array is exactly \{B_1, B_2, \ldots , B_{N+1}\}.

Hence proved.

TIME COMPLEXITY:

Time complexity is O(N).

SOLUTION:

Setter's Solution
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const long long INF = 1e18;

const int N = 1e6 + 5; 

void solve()
{
    int n; cin >> n;
    vector<int> b(n + 1);
    for(int &x: b)
        cin >> x;
    if(n % 2 == 0)
    {
        for(int i = 1; i <= n; i++)
            cout << (b[0] ^ b[i]) << " ";
    }
    else
    {
        int X = 0;
        for(int &x: b)
            X ^= x;
        bool found = 0;
        for(int &x: b)
        {
            if(!found and X == x)
                found = true;
            else
                cout << (X ^ x) << " ";
        }
    }
    cout << endl;
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T; cin >> T;
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e5+5;
int n;
ll a[N];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;
	while(t--){
		cin >> n;
		ll king=0;
		for(int i=1; i<=n+1 ;i++){
			cin >> a[i];
			king^=a[i];
		}
		if(n%2==0) king=a[1];
		for(int i=1; i<=n+1 ;i++){
			if(a[i]==king) swap(a[1],a[i]);
		}
		for(int i=2; i<=n+1 ;i++) cout << (a[1]^a[i]) << ' ';
		cout  << '\n';
	}
}
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;
        int tot = 0;
        vector<int> a(n + 1);
        for (int i = 0; i < n + 1; i++) {
            cin >> a[i];
            tot ^= a[i];
        }
        bool rem = false;
        for (int i = 0; i < n + 1; i++) {
            if (!rem && (n % 2 == 0 || (n % 2 == 1 && a[i] == tot))) {
                rem = true;
                tot = a[i];
            } else {
                cout << (tot ^ a[i]) << " ";
            }
        }
        cout << '\n';
    }
}
11 Likes

If n is even , let’'s say n = 6
Lost Array is {1, 2, 3, 4, 5, 6}
So, total 7 subsequences possible

B[0] = 1 2 3 4 5
B[1] = 1 2 3 4 6
B[2] = 1 2 3 5 6
B[3] = 1 2 4 5 6
B[4] = 1 3 4 5 6
B[5] = 2 3 4 5 6
B[6] = 1 2 3 4 5 6

Now,
B[0]^B[1] = 5^6 = 3
B[0]^B[2] = 4^6 = 2
B[0]^B[3] = 3^6 = 5
B[0]^B[4] = 2^6 = 4
B[0]^B[5] = 1^6 = 7
B[0]^B[6] = 6

So, how are we recovering the lost array? Can someone help !

10 Likes

Brother, there can be more than one array possible and we have to return any one of them. Just that it should not violate any condition

6 Likes

Ohhok thanks ^^

yes

@kuroni Thanks for great editorial. I have just a small doubt that is there any proof for the case when n is even?

13 Likes

anyone please elaborate the editorial ?

**For n = 4 : **
Let’s assume the sequence as (a1,a2,a3,a4)
We are given B as let’s say : (some random order)
{a1^a2^a4}
{a1^a2^a3^a4}
{a2^a3^a4}
{a1^a3^a4}
{a1^a2^a3}

Since we do not know that 2nd value (a1,a2,a4,a4) is the xor of all the values unlike the case for n is odd, where we had figured it out we will blindly pick some value from array B, let’s say i pick the first value (a1,a2,a4) and xor it with all the other array values … we get an array like :

a3
a1 a3
a2 a3
a3 a4

Lets assume that this is out original array which was lost, now if we try to make an array B out of this we will get out array B back. Also this does not work for n = odd case, you may try it out.

3 Likes

Lovely explanation…:slight_smile:

You can prove by reconstructing elements in the array B and see that it coincides with the original array B. I don’t think there’s any better way to formally prove this, but intuitively you can think that since XOR of all elements in B are the same, any element in B has the same ability to become X (since xor of the remaining B's will be this element B).

when the contest start and i started with the third problem LOSTARRAY and after about 30min i have implemented the solution but when i click on submit button it shows error then i read the annoucement that the problem is replaced by another problem…
then i didn’t try coz i wasted almost 45 min now

can someone give a clear explanation i cant understand the editorial quite well

Can someone tell what’s wrong with my code?

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
	    int n,xr;cin>>n;
	    int b[n+1];cin>>b[0];xr=b[0];
	    for(int i=1;i<=n;i++)
	    {
	       cin>>b[i];xr^=b[i];
	    }
	    if(n&1){
	    for(int i=0;i<=n;i++)
	    {
	       if(b[i]!=xr)
	       {
	           cout<<(xr^b[i])<<" ";
	       }
	    }cout<<"\n";}
	    else
	    {
	        for(int i=1;i<=n;i++)
	       {
	           cout<<(b[0]^b[i])<<" ";
	       }cout<<"\n";
	    }
	    
	}
	return 0;
}

I am getting WA in many test cases while almost all test case of subtask 2 are accepted.

using
ll b[n+1],z=0;
for(int i=0;i<n+1;i++){
cin>>b[i];
z = z^b[i];
}
if(n%2==0){
z = b[0];
}
else{
for(int i=1;i<n+1;i++){
if(z == b[i]){
swap(b[0],b[i]);
}
}
}
for(int i=1;i<n+1;i++){
cout<<(b[i] ^ z)<<" ";
}
cout<<endl;

i am getting right submission but the thing is
when test case
4
1 2 3 4 5
it gives correct output
that is 2 3 4 5
but when the test case is 4 3 2 1 5
i gives wrong output
that is 7 6 5 1
while the xor of subsequence 1 ,6,7 is zero that is not in input array

please check if i am committing mistake anywhere

Could someone please explain what the 2nd for loop does ?

please inform me too if you get an answer

Can someone give a mathematical proof for the case when n is even?

The editorial for even n case seems wrong and misguiding.

when you are doing

if (b[i] != xr)

you are not considering other elements that maybe also equal to xr, and since you are not using any flag, your code will skip those values.
I wrote the same code by reading the editorial but after seeing some solutions, It clicked that using a flag or some counter will help.

We have added an Detailed Explanation section now.