USACO 2016 US Open Contest Bronze Division - Bull in a China Shop

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

In this problem, we need to brute force all variants of placing the pieces, and given that the grid is very small, this can be done without much difficulty complexity wise.

However, because there are quite a few cases you need to worry about, you must be very careful when it comes to implementing the solution.

Another good editorial can be found here

Source codes

The source codes in C++ and Python can be seen below.

#include <fstream>
#include <vector>
using namespace std;

int n;
bool pieces[11][8][8];
vector<int> s[11];

// check if a piece is in bounds and is '#'
bool check(int piece, int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n && pieces[piece][x][y];
}

int main() {
    ifstream cin("bcs.in");
    ofstream cout("bcs.out");
    int k;
    cin >> n >> k;
    char c;
    int left, right, top, bottom;
    for (int i = 0; i <= k; i++) {
        left = n - 1;
        right = 0;
        top = n - 1;
        bottom = 0;
        for (int j = 0; j < n; j++) {
            for (int l = 0; l < n; l++) {
                cin >> c;
                pieces[i][j][l] = (c == '#');
                // find the sides of the piece
                if (pieces[i][j][l]) {
                    bottom = max(bottom, j);
                    top = min(top, j);
                    right = max(right, l);
                    left = min(left, l);
                }
            }
        }
        s[i] = {left, right, top, bottom};
    }

    // try all the pieces and shifts to find the correct one
    for (int i = 1; i <= k; i++) {
        for (int j = i + 1; j <= k; j++) {
            for (int idx = s[i][3] - n + 1; idx <= s[i][2]; idx++) {
                for (int idy = s[i][1] - n + 1; idy <= s[i][0]; idy++) {
                    for (int jdx = s[j][3] - n + 1; jdx <= s[j][2]; jdx++) {
                        for (int jdy = s[j][1] - n + 1; jdy <= s[j][0]; jdy++) {
                            bool good = true;
                            for (int x = 0; x < n; x++) {
                                for (int y = 0; y < n; y++) {
                                    bool ipiece = check(i, x + idx, y + idy);
                                    bool jpiece = check(j, x + jdx, y + jdy);
                                    // two '#' are in the same place
                                    if (ipiece && jpiece) {
                                        good = false;
                                        break;
                                    }
                                    // the result doesn't match the figurine
                                    if (pieces[0][x][y] != (ipiece || jpiece)) {
                                        good = false;
                                        break;
                                    }
                                }
                                if (!good) { break; }
                            }
                            if (good) {
                                cout << i << " " << j << endl;
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}

with open("bcs.in", "r") as fin:
    tokens = fin.read().split()
it = iter(tokens)
n = int(next(it))
k = int(next(it))
pieces = []
s = []
for i in range(k + 1):
    left = n - 1
    right = 0
    top = n - 1
    bottom = 0
    piece = [[False] * n for _ in range(n)]
    for j in range(n):
        line = next(it)
        for l in range(n):
            piece[j][l] = (line[l] == '#')
            if piece[j][l]:
                bottom = max(bottom, j)
                top = min(top, j)
                right = max(right, l)
                left = min(left, l)
    pieces.append(piece)
    s.append([left, right, top, bottom])

def check(piece_index, x, y):
    return 0 <= x < n and 0 <= y < n and pieces[piece_index][x][y]

result_found = False
output_i = 0
output_j = 0
for i in range(1, k + 1):
    for j in range(i + 1, k + 1):
        for idx in range(s[i][3] - n + 1, s[i][2] + 1):
            for idy in range(s[i][1] - n + 1, s[i][0] + 1):
                for jdx in range(s[j][3] - n + 1, s[j][2] + 1):
                    for jdy in range(s[j][1] - n + 1, s[j][0] + 1):
                        good = True
                        for x in range(n):
                            if not good:
                                break
                            for y in range(n):
                                ipiece = check(i, x + idx, y + idy)
                                jpiece = check(j, x + jdx, y + jdy)
                                if ipiece and jpiece:
                                    good = False
                                    break
                                if pieces[0][x][y] != (ipiece or jpiece):
                                    good = False
                                    break
                        if good:
                            output_i = i
                            output_j = j
                            result_found = True
                            break
                    if result_found:
                        break
                if result_found:
                    break
            if result_found:
                break
        if result_found:
            break
    if result_found:
        break

with open("bcs.out", "w") as fout:
    fout.write(f"{output_i} {output_j}\n")