USACO 2022 US Open Contest Bronze Division - Counting Liars

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can brute force through each of the N relevant places and find the minimum number of people who are lying.

Source codes

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

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

int main() 
{

    int n;
    cin >> n;
    vector<pair<char, int> > vp(n+1);
    for(int i = 1; i <= n; i++)
        cin >> vp[i].first >> vp[i].second;

    int ans = n;
    for(int i = 1; i <= n; i++)
    {
        int oki = 0;
        for(int j = 1; j <= n; j++)
        {
            if(vp[j].first == 'G' && vp[i].second < vp[j].second)
                oki++;
            if(vp[j].first == 'L' && vp[i].second > vp[j].second)
                oki++;
        }
        ans = min(ans, oki);
    }

    cout << ans;
    return 0;
}

n = int(input())
vp = []
for _ in range(n):
    c, x = input().split()
    vp.append((c, int(x)))
ans = n
for i in range(n):
    oki = 0
    for j in range(n):
        if vp[j][0] == 'G' and vp[i][1] < vp[j][1]:
            oki += 1
        if vp[j][0] == 'L' and vp[i][1] > vp[j][1]:
            oki += 1
    ans = min(ans, oki)
print(ans)