USACO 2018 US Open Contest Bronze Division - Team Tic Tac Toe

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Run brute force and check all cases using sets.

Source codes

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

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

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

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

    set<char> winners;
    set<pair<char, char> > pairwinners;

    for(int i = 0; i < 3; i++)
    {
        set<char> letters;
        for(int j = 0; j < 3; j++)
            letters.insert(mat[i][j]);
        if(letters.size() == 1)
            winners.insert(*letters.begin());
        if(letters.size() == 2)
        {
            char a = *letters.begin();
            letters.erase(a);
            char b = *letters.begin();
            letters.erase(b);
            pairwinners.insert({a, b});
        }
    }

    for(int i = 0; i < 3; i++)
    {
        set<char> letters;
        for(int j = 0; j < 3; j++)
            letters.insert(mat[j][i]);
        if(letters.size() == 1)
            winners.insert(*letters.begin());
        if(letters.size() == 2)
        {
            char a = *letters.begin();
            letters.erase(a);
            char b = *letters.begin();
            letters.erase(b);
            pairwinners.insert({a, b});
        }
    }

    for(int i = 0; i < 1; i++)
    {
        set<char> letters;
        for(int j = 0; j < 3; j++)
            letters.insert(mat[j][j]);
        if(letters.size() == 1)
            winners.insert(*letters.begin());
        if(letters.size() == 2)
        {
            char a = *letters.begin();
            letters.erase(a);
            char b = *letters.begin();
            letters.erase(b);
            pairwinners.insert({a, b});
        }
    }

    for(int i = 0; i < 1; i++)
    {
        set<char> letters;
        for(int j = 0; j < 3; j++)
            letters.insert(mat[j][2-j]);
        if(letters.size() == 1)
            winners.insert(*letters.begin());
        if(letters.size() == 2)
        {
            char a = *letters.begin();
            letters.erase(a);
            char b = *letters.begin();
            letters.erase(b);
            pairwinners.insert({a, b});
        }
    }

    cout << winners.size() << '\n';
    cout << pairwinners.size() << '\n';
    return 0;
}

with open("tttt.in", "r") as fin:
    mat = [list(fin.readline().strip()) for _ in range(3)]

winners = set()
pairwinners = set()

# Check rows
for i in range(3):
    letters = set()
    for j in range(3):
        letters.add(mat[i][j])
    if len(letters) == 1:
        winners.add(next(iter(letters)))
    if len(letters) == 2:
        a = min(letters)
        b = max(letters)
        pairwinners.add((a, b))

# Check columns
for i in range(3):
    letters = set()
    for j in range(3):
        letters.add(mat[j][i])
    if len(letters) == 1:
        winners.add(next(iter(letters)))
    if len(letters) == 2:
        a = min(letters)
        b = max(letters)
        pairwinners.add((a, b))

# Check primary diagonal
letters = set()
for i in range(3):
    letters.add(mat[i][i])
if len(letters) == 1:
    winners.add(next(iter(letters)))
if len(letters) == 2:
    a = min(letters)
    b = max(letters)
    pairwinners.add((a, b))

# Check secondary diagonal
letters = set()
for i in range(3):
    letters.add(mat[i][2-i])
if len(letters) == 1:
    winners.add(next(iter(letters)))
if len(letters) == 2:
    a = min(letters)
    b = max(letters)
    pairwinners.add((a, b))

with open("tttt.out", "w") as fout:
    fout.write(str(len(winners)) + "\n")
    fout.write(str(len(pairwinners)) + "\n")