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';
}
}
