USACO 2021 February Contest Silver Division - Year of the Cow

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We keep a set in which for each number we add the interval it belongs to (an interval is a sequence of consecutive numbers, of length 12.

This can be done this using the formula \((y - 1) / 12 + 1 = (y - 1 + 12) / 12 = (y + 11) / 12\);

Then because we sorted them, we keep in a vector the length of the distances between each two positions in the set (e.g. set[1] - set[0]; set[2] - set[1] etc.). Last but not least, we sort this vector and count the answer.

Source code

The source code in C++ can be seen below.

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

int n, k;
int val, lst;

set<int> s;
vector<int> dist;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
    {
        cin >> val;
        s.insert((val+11) / 12);
    }

    long long ans = *s.rbegin();
    while(!s.empty())
    {
        int sm = *s.begin();
        dist.push_back(sm - lst - 1);
        lst = sm;
        s.erase(sm);
    }
    sort(dist.begin(), dist.end(), greater<int> ());
    for(int i = 0; i < k-1 && i < (int) dist.size(); ++i)
        ans -= dist[i];
    cout << ans * 12;

    return 0;
}