# CRZBISHOP - Editorial

Authors: d_k_7386
Tester: tabr
Editorialist: iceknight1093

1351

Observation

# PROBLEM:

There’s an N\times N chessboard with N bishops on it.
Initially, the bishops are at positions (1, 1), (2, 2), (1, 3), (2, 4), (1, 5), \ldots

You want their final positions to be (1, 1), (2, 2), (3, 3), (4, 4), \ldots
What’s the minimum number of moves needed to achieve this?

# EXPLANATION:

If N \leq 2, the answer is 0 because the first 2 bishops are already in positions.

For N \gt 2, working out a few small cases on paper might give you the following strategy:

• For each bishop that’s initially on (2, x), use one move to bring it to the required diagonal.
• Then, for each bishop that’s initially on (1, x), use two moves to bring it to the required diagonal.

This strategy would take a + 2\cdot b moves, where a = \left\lfloor \frac{N}{2} \right\rfloor - 1 is the number of bishops initially on the second row (that need to be moved), and b = \left\lceil \frac{N}{2} \right\rceil - 1 is the number of bishops initially on the first row (that need to be moved).

In fact, this is optimal!

Proof

For N \leq 2,, the fact that 0 moves are required is obvious.

For N \gt 2, note that each bishop has a unique cell on the main diagonal that they can reach in one move.
In particular, the bishops on (2, 2k) and (1, 2k+1) share the same main diagonal cell for any k \geq 1.

So, each of these bishops need at least one move, and at least one of them needs another; because if they both used one move they’d end up in the same cell, which is not allowed.

This gives us a lower bound on the number of moves needed, and it’s easy to see that our strategy attains this lower bound and is hence optimal.

It’s not hard (but also not necessary) to further simplify this into a formula based on N:

• If N = 1, the answer is 0.

• If N is odd, the answer is \displaystyle\frac{3N-5}{2}

• If N is even, the answer is \displaystyle\frac{3N-6}{2}

# TIME COMPLEXITY

\mathcal{O}(1) per test case.

# CODE:

Setter's code (C++)
/* DK....DAIICT */

#include <bits/stdc++.h>
using namespace std;

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

long long pow_s(long long a, long long b)
{
long long res = 1;
while (b > 0)
{
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}

long long pow_m(long long a, long long b, long long m)
{
a %= m;
long long res = 1;
while (b > 0)
{
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
// string s = bitset<8>(n).to_string();    int to binary string
long long gcd(long long a, long long b)
{
while (b)
{
a %= b;
swap(a, b);
}
return a;
}
long long lcm(long long a, long long b)
{
return a / gcd(a, b) * b;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;

const ll MOD = 1e9 + 7;

void solve()
{
ll n;
cin >> n;
if (n == 1)
{
cout << "0" << endl;
return;
}
if (n & 1)
cout << (3 * n - 5) / 2 << endl;
else
cout << (3 * n - 6) / 2 << endl;
}

int32_t main()
{
FAST;
ll t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}

assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
res += buffer[pos];
pos++;
}
return res;
}

string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

int main() {
input_checker in;
while (tt--) {
long long n = in.readInt(1, 1e9);
long long ans = 0;
while (n > 2) {
if (n == 3) {
ans += 2;
n--;
} else if (n == 4) {
ans += 1;
n--;
} else {
long long k = (n - 2) / 2;
ans += 3 * k;
n -= 2 * k;
}
}
cout << ans << '\n';
}
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
top, bottom = n//2, (n+1)//2
print(max(0, top-1 + 2*(bottom-1)))


Why this code is giving me the wrong answer, when the final formula is same as of the editorial?

#include <iostream>
using namespace std;

#define ll long long int

void solve(){
ll n;
cin>>n;
if(n == 1 || n == 2) {cout<<0<<"\n"; return;}
n = n-2;
if(n%2 == 1){
ll ans = 2 + ((n+1)/2-1)*3;
cout<<ans<<"\n";
}
ll ans = 3 + (n/2-1)*3;
cout<<ans<<"\n";
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);

int t;
cin>>t;
while(t--){
solve();
}
return 0;
}



for odd case:
Put n = n-2; in the equation:
ans = 2 + ((n-2+1)/2 -1)*3
ans = 2 + ((n-1)/2 -1)*3
ans = 2 + (3n-3)/2 -3
ans = (3n-3)/2 -1
ans = (3n-5)/2

Similarly for the even case:
ans = 3 + ((n-2)/2 - 1)*3
ans = 3 + (3n-6)/2 -3
ans = (3n-6)/2

Any help will be appreciated!

return statement is missing in this if block

if(n%2 == 1){
ll ans = 2 + ((n+1)/2-1)*3;
cout<<ans<<"\n";
}


Thanks! I literally struggled for more than 20 minutes, assuming my logic is incorrect.

Can’t this problem be solved using concept of shifting bits?

For example: when n=6
Then
n-2=6-2=4
Now find the MSB
mSB(4) =3

Temp = 1<<3;

While(temp>=n-2)
temp>>1

ans=1+(n-2) + temp;

Tc: n=6 MSB : 3 so adding temp=1
Tc: n=8 MSB: 4 so adding temp=2
Tc n=9 MSB : so add temp=3
1+(9-2) +3= 11 same as formula