MARM - Editorial

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

1 Like
1 Like

https://www.codechef.com/viewsolution/27333018
here is my solution in which i am getting wrong answer

For the testcase:

``````1
4 49
858 723 332 138
``````

your program is giving (Edit: actually, I’m getting a different result every time, so there’s some Undefined Behaviour/ uninitialised data in there):

``````140725646481792 4 2 94828364422956
``````

when it should be:

``````976 723 332 138
``````

so how can i correct my solution by keeping the same approcah of dp

I don’t know Why do you want to use DP instead of the method described in the Editorial?

just trying an another way

1 Like

Could u check why my my output is giving wrong ans:
i just observed the patters that after three operations the array retains the same confiquration.
import java.util.;
import java.io.
;
import java.lang.*;

class cd207
{
public static void main(String args[])throws IOException
{
try
{
//takign input through IO
OutputWriter out = new OutputWriter(System.out);
long k;
while(t–>0)
{
rem = (int)k%n;
rep = (int)k/n;
if(rep!=0)
{
op(arr,rem,rep%3);
}
else
{
for(int i=0;i<k;i++)
arr[i] = arr[i]^arr[arr.length-i-1];
}
for(int i=0;i<arr.length;i++)
{
out.print(arr[i]+" ");
out.flush();
}
out.printLine();
out.flush();
}
out.close();
}
catch(Exception e){
e.printStackTrace();
}

}

``````static void op(int arr[],int rem,int cat)
{
int n = (arr.length-1)/2;
switch(cat)
{
case 0 :

for(int i=0;i<=n;i++)
arr[i] = arr[i]^arr[arr.length-i-1];
for(int i=n+1;i<arr.length;i++)
arr[i] = 0;
break;

case 1 :

for(int i=0;i<arr.length;i++)
arr[i] = arr[i]^arr[arr.length-i-1];
break;

case 2:
for(int i=0;i<=n;i++)
arr[i] = 0;
for(int i=n+1;i<arr.length;i++)
arr[i] = arr[i]^arr[arr.length-i-1];
break;
default:

}

for(int i=0;i<rem;i++)
arr[i] = arr[i]^arr[arr.length-i-1];
}
``````

}

https://www.codechef.com/viewsolution/27154577
check it here

1 Like

It also fails the testcase here:

Can someone please tell me where my code gone wrong.

It fails on the following testcase:

``````1
91 27
458 406 299 653 253 660 551 56 174 880 194 660 141 945 790 667 949 365 798 146 818 473 545 90 271 572 615 907 565 505 233 22 262 884 26 514 543 576 570 716 807 115 727 948 411 869 966 711 233 115 857 402 588 401 491 210 972 105 116 536 961 701 910 574 584 935 440 478 863 9 193 669 475 272 968 237 140 933 947 372 48 803 126 987 204 616 196 527 73 663 415
``````

``````85 769 354 130 57 252 747 995 208 83 242 992 830 20 922 630 125 125 709 527 1011 464 382 388 183 411 47 907 565 505 233 22 262 884 26 514 543 576 570 716 807 115 727 948 411 869 966 711 233 115 857 402 588 401 491 210 972 105 116 536 961 701 910 574 584 935 440 478 863 9 193 669 475 272 968 237 140 933 947 372 48 803 126 987 204 616 196 527 73 663 415