PROBLEM LINK:
Author: Mayank Agrawal
Tester: Hanlin Ren
Editorialist: Hanlin Ren
DIFFICULTY:
SIMPLE
PREREQUISITES:
Array manipulation
PROBLEM:
You are given an array A[0\sim (N-1)], and you need to perform the following operations for i from 0 to K-1:
A[i\bmod N]\gets A[i\bmod N]\text{ xor } A[N-(i\bmod N)-1].
QUICK EXPLANATION:
- Solution 1: for every pair of indices (i,N-i-1), we compute the number of operations done on this pair, and use the corresponding formula.
- Solution 2: We simply let K\gets K\bmod 3N and do what we’re told to do. When N is odd, we need to deal with A[\frac{N-1}{2}] as a special case, though.
EXPLANATION:
Subtask 1
Since K is small in this subtask, the problem is easy: we simply implement what the problem asks us to do.
Time complexity: O(K+N).
Subtask 2
For every 0\le p<N, we pair the indices p and N-p-1 together. (Note that if p=N-q-1, then p is also paired with N-p-1=q.) It’s easy to see that each A[p] only interacts with A[N-p-1].
Assume p<N-p-1, and for convenience let’s denote q=N-p-1. Let’s denote the original array as A, and the modified array as A'. Let’s simulate the process in the problem statement, let i\gets 0 to K-1, and see when A'[p] and A'[q] would make changes:
- After the operation that i=p, A'[p]=A[p]\oplus A[q], and A'[q]=A[q].
- After the operation that i=q, A'[p]=A[p]\oplus A[q], and A'[q]=A[q]\oplus (A[p]\oplus A[q])=A[p].
- After the operation that i=N+p, A'[p]=(A[p]\oplus A[q])\oplus A[p]=A[q], and A'[q]=A[p].
- …
Or let’s make a table so we can see it more clearly:
After i = | A'[p] | A'[q]
p | A[p] xor A[q] | A[q]
q | A[p] xor A[q] | A[p]
N + p | A[q] | A[p]
N + q | A[q] | A[p] xor A[q]
2N + p | A[p] | A[p] xor A[q]
2N + q | A[p] | A[q]
3N + p | A[p] xor A[q] | A[q]
3N + q | A[p] xor A[q] | A[p]
4N + p | A[q] | A[p]
4N + q | A[q] | A[p] xor A[q]
5N + p | A[p] | A[p] xor A[q]
5N + q | A[p] | A[q]
... | ... | ...
Let b[i] be the number of operations done on A'[i]. If i<K\bmod n, then b[i]=\lfloor n/k\rfloor+1; Otherwise b[i]=\lfloor n/k\rfloor. We can see that
- the first operation on A'[p] changes it to A[p]\oplus A[q];
- the second operation on A'[p] changes it to A[q];
- the third operation changes it back to A[p].
The above argument only works for p<N/2. For q>N/2, we can still find the pattern:
- the first operation on A'[q] changes it to A[p];
- the second operation changes it to A[p]\oplus A[q];
- the third operation changes it back to A[q].
Therefore, we can compute the values of each A'[p],A'[q] according to b[p]\bmod 3 and b[q]\bmod 3 respectively. For more details, please refer to Setter’s solution.
A special case
When N is odd and p=(N-1)/2, we have p=N-p-1=q. In this case, the first operation on A[p] becomes A[p]\gets A[p]\oplus A[p], therefore it sets A[p] to 0. Further operations on A[p] can only leave it as 0 forever.
Thus there is a special case: if p=(N-1)/2, then let’s examine b[p], i.e. the number of operations done on A[p]. If b[p]=0, then A'[p]=A[p]; otherwise A'[p]=0.
ALTERNATE EXPLANATION:
In fact, there is a simpler-looking solution: we simply let K\gets K\bmod 3N and do what we’re asked to do. The reason is also simple from the above table: 3N operations restore the same array as before, except for the special case where A[(N-1)/2] is set to zero. The pseudocode is very clear:
if (N is odd and K >= (N - 1) / 2) then
A[(N - 1) / 2] = 0
K = K % (3 * N)
for i = 0 to K - 1
A[i mod N] = A[i mod N] xor A[N - (i mod N) - 1]
In the tester’s alternate solution, I set
K\gets\begin{cases}K&K<3N\\3N+(K\bmod 3N)&K>3N\end{cases},
and didn’t handle the special case at all. If you are interested, you can think about why this works. 
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define ll long long int
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int main()
{
int i,j,x,y,t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
ll p = k/n;
k%= n;
ll a[n] , b[n];
for(i=0;i<n;++i){
cin>>a[i];
b[i]= p;
if(i<k)
++b[i];
}
for(i=0;i<n/2;++i){
if(b[i]%3LL==0LL){
b[i] = a[i];
}else if(b[i]%3LL==1LL){
b[i] = a[i]^a[n-i-1];
}else{
b[i] = a[n-i-1];
}
if(b[n-i-1]%3LL==0LL){
b[n-i-1] = a[n-i-1];
}else if(b[n-i-1]%3LL==1){
b[n-i-1] = a[i];
}else{
b[n-i-1] = a[i]^a[n-i-1];
}
}
if(n%2){
if(b[n/2]==0){
b[n/2]= a[n/2];
}else{
b[n/2]= 0;
}
}
for(i=0;i<n;++i){
cout<<b[i]<<" ";
}cout<<"\n";
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template <class Q>
void gi(Q &x) {char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();}
template <class Q>
void pi(Q x) {if (x > 9) pi(x / 10); putchar(x % 10 + 48);}
int n;
long long k;
int a[100200];
void doit() {
gi(n); gi(k);
for (int i = 0; i < n; i++) gi(a[i]);
for (int i = 0; i < n; i++) {
int ans = 0, num_of_op = k / n + ((k % n) > i), j = n - i - 1;
if (i < j) {
switch (num_of_op % 3) {
case 0: ans = a[i]; break;
case 1: ans = a[i] ^ a[j]; break;
case 2: ans = a[j]; break;
}
} else if (i > j) {
switch (num_of_op % 3) {
case 0: ans = a[i]; break;
case 1: ans = a[j]; break;
case 2: ans = a[i] ^ a[j]; break;
}
} else {
if (k > i) ans = 0;
else ans = a[i];
}
pi(ans); putchar(' ');
}
putchar('\n');
}
int main() {int t; gi(t); while (t--) doit(); return 0;}
Tester's alternate Solution
#include <bits/stdc++.h>
using namespace std;
template <class Q>
void gi(Q &x) {char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();}
template <class Q>
void pi(Q x) {if (x > 9) pi(x / 10); putchar(x % 10 + 48);}
int n;
long long k;
int a[100200];
void doit() {
int i;
gi(n); gi(k);
if (k >= n * 3) k = n * 3 + (k % (n * 3));
for (i = 0; i < n; i++) gi(a[i]);
for (i = 0; i < k; i++) {
a[i % n] = a[i % n] ^ a[n - (i % n) - 1];
}
for (i = 0; i < n; i++) pi(a[i]), putchar(' ');
putchar('\n');
}
int main() {int t; gi(t); while (t--) doit(); return 0;}
