USACO Gold 2019 Open - I Would Walk 500 Miles

Official Analysis (C++)

Solution 1: Prim's Algorithm

For this problem, we want to maximize the minimum of the number of miles two cows are willing to walk, henceforth referred to as $M$. Let's consider a Minimum Spanning Tree (MST) of all $N$ cows. By adding the $i$-th edge to the MST, it implies that all edges between the rest $N - i$ components have weights higher or equal than this added edge, or, in other words, $M$ is equal to the weight of this added edge.

In case of splitting the cows into $K$ groups, we remove the $K - 1$ edges from the MST which have the maximum weight. $M$ is then equal to the weight of the minimum of those removed edges. If the edges in the MST are sorted in ascending order, $M$ would be the weight of the $N - K + 1$-th edge of the MST.

As the typical implementation of Kruskal's Algorithm requires $\mathcal{O}(N^2 \log N)$ time for a dense graph as in our case, we use instead Prim's Algorithm with linear search for the closest vertex. Each scan only takes $\mathcal{O}(N)$ time, and we only have to do $N$ scans.

Time Complexity: $\mathcal{O}(N^2)$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 2019201997LL;
const ll FACTOR1 = 2019201913LL;
const ll FACTOR2 = 2019201949LL;

/**
 * @return the number of miles cow a + 1 and b + 1 are willing to walk to see

Copy
import java.io.*;
import java.util.*;

public class Walk {
	static final long MOD = 2019201997L;
	static final long FACTOR1 = 2019201913L;
	static final long FACTOR2 = 2019201949L;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("walk.in"));

Solution 2: Kruskal's Algorithm & Two-Pass Radix Sort

Alternatively, we can also use Kruskal's Algorithm to construct our MST. Note that only the step of sorting all edges takes too long time. If we manage to sort all edges in linear time, we might be able to solve it with Kruskal's Algorithm as well.

To sort these edges, we can apply a two-pass radix sort. In particular, we first use counting sort to sort the first 16 bits ($[0, 2^{16})$) of the weights. Then, in the second iteration, we sort the rest 16 bits ($[2^{16}, 2^{32})$). After the sorting process, we apply the unmodified Kruskal's Algorithm on the edges and $M$ is equal to the weight of the $N - K + 1$-th longest edge of the MST.

Time Complexity: $\mathcal{O}(N^2)$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

 Code Snippet: DSU (Click to expand)

const ll MOD = 2019201997LL;
const ll FACTOR1 = 2019201913LL;
const ll FACTOR2 = 2019201949LL;

Solution 3: Math

Since this problem has its roots in optimizing a given weight expression, we are motivated to use math.

First, we can use modular arithmetic to find a direct expression for the modular residue. The goal is to find an expression for the modular residue involving only basic operations that we will be able to optimize with mathematical techniques. Using modular arithmetic properties (negative numbers in modular arithmetic), consider the expression $\pmod{2019201997}$ to reduce the numbers:

Since $x,y$ are bounded by $N \leq 7500,$ this expression will always give a negative value whose absolute value does not exceed the modulus $2019201997.$ Thus, we can easily find an expression for the modular residue from here if we just shift up by the modulus $2019201997$ once:

Now, it remains to optimize this expression. Formally, we must find a $K$-partition of the cows such that

is maximized.

Now, let's analyze the function's behavior: for large $x,y,$ the expression becomes small, and for small $x,y,$ the expression becomes large.

But remembering the condition that $x,y$ must be in different groups to contribute to the answer, this means that large $x,y$ should be together in the same group (to greedily avoid making the expression small) and small $x,y$ should be in different groups (to greedily make the expression large). This leads to the following greedy strategy:

Make one group with all the largest cows that can fit and $k-1$ groups with all the smallest cows. Of course, the $k-1$ smallest cows are just $1 \dots k-1,$ so this means that the other $n-(k-1)$ cows will be in the large group.

Now that we have pinpointed the optimal grouping, we can find the answer by going back to the question: we want to minimize the expression. To minimize the expression, we should greedily choose the largest cows that are in different groups (since large $x,y$ make the expression smaller). Clearly, this means that we should take cow $n,$ the largest cow in the group of large cows, and $k-1,$ the largest cow not in the group of large cows.

Recall that the problem statement requires $x < y,$ so we have $x = k - 1, y = n.$ Our answer is as easy as a substitution of these values into the modular residue expression $2019201997 - 84 x - 48 y:$

In retrospect, this solution is equivalent to performing Kruskal's MST algorithm by hand when we analyze the edge weight expression and use greedy logic to create the optimal grouping. (So the previous solutions will find the exact same grouping.)

Time Complexity: $\mathcal{O}(1)$

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

int main() {
	freopen("walk.in", "r", stdin);
	freopen("walk.out", "w", stdout);
	int N, K;
	cin >> N >> K;
	long long answer = 2019201997LL - 48LL * N - 84LL * (K - 1LL);
	cout << answer << endl;
}

Copy
import java.io.*;
import java.util.*;

public class Walk {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("walk.in"));
		StringTokenizer st = new StringTokenizer(br.readLine());
		br.close();

		int N = Integer.parseInt(st.nextToken());