After a lot of hard work and several failed attempts, I finally passed USACO Silver in the latest USACO competition. The difficulty from USACO Bronze to Silver was no joke: silver introduced recursion, graph problems, prefix sum arrays, pointers and greedy problems to name a few. While I certainly knew many of these before, learning to effectively utilize these techniques was also difficult. However, my effort was not for nothing, as I have become a much better programmer because of this. Now let’s talk about the latest contest!
The first problem is called The Best Lineup, and consists of our favorite bovine enthusiast Farmer John attempting to construct a lineup b of cows based on the existing lineup a. In both lineups, each cow has an integer value attributed to it but cause of course they do. Lineup b is initially empty, but FJ will gradually move the cows from lineup a to lineup b in order. At each cow, FJ can choose to add it or not, so lineup b will not necessarily be the same size as lineup a. FJ’s goal is to construct lineup b in a way that it has the maximum lexicographical value. However, Farmer John is allowed to move one cow and insert it anywhere in the lineup to change how lineup b will form.
Line Up
Read the problem statement here.
This problem is generally quite simple. First, we see that in order to maximize lexicographical value, we will always skip a cow if a following cow has a larger value. This is because lexographically speaking, the earlier values are counted first, so “dcab” is smaller than “dcb”. This leads to our second observation: that the most efficient cow to move will be one that is overshadowing an earlier cow. This is because it will allow the formerly overshadowed cow to join lineup b, thus increasing it’s lexographical order. Lastly, we see that the best way to maximize this is by uncovering the largest overshadowed value. However, because we can only move one cow, not all cows can be uncovered. If a cow has two values behind it that are larger than it, no matter what we do, we will need to remove it. Thus, the rule becomes to find the largest value xi that is the second largest value in the subarray [i, n-1]. This is very simple to find in O(N) time if we iterate from back to front, tracking the largest two values we find. Then, we will track what the largest value is that is larger than or equal to the second largest value but smaller than the largest value. Now, we know that the value we are going to move is the one that overshadowed the largest second largest value. Knowing this, we can iterate a second time from back to front and skipping the value we’ve decided to move, and only adding descending values to lineup b. Finally we add the skipped value back, yielding the final lineup.
Vocabulary Quiz
Read the problem statement here.
The major observation is that you can store every word in a tree structure. Because of how the words are specified using prefixes, you can use each node to represent a unique word, with its parent being its closest prefix. Now, the problem asks for the number of letters Bessie needs to reveal for there only be one possible answer. This is equivalent to reaching a leaf node in our tree structure since leaf node has no children, meaning that that is the only word that can contain the given prefix.
Not only this, all words that Elize will need to guess from are leaf nodes in this tree, since these words are “not a prefix of some other word”. So, how do we find the number of letters Elsie needs? For convenience, we will define this as the height of this node in the tree. This makes sense since the number of letters needed is essentially the number of steps you need to take, with each step in our tree representing one additional letter added.
However, there are some cases where Elsie can guess earlier, like when a node only has one final descendant with many intermediate nodes. Even though there is only one possible answer, the height of the tree does not represent this. Hence, for each leaf node, if its parent has only one child, we need to delete the parent and link the leaf node to it’s grandparent. Repeat this until the leaf node’s parent has more than one child. We will perform this each time before outputting the height of the leaf node to ensure that we always check for this edge case before printing. Also performing this before each output best minimizes the number of times we need to call this while accounting for all cases.
Finally, what is the time complexity? Despite the trees structure and the constant deletion operations, this is actually O(N). This is because the only operations we do are adding and deleting nodes from the tree structure, each O(1) operations. Secondly, since we only ever perform each action once for each node, the final time complexity is O(N).
Transforming Pairs
Read problem statement here.
This problem was also quite interesting. We are given values a, b, c, d, and are trying to make a and b equal to c and d. At each time stamp, we have two options: add a to b or add b to a. However, we notice that if we try to do the reverse, reduce c to a and d to b, there is only ever one possible option. If we look at the case where d > c, we notice that the last computation must have been adding c to d. This is because we can rewrite d as c + x, with x being the previous d value. We cannot do the opposite since we cannot do so while ensuring that both d > c and that x is a positive value. We can use this to calculate the second to last state, and then the third to last state and so on until we have computed the entire sequence of moves. From this, telling if it is possible is simply a matter of seeing if at any point the condition is satisfied. If it is never satisfied, ie. c becomes less than a or d becomes less than d, we break and print -1. This is very simple to implement and is honestly a very cool example of backtracking and how it can simplify an otherwise complex problem.
Final Remarks
Now that I have passed silver, I will start working on passing gold and learning the required techniques. I particularly look forward to learning more Dynamic Programming, since it is just a very cool and powerful way to solve problems. I have also begun transitioning to using C++ as opposed to Java, which I hope will help me out with the much more difficult and demanding problems I will face is gold. Thanks for reading!
Lineup Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeMap;
public class lineup {
public static void solve(BufferedReader br) throws IOException {
int n = Integer.parseInt(br.readLine());
int[] as = new int[n];
String[] line = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
as[i] = Integer.parseInt(line[i]);
}
int[] occ = new int[n];
int max1 = 0;
int max2 = 0;
for (int i = n-1; i >= 0; i--) {
if (as[i] < max1) occ[i]++;
if (as[i] < max2) occ[i]++;
if (as[i] >= max1) {
max2 = max1;
max1 = as[i];
}
else if (as[i] > max2) {
max2 = as[i];
}
}
int max_pos = -1;
int max_skipped_pos = -1;
int skipper_psum = 0;
for (int i = n-1; i >= 0 ; i--) {
if (max_pos == -1 || as[max_pos] < as[i]) {
max_pos = i;
}
if (as[i] < as[max_pos] && occ[i] == 1 && (max_skipped_pos == -1 || as[i] > as[max_skipped_pos])) {
max_skipped_pos = i;
skipper_psum = max_pos;
}
}
TreeMap<Integer, Integer> bs = new TreeMap<>((v1, v2)->v2-v1);
max_pos = -1;
for (int i = n-1; i >= 0; i--) {
if (i == skipper_psum) continue;
if (max_pos == -1 || as[i] > as[max_pos]) {
max_pos = i;
}
if (as[i] >= as[max_pos]) {
bs.putIfAbsent(as[i], 0);
bs.replace(as[i], bs.get(as[i])+1);
}
}
bs.putIfAbsent(as[skipper_psum], 0);
bs.replace(as[skipper_psum], bs.get(as[skipper_psum])+1);
for (int k : bs.keySet()) {
for (int i = 0; i < bs.get(k); i++) {
if (k != bs.firstKey() || i != 0)
System.out.print(" ");
System.out.print(k);
}
}
System.out.print('\n');
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
solve(br);
}
}
}
Vocabulary Quiz Code:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.TreeSet;
public class vocab {
public static class Node {
int p;
int h;
int id;
int c;
Node(int p, int id, int h) {
this.p = p;
this.id = id;
this.h = h;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Node[] nodes = new Node[n+1];
String[] line = br.readLine().split(" ");
nodes[0] = new Node(-1, 0, 0);
for (int i = 1; i <= n; i++) {
int p = Integer.parseInt(line[i-1]);
nodes[i] = new Node(p, i, nodes[p].h+1);
nodes[nodes[i].p].c++;
}
while (true) {
int w;
try {
w = Integer.parseInt(br.readLine());
}
catch(Exception e) { break; }
int p = nodes[w].p;
while (p != -1 && nodes[p].c == 1) {
p = nodes[w].p = nodes[p].p;
nodes[w].h--;
}
System.out.println(nodes[w].h);
while (nodes[w].p != -1 && nodes[w].c == 0) {
nodes[nodes[w].p].c--;
w = nodes[w].p;
}
}
}
}Transforming Pairs Code:
import java.io.*;
public class pairs {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
String[] line = br.readLine().split(" ");
double a = Long.parseLong(line[0]);
double b = Long.parseLong(line[1]);
double c = Long.parseLong(line[2]);
double d = Long.parseLong(line[3]);
long cnt = 0;
while (true) {
if (a == c && b == d) break;
if (c < a || d < b) break;
if (c > d) {
long steps = (long)(c-Math.max(a, d))/(long)d;
if (steps == 0) {
steps = 1;
}
cnt += steps;
c -= steps*d;
}
else if (d > c) {
long steps = (long)(d-Math.max(b, c))/(long)c;
if (steps == 0) steps = 1;
d -= (steps*c);
cnt += steps;
}
else break;
}
if (a == c && b == d) System.out.println(cnt);
else System.out.println(-1);
}
}
}
Lingyuan's blog 