Year of the Cow 2021 Feb Silver

Problems and Contests
#1

Problem Link

Here is my code:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vl = vector<ll>;

#define all(x) begin(x), end(x)
#define dbg(x) for(auto& a: x) cout << a << " "
#define re(x) cin >> x
#define print(x) cout << x << endl;
#define sort(x) sort(all(x))
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ROF(i, b, a) for(int i=(b)-1; i>=a; --i)

int main(){
    int n, k; re(n); re(k);
    // Read in how many years before the current year (2021?) each ancestor lived...
    vl yearsBefore(n);
    FOR(i, 0, n){
        re(yearsBefore[i]);
    }
    // Find which portal interval each ancestor is a part of...
    FOR(i, 0, n){
        yearsBefore[i] = (yearsBefore[i] / 12);
    }
    sort(yearsBefore);
    // dbg(yearsBefore);
    // print("");
    vl differences(n);
    differences[0] = 0;
    FOR(i, 1, n){
        differences[i] = yearsBefore[i] - yearsBefore[i-1];
    }
    // dbg(differences);
    // print("");
    ll sumX = 0;
    sort(differences);
    FOR(i, 0, (differences.size() - (k-2))){
        sumX += (differences[i]);
    }
    print((sumX + (k-1)) * 12);
}

Could someone help me identify what’s wrong with my code?

USACO servers say that I got 1/10 test cases from this solution…

#2

Several issues:

  • You’re ignoring the distance between the first year and the origin. Need to set differences[0] = yearsBefore[0] and also add 1 to all yearsBefore. This should be a bit suspicious because you have a special case that doesn’t fit the pattern.
  • Your accounting for the (k-1) differences to be erased is confusing and doesn’t handle a lot of cases. Why are you going up to n-(k-2)? What if the gaps are all zero? Is the answer really at least (k-1)*12?
  • More straightforward approach: start with the full distance from 0 to yearsBefore[n-1] and subtract away up to (k-1) largest differences[i]-1. View it as a shortest path problem with (k-1) teleports.

Try to handle the cases better and write more straightforward code that directly calculates the answer.

#4

Luckily, this edge case isn’t one of the test cases… :laughing: