USACO 2022 US Open Contest, Bronze Problem 2. Counting Liars

USACO 2022 US Open Contest, Bronze Problem 2. Counting Liars

Bessie the cow is hiding somewhere along the number line. Each of Farmer John's NN other cows (1≤N≤10001≤N≤1000) have a piece of information to share: the ii-th cow either says that Bessie is hiding at some location less than or equal to pipi, or that Bessie is hiding at some location greater than or equal to pipi (0≤pi≤1090≤pi≤109).
Unfortunately, it is possible that no hiding location is consistent with the answers of all of the cows, meaning that not all of the cows are telling the truth. Count the minimum number of cows that must be lying.

 

 

SAMPLE INPUT:

2
G 3
L 5

SAMPLE OUTPUT:

0

It is possible that no cow is lying.

SAMPLE INPUT:

2
G 3
L 2

SAMPLE OUTPUT:

1

At least one of the cows must be lying.

Problem credits: Jesse Choe

USACO 2022 US Open Contest, Bronze Problem 2. Counting Liars 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]
(Analysis by Benjamin Qi)
We can rephrase the problem as finding an integer hh such that the number of cows who provided information inconsistent with Bessie hiding at hh is minimized. For the first sample input, any hh satisfying 3≤h≤53≤h≤5 is consistent with there being zero liars. For the second sample input, any hh satisfying h≤1h≤1 or h≥2h≥2 is consistent with there being a single liar.
Of course, we don't have time to try all possible values of hh. We can reduce the number of hh we need to consider by observing that if we move hh leftwards or rightward until it equals one of the pipi provided in the input, the number of cows that are inconsistent with hh either stays the same or decreases. For example, consider the first sample input:

• If we move h=6h=6 leftwards to h=5h=5, the number of cows inconsistent with hh stays the same (zero for both values of hh).
• If we move h=4h=4 rightwards to h=5h=5, the number of cows inconsistent with hh decreases from one to zero.

So it suffices to only consider the case when h=pih=pi for some ii. That is,

For a single value of hh, we can count the number of cows inconsistent with hh in O(N)O(N) time by looping over all cows in the input. So the overall time complexity is O(N2)O(N2).
Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class CountingLiarsQuadratic {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader
(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        Information[] infos = new Information[n];
        for (int j = 0; j < n; j++) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            char direction = tokenizer.nextToken().charAt(0);
            int reference = Integer.parseInt(tokenizer.nextToken());
            infos[j] = new Information(direction, reference);
        }
        int answer = n;
        for (Information tight : infos) {
            int x = tight.reference;
            int liars = 0;
            for (Information info : infos) {
                if (info.direction == 'G' ? x < info.reference :
 x > info.reference) {
                    liars++;
                }
            }
            answer = Math.min(answer, liars);
        }
        System.out.println(answer);
    }
 
    public static class Information {
        public final char direction;
        public final int reference;
 
        public Information(char direction, int reference) {
            this.direction = direction;
            this.reference = reference;
        }
    }
}

Jichao Qian's code:

#include <stdio.h>
#include <stdint.h>
 
#include <vector>
#include <algorithm>
using namespace std;
 
 
int main()
{
    int N;
    scanf("%d", &N);
 
    vector<pair<int, int>> locations(N);
    for (int idx = 0; idx < N; ++idx)
    {
        char dir[10];
        scanf("%s", dir);
        scanf("%d", &locations[idx].first);
        if (dir[0] == 'G')
            locations[idx].second = -1;
        else
            locations[idx].second = +1;
    }
 
    int minLiars = N;
    sort(locations.begin(), locations.end());
 
    for (int idx = 0; idx < N; ++idx)
    {
        int numLiars = 0;
        for (int jdx = 0; jdx < idx; ++jdx)
            if (locations[jdx].second == 1)
                ++numLiars;
 
        for (int jdx = idx+1; jdx < N; ++jdx)
            if (locations[jdx].second == -1)
                ++numLiars;
 
        minLiars = min(numLiars, minLiars);
    }
 
    printf("%d\n", minLiars);
}

Bonus: Solve the problem in O(NlogN)O(Nlog⁡N) time.
[/hide]