USACO 2019 US Open Contest Silver Division - Left Out

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

All rows should either be the same or flipped version of itself (e.g. RLL or LLR) and same with the columns. Wherever the pattern is broken is the cow left out.

Source code

The source code in C++ can be seen below.

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

const int MAX_N = 1e3;

char mat[MAX_N + 5][MAX_N + 5];
int n;

char flip (char ch) {
    if (ch == 'L') {
        return 'R';
    }
    return 'L';
}

void flipLine (int lin) {
    int col;
    for (col = 0; col < n; col++) {
        mat[lin][col] = flip(mat[lin][col]);
    }
}

void flipCol (int col) {
    int lin;
    for (lin = 0; lin < n; lin++) {
        mat[lin][col] = flip(mat[lin][col]);
    }
}

int count (pair<int, int> coltL, pair<int, int> coltR, int val) {
    int linL = coltL.first, colL = coltL.second;
    int linR = coltR.first, colR = coltR.second;

    int lin, col, ans = 0;
    for (lin = linL; lin <= linR; lin++) {
        for (col = colL; col <= colR; col++) {
            ans += (mat[lin][col] == val);
        }
    }

    return ans;
}

int main () {
    ifstream cin("leftout.in");
    ofstream cout("leftout.out");

    int lin, col;
    string line;

    cin >> n;
    for (lin = 0; lin < n; lin++) {
        cin >> line;
        for (col = 0; col < n; col++) {
            mat[lin][col] = line[col];
        }
    }

    for (lin = 0; lin < n; lin++) {
        if (mat[lin][0] == 'L') {
            flipLine(lin);
        }
    }
    for (col = 0; col < n; col++) {
        if (mat[0][col] == 'L') {
            flipCol(col);
        }
    }

    /* Example */
    int cntR = count({1, 1}, {n - 1, n - 1}, 'R');
    int cntL = count({1, 1}, {n - 1, n - 1}, 'L');
    if (!cntR) {
        cout << "1 1\n";
        return 0;
    }
    if (cntL == n - 1) {
        for (lin = 1; lin < n; lin++) {
            if (count({lin, 1}, {lin, n - 1}, 'L') == n - 1) {
                cout << (lin + 1) << " 1\n";
                return 0;
            }
        }
    }
    if (cntL != 1) {
        cout << "-1\n";
        return 0;
    }
    for (lin = 0; lin < n; lin++) {
        for (col = 0; col < n; col++) {
            if (mat[lin][col] == 'L') {
                cout << lin + 1 << " " << col + 1 << "\n";
                return 0;
            }
        }
    }

    return 0;
}