USACO Cow College Problem

This article discusses the Cow College problem in the USA Computing Olympiad (USACO) Bronze Division December 2022 contest, and contains the Python code solution.

USACO Cow College problem

Cow College problem

The Cow College problem was one of the problems in the USACO December 2022 Bronze Division contest. The programming language we will use in this blog post is Python.

You can read the Cow College problem. Make sure you understand the problem first. Read it many times, if necessary. Then, write the algorithm on paper before coding anything. For your algorithm, you can write either pseudocode or a diagrammatical flowchart.

Test Input

This is the test input on the USACO problem page. You can either save the contents of the input into a .in file or copy-paste it on the Terminal when running the program and it waits for your input.

INPUT

4
1 6 4 6

OUTPUT

12 4

Programming Solution Logic

The goal is to find the maximum amount that can be earned by Farmer John and the subsequent tuition amount that he can charge.

The first line is N, the number of cows. We will convert it to an int.

The second line is a space separated string of N numbers, where each number is the maximum tuition a cow can pay. We will split the numbers, convert the numbers to int and dump them into a list (array) that we will call tuition.

Look at the test case.

To make it easier, let us sort the maximum tuition amount first.

So, the tuition amounts the four cows can pay are:

1 4 6 6

Let us trace the amounts if we increase the maximum tuition amount one by one.

If the tuition amount is set to $1, 4 cows can pay for it, and the total becomes 4 * 1 = $4.

If the tuition amount is set to $4, 3 cows can pay for it, and the total becomes 3 * 4 = $12.

If the tuition amount is set to $6, 2 cows can pay for it, and the total becomes 2 * 6 = $12.

We return the maximum corresponding total tuition amount ($12) along with the corresponding individual tuition amount ($4), so the returned value is 4 10.

To implement this, we need to iterate through all the sorted tuition amounts. Before iterationg through the loop, we initialize a varible to store the maximum tuition amount (first number in output) and a second variable to store the optimal tuition amount (second number in output)

For every iteration, we find the number of cows that can afford this tuition (all the cows on the right side), which is the total length of the tuition amount list - current index of the list.

Next, we calculate the current tuition that these cows can afford by multiplying the current tuition with the number of cows that can afford.

If this current tuition amount is greater than the maximum tuition amount, update the maximum tuition amount and optimal tuition amount.

After completing the for loop iterations, you will be left with the maximum tuition and optimal tuition amount.

My Python solution

This is my Python solution:

# line 1: N = number of cows
# line 2: cow1_tuition cow2_tuition ... cowN_tuition

# 4
# 1 6 4 6
# ans = 12 4

N = input()
tuition = [int(x) for x in input().split()]

tuition = sorted(tuition)

# 1, 4, 6, 6
# length of list - index = number of cows that can afford the tuition

max_tuition = 0
optimal_tuition = 0

for i, x in enumerate(tuition):    
    num_of_cows = len(tuition) - i # num of cows that can attend college with this tuition
    current_tuition = x * num_of_cows
    if current_tuition > max_tuition:
        max_tuition = current_tuition
        optimal_tuition = x

# answer
print(max_tuition, optimal_tuition)

Running the Python code

Run the Python code from your Terminal. If you are running it without an input file, you have to manually enter the input.

$ python cow_college.py 
4
1 6 4 6

cat INPUT | python PROGRAM

If you are running it by piping it from an input file cow_college_1.in

$ cat cow_college_1.in | python cow_college.py 
12 4

< INPUT python PROGRAM

$ < cow_college_1.in python cow_college.py 
12 4

The output is the same in all three cases.

Submit the Python code

Scroll down the USACO problem page and submit your code. Make sure you change the language to Python 3.6.9 and click on Submit Solution. It will take a few seconds to grade your solution.

Conclusion

If there is anything you would like me to add to this article, feel free to comment below or contact me. Thanks.

Related Posts

If you have any questions, please contact me at arulbOsutkNiqlzziyties@gNqmaizl.bkcom. You can also post questions in our Facebook group. Thank you.