F - Ideal Sheet Editorial by en_translator
First, the area in \(C\) to cut out can be fixed, as it is independent of whether \(X\) can be obtained.
So we first define a coordinate system in the sheet \(C\). Let \((0,0)\) be the top-left square in the \((H_X\times W_X)\)-region to be cut out, and denote by \((a,b)\) the square in the \(a\)-th row below and \(b\)-th column to the right. If \(a\) or \(b\) is negative, it respectively denotes the \(\lvert a\rvert\)-th row above and \(\lvert b\rvert\)-th row to the left. Here, we cut out the grid formed by squares \((i,j)\) such that \(0\leq i\leq a-1\) and \(0\leq j\leq b-1\). Let this region be \(D\).
Solution \(1\)
Consider which region to paste sheet \(A\). Sheet \(A\) contains a black square, and region \(D\) contains all black squares in \(A\), so the region to paste sheet \(A\) and region \(D\) must share at least one square. Thus, the possible squares (on sheet \(C\)) onto which the top-left square of sheet \(A\) is pasted are \((i,j)\) \((-H_A+1\leq i\leq H_X-1, -W_A+1\leq i\leq W_X-1\). Similarly, the possible squares (on sheet \(C\)) onto which the top-left square of sheet \(B\) is pasted are \((i,j)\) \((-H_B+1\leq i\leq H_X-1, -W_B+1\leq i\leq W_X-1)\).
When the positions of each sheet is determined, you can check if the two conditions in the problem statement are satisfied by checking all black squares in the \(H_A\times W_A\) and \(H_B\times W_B\) grids are pasted onto region \(D\), and the \(H_X\times W_X\) grid coincides with the sought sheet \(X\).
There are \(19\times 19\) candidates of the positions to paste sheets \(A\) and \(B\), and you need to inspect \(3\times(10\times 10)\) squares to check the conditions, so it requires a total of \((19\times 19)^2\times 300\) operations, which is fast enough to finish in the time limit. Thus, the problem has been solved.
The implementation may be simplified (depending on the approach) by the following idea:
- in many languages, the index of the array is desired to be non-negative, so let the top-left square of the cut-out region be \((10,10)\).
- in order to make the code independent of the dimensions of the grid, extend sheets \(A\), \(B\), and \(X\) to make them \(10\times 10\) by adding transparent squares if necessary.
Solution \(2\)
For each of sheets \(A\), \(B\), and \(X\), let us call a black square “good” if it belongs to the topmost row among the black squares, and if it belongs to the leftmost column among those in that row. Then, when the cut-out sheet satisfies the conditions, the good square of sheet \(A\) or sheet \(B\) is pasted onto the good black square of sheet \(X\). Since the location to paste in order to match good black squares is uniquely determined, it is sufficient to check the cases where it matches to that of sheet \(A\), and where it matches to that of sheet \(B\), while brute-forcing all candidates of positions to paste the other sheet. (In the sample code below, for implementation purpose we also define that bottom-right square is also good.)
In this solution, \(2\times (19\times 19)\times 300\) comparisons are performed, which is faster.
Sample code in C++ \(1\) (Solution \(1\)):
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
int main(void){
string a[3][10];
char tmp[10][11];
int h[3],w[3];
bool flag;
for(int k=0;k<3;k++){
cin>>h[k]>>w[k];
for(int i=0;i<h[k];i++)cin>>a[k][i];
}
for(int dh0=-h[0]+1;dh0<h[2];dh0++){
for(int dw0=-w[0]+1;dw0<w[2];dw0++){
for(int dh1=-h[1]+1;dh1<h[2];dh1++){
for(int dw1=-w[1]+1;dw1<w[2];dw1++){
for(int i=0;i<h[2];i++)for(int j=0;j<w[2];j++)tmp[i][j]='.';
flag=true;
for(int i=0;i<h[0];i++){
for(int j=0;j<w[0];j++){
if(a[0][i][j]=='#'){
if(i+dh0<0)flag=false;
if(i+dh0>=h[2])flag=false;
if(j+dw0<0)flag=false;
if(j+dw0>=w[2])flag=false;
if(flag)tmp[i+dh0][j+dw0]='#';
}
}
}
for(int i=0;i<h[1];i++){
for(int j=0;j<w[1];j++){
if(a[1][i][j]=='#'){
if(i+dh1<0)flag=false;
if(i+dh1>=h[2])flag=false;
if(j+dw1<0)flag=false;
if(j+dw1>=w[2])flag=false;
if(flag)tmp[i+dh1][j+dw1]='#';
}
}
}
for(int i=0;i<h[2];i++){
for(int j=0;j<w[2];j++){
if(a[2][i][j]!=tmp[i][j])flag=false;
}
}
if(flag){
cout<<"Yes"<<endl;
return 0;
}
}
}
}
}
cout<<"No"<<endl;
return 0;
}
Sample code in C++ \(2\) (Solution \(1\)):
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
int main(void){
string a[3][10];
char tmp[30][31];
int h[3],w[3];
bool flag;
for(int k=0;k<3;k++){
cin>>h[k]>>w[k];
for(int i=0;i<h[k];i++)cin>>a[k][i];
}
for(int dh0=1;dh0<20;dh0++){
for(int dw0=1;dw0<20;dw0++){
for(int dh1=1;dh1<20;dh1++){
for(int dw1=1;dw1<20;dw1++){
for(int i=0;i<30;i++)for(int j=0;j<30;j++)tmp[i][j]='.';
for(int i=0;i<h[0];i++)for(int j=0;j<w[0];j++)if(a[0][i][j]=='#')tmp[i+dh0][j+dw0]='#';
for(int i=0;i<h[1];i++)for(int j=0;j<w[1];j++)if(a[1][i][j]=='#')tmp[i+dh1][j+dw1]='#';
flag=true;
for(int i=0;i<30;i++){
for(int j=0;j<30;j++){
if((0<=(i-10))&&((i-10)<h[2])&&(0<=(j-10))&&((j-10)<w[2])){
if(tmp[i][j]!=a[2][i-10][j-10])flag=false;
}
else{
if(tmp[i][j]!='.')flag=false;
}
}
}
if(flag){
cout<<"Yes"<<endl;
return 0;
}
}
}
}
}
cout<<"No"<<endl;
return 0;
}
Sample code in C++ \(3\) (Solution \(2\)):
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
int main(void){
string a[3][10];
char tmp[30][31];
int h[3],w[3];
int dh0,dw0,dh1,dw1;
int gh[3],gw[3];
bool flag;
for(int k=0;k<3;k++){
cin>>h[k]>>w[k];
for(int i=0;i<h[k];i++){
cin>>a[k][i];
for(int j=0;j<w[k];j++)if(a[k][i][j]=='#')gh[k]=i,gw[k]=j;
}
}
dh0=gh[2]-gh[0]+10,dw0=gw[2]-gw[0]+10;
for(int dh1=1;dh1<20;dh1++){
for(int dw1=1;dw1<20;dw1++){
for(int i=0;i<30;i++)for(int j=0;j<30;j++)tmp[i][j]='.';
for(int i=0;i<h[0];i++)for(int j=0;j<w[0];j++)if(a[0][i][j]=='#')tmp[i+dh0][j+dw0]='#';
for(int i=0;i<h[1];i++)for(int j=0;j<w[1];j++)if(a[1][i][j]=='#')tmp[i+dh1][j+dw1]='#';
flag=true;
for(int i=0;i<30;i++){
for(int j=0;j<30;j++){
if((0<=(i-10))&&((i-10)<h[2])&&(0<=(j-10))&&((j-10)<w[2])){
if(tmp[i][j]!=a[2][i-10][j-10])flag=false;
}
else{
if(tmp[i][j]!='.')flag=false;
}
}
}
if(flag){
cout<<"Yes"<<endl;
return 0;
}
}
}
dh1=gh[2]-gh[1]+10,dw1=gw[2]-gw[1]+10;
for(int dh0=1;dh0<20;dh0++){
for(int dw0=1;dw0<20;dw0++){
for(int i=0;i<30;i++)for(int j=0;j<30;j++)tmp[i][j]='.';
for(int i=0;i<h[0];i++)for(int j=0;j<w[0];j++)if(a[0][i][j]=='#')tmp[i+dh0][j+dw0]='#';
for(int i=0;i<h[1];i++)for(int j=0;j<w[1];j++)if(a[1][i][j]=='#')tmp[i+dh1][j+dw1]='#';
flag=true;
for(int i=0;i<30;i++){
for(int j=0;j<30;j++){
if((0<=(i-10))&&((i-10)<h[2])&&(0<=(j-10))&&((j-10)<w[2])){
if(tmp[i][j]!=a[2][i-10][j-10])flag=false;
}
else{
if(tmp[i][j]!='.')flag=false;
}
}
}
if(flag){
cout<<"Yes"<<endl;
return 0;
}
}
}
cout<<"No"<<endl;
return 0;
}
posted:
last update: