 CHEFGRD - Editorial

Setter: Akash Sharma
Testers: Lavish Gupta, Tejas Pandey
Editorialist: Ajit Sharma Kasturi

SIMPLE

None

PROBLEM:

Consider a N \times N grid where N is odd. We are currently at point (x, y). We need to find the minimum cost to reach the center of the grid by using some operations where in an operation we can move from (i, j) to (i+1, j+1), (i+1, j-1), (i-1, j+1) or (i-1, j-1) with cost 0 and we can move from (i,j) to (i,j+1) or (i, j-1) with cost 1.

EXPLANATION:

• Let C = \frac{N+1}{2} . The center of the grid is (C, C).

• Without losss of generality, let us assume i < C and j < C. ( The similar casework applies for remaining cases also. )

• I claim that the answer will be always 0 or 1.

• Let p = C-X and q = C-y. If p=q, we can apply the operation (i,j) \rightarrow (i+1,j+1) p times and reach the center with 0 cost.

• If p \lt q, and q-p is odd, we can apply the operation (i,j) \rightarrow (i+1,j+1) p times, then apply the pair of operations (i,j) \rightarrow (i+1,j+1)\rightarrow (i,j+2) \frac{q-p-1}{2} times. Now we will end up at (C, C-1) with 0 cost. With a cost of 1, we can move from (C, C-1) to (C, C).

• If p \lt q, and q-p is even, we can apply the operation (i,j) \rightarrow (i+1,j+1) p times, then apply the pair of operations (i,j) \rightarrow (i+1,j+1)\rightarrow (i,j+2) \frac{q-p}{2} times. Now we will end up at (C, C) with 0 cost.

• Similarly, we can check for all the cases. Therefore, the final answer is 0 if the parity of q-p is 0, else the answer is 1.

TIME COMPLEXITY:

O(1) for each test case.

SOLUTION:

Editorialist's solution
#include <bits/stdc++.h>
using namespace std;

int main()
{
int tests;
cin >> tests;
while (tests--)
{
int n, x, y;
cin >> n >> x >> y;
int need_x = (n + 1) / 2 - x, need_y = (n + 1) / 2 - y;
int diff = abs(abs(need_x) - abs(need_y));
if (diff % 2 == 0)
cout << 0 << endl;
else
cout << 1 << endl;
}
return 0;
}

Setter's solution
#include <bits/stdc++.h>
using namespace std;

int main()
{
int T;
cin >> T;
while (T-- > 0)
{
int n, x, y;
cin >> n >> x >> y;
if(x%2==y%2)cout<<0;
else cout<<1;
cout << '\n';
}
return 0;
}
Tester's solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 10000;
const int MAX_N = 20000;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int sum_len=0;

void solve()
{
assert(n&1);
cout << ((x&1) != (y&1)) << "\n";
}

signed main()
{
//fast;
#ifndef ONLINE_JUDGE
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif

for(int i=1;i<=t;i++)
{
solve();
}

assert(getchar() == -1);
}

Please comment below if you have any questions, alternate solutions, or suggestions. Done almost same as setters solution just did a lot more if’s then needed, need to improve more .

BTW nice question, thanks.

my solution

can any one tell me at which condition my code failed

question kon se concept ka hai

1
13 2 6
Expected output is 0.

1 Like

Based on the second grid I have noticed that if the sum is odd then the answer is 1 otherwise 0