MARM - Editorial

PROBLEM LINK:

Div 1
Div 2
Practice

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. :slight_smile:

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

What’s your solution link?

1 Like

https://pastebin.com/E9McYyQG

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 :smile:

1 Like

YES
it worked
Thanks a lot!

1 Like

Oh man!! Nice :wink:

Great Explanation !

You made the same mistake which I had made in the contest and later rectified it.

Test Case

1
3 1
1 2 3

Your Output

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. :slight_smile:

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 

(the answer should be

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