ADASHOP2 - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

Author: Alei Reyes
Tester: Suchan Park
Editorialist: William Lin

DIFFICULTY:

Simple

PREREQUISITES:

Constructive algorithms

PROBLEM:

A bishop starts on a black cell on a chessboard. Find a sequence of at most 64 moves so that the bishop can visit all black cells on the board.

QUICK EXPLANATION:

We can visit all cells in a single diagonal of the board by moving to the topmost and bottommost cell of the diagonal. After we visit all diagonals, we will have visited all cells on the board.

EXPLANATION:

Let’s solve the first subtask first. The bishop starts at (1, 1). Our plan is to cover the diagonals one by one:

To visit the next diagonal, we first move down and right by one cell. Then, we move to the topmost cell of the diagonal and the bottommost cell of the diagonal in order to visit all cells of the diagonal. Before moving on to the next diagonal, we move back to the middle of the diagonal.

Implementation

There are two parts to this. The first part deals with these diagonals:

for(int i=4; i<=8; i+=2) {
	//visit all cells in x+y=i
}

First, we move to the middle of the new diagonal. If x+y=i, then x=y=\frac{i}{2}. Second, we move to the topmost cell of the diagonal, which is the cell in row 1. We can find the column to be (x+y)-x=i-1. Third, we move to the bottommost cell of the diagonal, which is the cell in column 1, and similarly, it is at (i-1, 1). Lastly, we move back to the middle of the diagonal, which is still (\frac{i}{2}, \frac{i}{2}).

for(int i=4; i<=8; i+=2) {
	//visit all cells in x+y=i
	//move to (i/2, i/2)
	//move to (1, i-1)
	//move to (i-1, 1)
	//move to (i/2, i/2)
}

The second part is the last 4 diagonals:

The only change is that the topmost cell is the cell at column 8 and the bottommost cell is the cell at row 8.

for(int i=10; i<=16; i+=2) {
	//visit all cells in x+y=i
	//move to (i/2, i/2)
	//move to (i-8, 8)
	//move to (8, i-8)
	//move to (i/2, i/2)
}

For subtask 2, the bishop can start on any cell, but we can easy use our solution for subtask 1 to solve this. We will somehow move our bishop to (1, 1), then perform the same solution for subtask 1.

To move to (1, 1), we will first move to the diagonal (i, i), and then move to (1, 1), as shown here:

Implementation

The diagonal is represented by the line y=x, whereas the line of cells that the bishop can move to is y=-(x-r)+c. Solving the equations, we find that x=y=\frac{r+c}{2}. So our first two moves will be (\frac{r+c}{2}, \frac{r+c}{2}) and (1, 1).

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int rint(char nxt){
  char ch=getchar();
  int v=0;
  int sgn=1;
  if(ch=='-')sgn=-1;  
  else{
    assert('0'<=ch&&ch<='9');
    v=ch-'0';
  }
  while(true){
    ch=getchar();
    if('0'<=ch && ch<='9')v=v*10+ch-'0';
    else{
      assert(ch==nxt);
      break;
    }
  }
  return v*sgn;
}
int main(){
//  freopen("1.in","r",stdin);
//  freopen("1.out","w",stdout);
  int t=rint('\n');
  assert(1<=t&&t<=32);
  while(t--){
    int r=rint(' ');
    int c=rint('\n');
    assert(1<=r&&r<=8);
    assert(1<=c&&c<=8);
    assert((r+c)%2==0);
    vector<pair<int,int> >ans={{r,c}};
    int mid=(r+c)/2;
    ans.push_back({mid,mid});
    ans.push_back({1,1});
    for(r=2;r<=4;r++){
      ans.push_back({r,r});
      ans.push_back({1,r+r-1});
      ans.push_back({r+r-1,1});
      ans.push_back({r,r});
    }
    for(r=5;r<=8;r++){
      int x=2*(r-4);
      ans.push_back({r,r});
      ans.push_back({x,8});
      ans.push_back({8,x});
      ans.push_back({r,r});
    }
 
    printf("%d\n",int(ans.size()));
    for(auto p:ans){
      printf("%d %d\n",p.first,p.second);
    }
  }
  assert(getchar()==EOF);
  return 0;
}
Tester's Solution
//
// Created by ��찬 on 2020/02/22.
//
 
#include <bits/stdc++.h>
 
namespace {
 
    const int BUFFER_SIZE = int(1.1e5);
 
    char _buf[BUFFER_SIZE + 10];
    int _buf_pos, _buf_len;
 
    char seekChar() {
        if(_buf_pos >= _buf_len) {
            _buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
            _buf_pos = 0;
        }
        assert(_buf_pos < _buf_len);
        return _buf[_buf_pos];
    }
 
    bool seekEof() {
        if(_buf_pos >= _buf_len) {
            _buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
            _buf_pos = 0;
        }
        return _buf_pos >= _buf_len;
    }
 
    char readChar() {
        char ret = seekChar();
        _buf_pos++;
        return ret;
    }
 
    int readInt(int lb, int rb) {
        char c = readChar();
        int mul = 1;
        if(c == '-') {
            c = readChar();
            mul = -1;
        }
        assert(isdigit(c));
 
        long long ret = c - '0';
        char first_digit = c;
        int len = 0;
        while(!seekEof() && isdigit(seekChar()) && ++len <= 19) {
            ret = ret * 10 + readChar() - '0';
        }
        ret *= mul;
 
        if(len >= 2) assert(first_digit != '0');
        assert(len <= 18);
        assert(lb <= ret && ret <= rb);
        return (int)ret;
    }
 
    void readEoln() {
        char c = readChar();
        assert(c == '\n');
    }
 
    void readSpace() {
        assert(readChar() == ' ');
    }
 
}
 
bool gph[64][64];
 
std::vector<int> path;
bool vis[64];
 
bool brute(int u, int c) {
    if(c == 32) {
        printf("%ld\n", path.size());
        for(int it : path) {
            printf("%d %d\n", it / 8 + 1, it % 8 + 1);
        }
        return true;
    }
    for(int v = 0; v < 64; v++) if(!vis[v] && gph[u][v]) {
        path.push_back(v); vis[v] = true;
        if(brute(v, c+1)) return true;
        path.pop_back(); vis[v] = false;
    }
    return false;
}
 
void run() {
    int r = readInt(1, 8);
    readSpace();
    int c = readInt(1, 8);
    readEoln();
 
    r -= 1;
    c -= 1;
    assert((r + c) % 2 == 0);
 
    memset(vis, 0, sizeof vis);
 
    int u = r * 8 + c;
    path.clear();
    vis[u] = true;
    assert(brute(u, 1));
}
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
 
    int T = readInt(1, 32);
    readEoln();
 
    for(int r1 = 0; r1 < 8; r1++) {
        for(int c1 = 0; c1 < 8; c1++) {
            int u = r1 * 8 + c1;
            for(int r2 = 0; r2 < 8; r2++) {
                for(int c2 = 0; c2 < 8; c2++) {
                    int v = r2 * 8 + c2;
                    if(r1 + c1 == r2 + c2 || r1 - c1 == r2 - c2) {
                        gph[u][v] = true;
                    }
                }
            }
        }
    }
 
    while(T--) {
        run();
    }
    return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

void solve() {
	//input
	int r, c;
	cin >> r >> c;

	vector<array<int, 2>> moves;
	//move to y=x diagonal
	moves.push_back({(r+c)/2, (r+c)/2});
	//move to (1, 1)
	moves.push_back({1, 1});
	//first 3 diagonals
	for(int i=4; i<=8; i+=2) {
		//visit all cells in x+y=i
		moves.push_back({i/2, i/2});
		moves.push_back({1, i-1});
		moves.push_back({i-1, 1});
		moves.push_back({i/2, i/2});
	}
	//last 4 diagonals
	for(int i=10; i<=16; i+=2) {
		//visit all cells in x+y=i
		moves.push_back({i/2, i/2});
		moves.push_back({i-8, 8});
		moves.push_back({8, i-8});
		moves.push_back({i/2, i/2});
	}

	//output
	cout << moves.size() << "\n";
	for(array<int, 2> a : moves)
		cout << a[0] << " " << a[1] << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while(t--)
		solve();
}

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

6 Likes

suppose the bishop is firstly at (1,1) itself . That case is not handled in editors solution , no?

Read the problem statement, do some work on your own, and then read the editorial, you will see that there is nothing wrong with the editorial.

Continuing the discussion from ADASHOP2 - Editorial:

Why I am getting wrong answer it seems correct.

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

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

const ll mod = 1e9+7;
const db eps = 1e-9;

#define mp make_pair
#define pb push_back
#define endl “\n”
#define deb(x) cout << #x << " " << x << endl

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

#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
freopen("error.txt","w",stderr);
#endif

ll t;
cin >> t;

while(t--)
{
	ll r,c;
	cin>>r>>c;
	if(r==c && r==1)
	{
	    cout<<19<<endl;
	    cout<<2<<' '<<2<<endl;
	    cout<<1<<' '<<3<<endl;
	    cout<<3<<' '<<1<<endl;
	    cout<<4<<' '<<2<<endl;
	    cout<<1<<' '<<5<<endl;
	    cout<<5<<' '<<1<<endl;
	    cout<<6<<' '<<2<<endl;
	    cout<<1<<' '<<7<<endl;
	    cout<<7<<' '<<1<<endl;
	    cout<<8<<' '<<2<<endl;
	    cout<<2<<' '<<8<<endl;
	    cout<<3<<' '<<7<<endl;
	    cout<<4<<' '<<8<<endl;
	    cout<<8<<' '<<4<<endl;
	    cout<<7<<' '<<5<<endl;
	    cout<<8<<' '<<6<<endl;
	    cout<<6<<' '<<8<<endl;
	    cout<<8<<' '<<7<<endl;
	    cout<<8<<' '<<8;
	    
	}
	else if(r==c && r!=1)
	{
        cout<<20<<endl;
        cout<<1<<' '<<1<<endl;
	    cout<<2<<' '<<2<<endl;
	    cout<<1<<' '<<3<<endl;
	    cout<<3<<' '<<1<<endl;
	    cout<<4<<' '<<2<<endl;
	    cout<<1<<' '<<5<<endl;
	    cout<<5<<' '<<1<<endl;
	    cout<<6<<' '<<2<<endl;
	    cout<<1<<' '<<7<<endl;
	    cout<<7<<' '<<1<<endl;
	    cout<<8<<' '<<2<<endl;
	    cout<<2<<' '<<8<<endl;
	    cout<<3<<' '<<7<<endl;
	    cout<<4<<' '<<8<<endl;
	    cout<<8<<' '<<4<<endl;
	    cout<<7<<' '<<5<<endl;
	    cout<<8<<' '<<6<<endl;
	    cout<<6<<' '<<8<<endl;
	    cout<<8<<' '<<7<<endl;
	    cout<<8<<' '<<8;
    }
    else
    {
        cout<<21<<endl;
        cout<<(r+c)/2<<' '<<(r+c)/2<<endl;
        cout<<1<<' '<<1<<endl;
	    cout<<2<<' '<<2<<endl;
	    cout<<1<<' '<<3<<endl;
	    cout<<3<<' '<<1<<endl;
	    cout<<4<<' '<<2<<endl;
	    cout<<1<<' '<<5<<endl;
	    cout<<5<<' '<<1<<endl;
	    cout<<6<<' '<<2<<endl;
	    cout<<1<<' '<<7<<endl;
	    cout<<7<<' '<<1<<endl;
	    cout<<8<<' '<<2<<endl;
	    cout<<2<<' '<<8<<endl;
	    cout<<3<<' '<<7<<endl;
	    cout<<4<<' '<<8<<endl;
	    cout<<8<<' '<<4<<endl;
	    cout<<7<<' '<<5<<endl;
	    cout<<8<<' '<<6<<endl;
	    cout<<6<<' '<<8<<endl;
	    cout<<8<<' '<<7<<endl;
	    cout<<8<<' '<<8;
    }
}

return 0;
}

For c=1 and r=2 You would print 1 1 twice

I think that doesn’t care. We can print print a number as many times but the total should be less than 64. And when you put values of i in the editorialist’s solution than u also get consecutive same numbers