USACO Bronze 2016 Open - Bull in a China Shop

Official Analysis (Java)

We can loop through all possible pairs of pieces and shift them to check if they can make the original figurine. Since we cannot shift a piece so any '#' fall outside the $N \times N$ grid, we need to find the sides of the pieces to determine how far to shift them.

As we iterate the pieces, we find the left, right, top and bottom sides of the piece and store them in the $s$ array. When we are shifting, we shift $\texttt{piece[i]}$ $\texttt{idy}$ units to the left and $\texttt{idx}$ units up, and shift $\texttt{piece[j]}$ $\texttt{jdy}$ units to the left and $\texttt{jdx}$ units up. This will send the piece at $(x + \texttt{idx}, y + \texttt{idy})$ to $(x, y)$ and the piece at $(x + \texttt{jdx}, y + \texttt{jdy})$ to $(x, y)$. So, we see that $\texttt{idy}$ must be bounded by $\texttt{right} - n + 1$ and $\texttt{left}$, and $\texttt{idx}$ must be bounded by $\texttt{bottom} - n + 1$ and $\texttt{top}$, with $\texttt{jdy}$ and $\texttt{jdx}$ bounded similarly. Because of that, every '#' will fall inside the $N \times N$ grid.

Once we have shifted the pieces, if there are two '#' in the same place, or if the result of superimposing the pieces is not the same as the original figurine ($\texttt{pieces[0]}$), then this shift will not work.

Implementation

Time Complexity: $\mathcal{O}(K^2 \cdot N^6)$

Copy
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
bool check(int piece, int x, int y);

int n;
bool pieces[11][8][8];
vector<int> s[11];
int main() {

Copy
import java.io.*;
import java.util.*;

public class BCS {
	public static boolean pieces[][][];
	public static int n;
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("bcs");

		pieces = new boolean[11][8][8];

Copy
from sys import exit

with open("bcs.in") as read:
	n, k = [int(i) for i in read.readline().split()]
	# First piece in this array is the one we're trying to match to
	pieces = []
	sides = []
	for i in range(k + 1):
		top = n - 1
		bottom = 0