PROBLEM LINK:
Setter: Akash Sharma
Testers: Lavish Gupta, Tejas Pandey
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
SIMPLE
PREREQUISITES:
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 readString(int l,int r,char endd){
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){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,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()
{
int n = readIntSp(3, MAX_N);
assert(n&1);
int x = readIntSp(1, n);
int y = readIntLn(1, n);
cout << ((x&1) != (y&1)) << "\n";
}
signed main()
{
//fast;
#ifndef ONLINE_JUDGE
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
int t = readIntLn(1, MAX_T);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
}
Please comment below if you have any questions, alternate solutions, or suggestions. 