MARM - Editorial

Author: Mayank Agrawal
Tester: Hanlin Ren
Editorialist: Hanlin Ren

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:

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

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

5 Likes

I did the same thing…
Can anybody point out where i am wrong?
My solution:-
https://www.codechef.com/viewsolution/27350673

Just take the brute force solution and add this line…and get AC😛

if(k>3*n){
k=k%(3*n) + 3*n;
}


9 Likes

This was really very clever. Thank you, got something new

1 Like

Used the same approach.
After every three iteration array comes back to its original form.
Just need to check if k>n then set the element a[n/2]=0.

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

1 Like

Why is this is giving wrong answer for me ?

1 Like

1 Like

can anybody help me with my solution…I am getting wrong answer with my solution
https://www.codechef.com/viewsolution/27380639

The logic exactly same for another solution which is giving AC
https://www.codechef.com/viewsolution/27358186

It’s just an issue with operator’s precedence

Change This

if(k>3*n){
k=k%3*n + 3*n;
}


To This, By adding brackets around 3n

if(k>3*n){
k=k%(3*n) + 3*n;
}


It’ll Work Now

1 Like

YES
it worked
Thanks a lot!

1 Like

Oh man!! Nice

Great Explanation !

Test Case

1
3 1
1 2 3

2 0 3

Expected Output

2 2 3

Hint to AC

Just add a condition for the middle element, if k is greater than the index of the middle element[1 indexed].

Hope this helps.

I am checking condition that in case when (k>(3n)), so if n is odd then make mid element 0 and if even then just do nothing and after checking this condition , i perform iteration from 0 to (k modulo (3n)) over list and then prints it but it gives me wrong answer .
But if I use your suggestion, it works fine.
Pls tell me the reason why this happens ?

Where am i committing mistake?

Please anyone explain why this approach is wrong?

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

Here’s a random testcase it fails on:

1
27 93
642 424 865 356 33 504 691 881 460 121 154 661 598 520 110 274 430 197 666 547 881 118 504 365 288 231 209


595 335 577 9 473 398 450 338 854 188 308 903 598 0 110 274 430 197 666 547 881 118 504 365 288 231 209


)

1 Like

i am using dp but my solution is giving wrong answer
here it is…
#include <bits/stdc++.h>
using namespace std;
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)(b))/gcd((a),(b))
typedef long long int lli;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
lli tc;
cin>>tc;
while(tc–)
{
lli i,j,n,k,c;
cin>>n>>k;
lli arr[n],dp[3][n];
for(i=0;i<n;i++)
cin>>arr[i];
if(n%2==0)
{
for(i=0;i<3;i++)
{
for(j=0;j<n;j++)
{
if(i==0)
{
if(j<n/2)
{
dp[i][j]=arr[j] ^ arr[n-1-j];
}
else
{
dp[i][j]=arr[j] ^ dp[0][n-1-j];
}
}
else
{
if(j<n/2)
{
dp[i][j]=dp[i-1][j] ^ dp[i-1][n-1-j];
}
else
{
dp[i][j]=dp[i-1][j] ^ dp[i][n-1-j];
}
}
}
}
}
else
{
for(i=0;i<3;i++)
{
for(j=0;j<n;j++)
{
if(i==0)
{
if(j<=n/2)
{
dp[i][j]=arr[j] ^ arr[n-1-j];
}
else
{
dp[i][j]=arr[j] ^ dp[0][n-1-j];
}
}
else
{
if(j<=n/2)
{
dp[i][j]=dp[i-1][j] ^ dp[i-1][n-1-j];
}
else
{
dp[i][j]=dp[i-1][j] ^ dp[i][n-1-j];
}
}
}
}
}
/

for(i=0;i<3;i++)
{
for(j=0;j<n;j++)
{
cout<<dp[i][j]<<" “;
}
cout<<’\n’;
}*/
lli l,r;
l=k%n;
r=(k-1)%3;
if(r==0)
{
for(i=0;i<n;i++)
{
if(i<l)
{
cout<<dp[2][i]<<” “;
}
else
{
cout<<dp[1][i]<<” “;
}
}
}
else if(r==1)
{
for(i=0;i<n;i++)
{
if(i<l)
cout<<dp[2][i]<<” “;
else
cout<<dp[1][i]<<” “;
}
}
else
{
for(i=0;i<n;i++)
{
if(i<l)
{
cout<<dp[r][i]<<” “;
}
else
{
cout<<dp[r-1][i]<<” ";
}
}
}
for(i=0;i<n;i++)
{

  }

cout<<'\n';


}
return 0;
}

pls anyone can explain me how to solve this problem using dynamic programming