USACO 2019 January Contest Bronze Division - Guess the Animal

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The answer is the maximum length of the intersection of two animals.

Source codes

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

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


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

    int n;
    cin >> n;

    vector<vector<string> > v(n+1);
    for(int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        int x;
        cin >> x;

        for(int j = 0; j < x; j++)
        {
            string a;
            cin >> a;
            v[i].push_back(a);
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        set<string> s;
        for(auto x : v[i])
            s.insert(x);
        for(int j = i+1; j <= n; j++)
        {
            int cnt = 0;
            for(auto x : v[j])
                if(s.find(x) != s.end())
                    cnt++;
            ans = max(ans, cnt);
        }
    }
    cout << ans+1;
    return 0;

}

with open("guess.in", "r") as fin:
    tokens = fin.read().split()
n = int(tokens[0])
index = 1
v = []
for i in range(n):
    s = tokens[index]
    index += 1
    x = int(tokens[index])
    index += 1
    lst = []
    for j in range(x):
        lst.append(tokens[index])
        index += 1
    v.append(lst)
ans = 0
for i in range(n):
    sset = set(v[i])
    for j in range(i+1, n):
        cnt = 0
        for token in v[j]:
            if token in sset:
                cnt += 1
        ans = max(ans, cnt)
with open("guess.out", "w") as fout:
    fout.write(str(ans+1))