The MooTube USACO Problem Again, But Gold

Hi everyone,

Just a quick follow-up note here.

Last time, we talked about a USACO graphs problem: the MooTube problem from the Silver January 2018 contest.

USACO rounds come in four challenge levels: bronze, silver, gold, and platinum. For a given round, moving to a higher challenge level does one or both of two things: presents an entirely different problem, or amps up the amount of input for an existing problem.

The latter is the case for MooTube. A reader alerted me to the fact that there’s also a gold version of MooTube! It’s the same as the silver version except for one thing: the bounds on the number of videos and questions. In the silver version, each is at most 5000. In the gold version, each is at most 100000.

Cranking the amount of input from 5000 to 100000 ruins our breadth-first search solution from last time.

Now What?

Let’s imagine for a sec that Farmer John’s questions have the following relevances: 20, 10, 5. We can first consider all edges with relevance at least 20, and then solve the first question. How do we know how many reachable videos there are at this time? We can use union-find! Each edge we add causes a potential union of two pieces of the graph.

OK – so the first question is done. Now we have to incorporate all edges with relevance at least 10 so that we can solve the second question. Fortunately, 10 is less than 20, so we’re only adding edges here, not taking any away. And that’s a good thing, because union-find supports only adding edges, not removing edges. Once we add these edges, we can take care of the second question by returning the number of reachable videos.

Now for the third question. Again, its relevance, 5, is less than 10, so we can just add edges with relevance at least 5 and then determine the number of reachable videos.

I hope you’re now on-board with the idea that union-find can be used if the relevances go down like this, from 20 to 10 to 5. We just keep adding more and more relevant edges for each subsequent question, because more and more edges become allowed as the relevance threshold drops.

But wait! We have no control over the questions. What if the questions have relevances of 20, 5, and then 10? How are we supposed to get rid of the illegal 5-9 relevances before processing the third question?

We’re not! And here’s the trick for this version of the problem: we sort the questions by relevance, from highest relevance to lowest relevance. No one’s forcing us to solve the questions in the order that they come in, after all. We can collect all the questions, sort them on our own, and then solve them in this more desirable order. Of course we have to be careful to output the answers in the question order, but we can do that by remembering the original position of each question.

I really like this technique: storing the questions offline, rather than answering them online as they come in.

If you read Chapter 8 of my Algorithmic Thinking book: you’re now ready to solve this gold version. If you aren’t able or don’t want to buy the book, you’re OK: the code for the book is all here in this code archive.

Please give it a try! USACO has a Java solution posted, but don’t try too hard to find it until you’ve given this problem a solid effort :)

Written on January 31st , 2021 by Daniel Zingaro