USACO Bronze 2016 Open - Bull in a China Shop

Authors: Maggie Liu, David Zhang


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×NN \times N grid, we need to find the sides of the pieces to determine how far to shift them.

Warning!

The official solution doesn't check if any '#' fall outside the N×NN \times N grid.

As we iterate the pieces, we find the left, right, top and bottom sides of the piece and store them in the ss array. When we are shifting, we shift piece[i]\texttt{piece[i]} idy\texttt{idy} units to the left and idx\texttt{idx} units up, and shift piece[j]\texttt{piece[j]} jdy\texttt{jdy} units to the left and jdx\texttt{jdx} units up. This will send the piece at (x+idx,y+idy)(x + \texttt{idx}, y + \texttt{idy}) to (x,y)(x, y) and the piece at (x+jdx,y+jdy)(x + \texttt{jdx}, y + \texttt{jdy}) to (x,y)(x, y). So, we see that idy\texttt{idy} must be bounded by rightn+1\texttt{right} - n + 1 and left\texttt{left}, and idx\texttt{idx} must be bounded by bottomn+1\texttt{bottom} - n + 1 and top\texttt{top}, with jdy\texttt{jdy} and jdx\texttt{jdx} bounded similarly. Because of that, every '#' will fall inside the N×NN \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 (pieces[0]\texttt{pieces[0]}), then this shift will not work.

Implementation

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

C++

#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() {

Java

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];

Python

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

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!