USACO 2018 January Contest, Gold Problem 1. MooTube
USACO January 2018 - MooTube
Problem Statement
In his spare time, Farmer John has created a new video-sharing service, which he names MooTube. On MooTube, Farmer John's cows can record, share, and discover many amusing videos. His cows already have posted videos (), conveniently numbered
out how to help his cows find new videos they might like.
FJ wants to create a list of "suggested videos" for every MooTube video. This way, cows will be recommended the videos most relevant to the ones they already watch.
FJ devises a metric of "relevance," which determines, as the name suggests, how relevant two videos are to each other. He picks pairs of videos and manually computes their pairwise relevance. Then, FJ visualizes his videos as a network, where each video is a node and the pairs of videos he manually considered are connected. Conveniently, FJ has picked his pairs so that any video can be reached from any other video along a path of connections in exactly one way. FJ decides that the relevance of any pair of videos should be defined as the minimum relevance of any connection along this path.
Farmer John wants to pick a value so that next to any given MooTube video, all other videos with relevance at least to that video will be suggested. However, FJ is worried that too many videos will be suggested to his cows, which could distract them from milk production! Therefore, he wants to carefully set an appropriate value of . Farmer John would like your help answering a number of questions about the suggested videos for certain values of .
What It's Asking For
There are N items. The relevance of two items, X and Y, have a relevance, R. If the relevance of X and Y is R1, and the relevance of Y and Z is R2, then the relevance of X and Z is the minimum of R1 and R2. The relevance of X and Y is the same as the relevance of Y and X. Given N-1 pre-evaluated relevance values, you are given Q queries. Query i asks for the amount of items at least as relevant as Ri to a item, Ki.
How we Get There
Data Structures / Algorithms
This problem is solved by utilizing a disjoint set. The given information are sorted by descending order of relevance, as so is the queries.
Why?
The disjoint-set data structure is chosen because it implements efficient merging and set checking.
There's a Silver Division version of this problem. That problem is doable with simple DFS searching. However, this question has a bloated amount of queries. This makes it unsuitable for use with DFS directly. A disjoint-set data structure greatly improves runtimes.
How?
This problem is special. For most problems, commands to a data structure are ran on-demand. However, due to the fact that all "merge" commands are in the first half and all "check" commands are in the second half, the "relevance" factor is given to us to masquerade the priority of the command. We read all the commands, merging and checking, and then sort them in descending order of relevance. Then, we run the commands. We store the answers in an array for printing out, for the check commands are not in the order given by input.
Code?
/*
Dear Mr.Li,
Upon hearing what you have said today, I have written code to
implement MooTube. However, given your idea, the calculation of the
first query (first as in first in relevance - largest in relevance)
would result in "calculation flooding" - the act of causing the current
state of the Union-Find Data Structure to also be used in the next query.
In the next query, since all queries are sorted in descending value of
relevance, the relevance would be less, whereas the merged sets for
higher relevance would be still used for this calculation.
This means that previous calculations, with less limits on
relevance, would be used towards forward calculations, in which there
are more limits on relevance. This is calculation flooding.
I had multiple attempts to stop calculation flooding in the course
of debugging my code.
First, I tried reversing the order of sorting.
This meant that the queries with least relevance were listed and parsed
first. This also meant that the wrong sets of edges would be used, since
there wouldn't be enough edges to support the calculation, as per the
sample test case.
Second, I tried using a new disjoint set for every query, but I
stopped because I figured it would be very slow - beyond O(N^3).
Third, I tried reversing only the query sort order, but this did
not have any sort of effect on the program execution. That is very
odd, what happened?
How do I prevent calculation flooding?
(mootube.in & mootube.out are input/output, mootube.err is debug text)
Thank you very much,
Dandan
*/
#include <algorithm>
#include <fstream>
#include <cstring>
#include <iomanip>
#define MAXN 100005
using namespace std;
ifstream cin("mootube.in");
ofstream cout("mootube.out");
int N, Q;
class DSSet
{
private:
int rt[MAXN];
public:
DSSet()
{
for(int i=0; i<N; i++) rt[i] = -1;
}
int root(int n)
{
if(rt[n] < 0) return n;
return (rt[n] = root(rt[n]));
}
void merge(int m, int n)
{
int rm = root(m), rn = root(n);
if(rm == rn) return;
if(rt[rm] > rt[rn]) swap(rm, rn);
rt[rm] += rt[rn];
rt[rn] = rm;
}
int size(int n)
{
return -rt[root(n)] - 1;
}
};
struct edge
{
int x, y, r;
} elist[MAXN];
bool ecmp(const edge& lhs, const edge& rhs)
{
return lhs.r > rhs.r;
}
struct query
{
int n, r, inp;
} queries[MAXN];
bool qcmp(const query& lhs, const query& rhs)
{
return lhs.r > rhs.r;
}
int answers[MAXN];
int main()
{
cin >> N >> Q;
DSSet Set;
for(int i=0; i<N-1; i++)
{
int x, y, r; cin >> x >> y >> r;
elist[i] = {--x, --y, r};
}
sort(elist, elist + N - 1, ecmp);
for(int i=0; i<Q; i++)
{
int n, r; cin >> r >> n;
queries[i] = {--n, r, i};
}
sort(queries, queries + Q, qcmp);
int curE = 0;
for(int i=0; i<Q; i++)
{
while(curE < N-1 && elist[curE].r >= queries[i].r)
{
Set.merge(elist[curE].x, elist[curE].y);
curE++;
}
answers[queries[i].inp] = Set.size(queries[i].n);
}
for(int i=0; i<Q; i++) cout << answers[i] << endl;
}
Comments
Post a Comment