USACO 2017 January Contest Bronze Division - Cow Tipping

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Start from bottom to top and from right to left and every time we have a cow which is flipped, we unflip the entire grid.

Source codes

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

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

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

    int n, cnt = 0;
    cin >> n;

    vector<vector<char> > mat(n, vector<char> (n));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> mat[i][j];

    for(int i = n-1; i >= 0; i--)
        for(int j = n-1; j >= 0; j--)
            if(mat[i][j] == '1')
            {
                cnt++;
                for(int q = 0; q <= i; q++)
                    for(int p = 0; p <= j; p++)
                        mat[q][p] = '0' + '1' - mat[q][p];
            }

    cout << cnt;
    return 0;
}

with open("cowtip.in", "r") as fin:
    n = int(fin.readline().strip())
    mat = [list(fin.readline().strip()) for _ in range(n)]
cnt = 0
for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if mat[i][j] == '1':
            cnt += 1
            for q in range(i+1):
                for p in range(j+1):
                    mat[q][p] = '1' if mat[q][p] == '0' else '0'
with open("cowtip.out", "w") as fout:
    fout.write(str(cnt))