7 PM – Intro to Competitive Programming – Darin

What We Did Today:

1. Solved the Cowntract Tracing problem theoretically

Homework:

Implement the code for https://usaco.org/index.php?page=viewproblem2&cpid=1348!

Theory:

Group final cows into sick and non sick
Think of each cows as having a window (net effect of sickness spread)

If we know each cows window, we can compute the initial cow count

I = number of cows in one sick group, W = cow window

I/W = initial cow count per group

Idea: Sum up all the I/W over the list of cows

How to compute W?

Cases (note that each I below is variable, so its per group basis):
Take the smallest odd group and compute:
W = I

Take edge groups and compute:
W = 2*I – 1

Take (if there exists) the smallest even group and compute:
W = I – 1

Between these candidate W’s, choose the min over all of them.

Notes:

You can reach out to me at ddjapri@ayclogic.com if you have any questions!

You can find class notes here.