In this blog post I'll go over the USACO Counting Liars Bronze US Open 2022 Problem 2 using other resources and solutions.
According to the problem statement, we are given a set of one dimensional vectors and are told to find the minimum number of vectors that have to be dropped such that all the remaining vectors have some common point that sits on each vector. For example, if we are given the following input:
Then we have to drop at least one of the two vectors because the two of them face opposite directions and don't intersect.
The solution would be to take in the input and put them in two seperate arrays, one for the greater than inputs and another for the less than inputs and sort the arrays. Whenever we choose any greater than input and the less than input immediately after it, we can count the number of liars by adding the index of the less than input to the size of the greater than array minus the index of the greater than input minus one. This works because the index of the less than input is equal to the number of less than inputs before the greater than input:
As shown in the number line above, the index of the less than input at 4 is 1 and the number of less than inputs before the greater than input (2 in our case) is 1.
The number of greater than inputs that do not match the vector is equivalent to the number of greater than inputs in total minus the index of the greater than input we are on (0 in our case) minus 1. Over here, we have 3 greater than inputs, so we get . This works because we are basically just looking for then number of elements after the index of the greater than input.
We can use this method of calculating the number of liars and iterate over each greater than input and apply it. This method takes time if we run binary search on the less than inputs each time we iterate over a greater than input, but we can also take time because it is underneath the time limit.
Let's go through an implementation in C++:
A lesson learned through this problem is to divide the input into seperate categories if applicable. Also, it helps to write down the constraints of the problem statement again if you are missing a few edge cases in the judging result. The answer may lie in some point forgotten to cover in the statement.