USACO 2020 February Contest, Gold Problem 3. Delegation

USACO 2020 February Contest, Gold Problem 3. Delegation

Farmer John's farm consists of NN pastures (2N1052≤N≤105) connected by N1N−1 roads, so that any pasture is reachable from any other pasture. That is, the farm is a tree. But after 28 years of dealing with the tricky algorithmic problems that inevitably arise from trees, FJ has decided that a farm in the shape of a tree is just too complex. He believes that algorithmic problems are simpler on paths.

Thus, his plan is to partition the set of roads into several paths, and delegate responsibility for each path to a worthy farm hand. To avoid contention, he wants each path to be the same length. He wonders for which lengths there exists such a partition.

More precisely, for each 1KN11≤K≤N−1, help Farmer John determine whether the roads can be partitioned into paths of length exactly KK.

 

SCORING:

  • In test cases 2-4 the tree forms a star; at most one vertex has degree greater than two.
  • Test cases 5-8 satisfy N103N≤103.
  • Test cases 9-15 satisfy no additional constraints..

 

INPUT FORMAT (file deleg.in):

The first line contains a single integer NN.The next N1N−1 lines each contain two space-separated integers aa and bb describing an edge between vertices aa and bb. Each of aa and bb is in the range 1N1…N.

 

OUTPUT FORMAT (file deleg.out):

Output a bit string of length N1.N−1. For each 1KN1,1≤K≤N−1, the KKth bit of this string from the left should equal one if it is possible to partition the edges of the tree into paths of length exactly KK and 00 otherwise.

 

SAMPLE INPUT:

13
1 2
2 3
2 4
4 5
2 6
6 7
6 8
8 9
9 10
8 11
11 12
12 13

SAMPLE OUTPUT:

111000000000

It is possible to partition this tree into paths of length KK for K=1,2,3.K=1,2,3. For K=3K=3, a possible set of paths is as follows:

 

1312118,10986,7623,542113−12−11−8,10−9−8−6,7−6−2−3,5−4−2−1

 

Problem credits: Mark Gordon and Dhruv Rohatgi

USACO 2020 February Contest, Gold Problem 3. Delegation 题解(翰林国际教育提供,仅供参考)

题解请注册登录查看

[/hide]

(Analysis by Benjamin Qi)

Root the tree at 11. We will do DP on subtrees.

First, observe that the answer is "no" if N1N−1 is not divisible by K.K. Otherwise, we wish to write a function dfs(x)dfs(x) which will check whether it is possible to partition the subtree corresponding to vertex xx into paths of length KK and possibly an extra one of length less than KK with one endpoint at xx. If possible, this function will return the length of the extra path. Otherwise, the function will return 1−1.

First, we should call dfs(t)dfs(t) for all children tt of x.x. If any of these return 1,−1, then dfs(x)dfs(x) should also return 1.−1. Otherwise, we have a path of length dfs(t)+1dfs(t)+1 with one endpoint at x.x. After doing this, we should pair up as many of the paths whose lengths are in (0,K)(0,K) as possible. If there is more than one unpaired path remaining after this process, return 1−1.

Otherwise, return the length of the unpaired path, or zero if none exists. Note that if dfs(x)1,dfs(x)≠−1, then its return value is equal to the remainder when the number of edges in the subtree corresponding to xx is divided by K,K, which is invariant regardless of how exactly we choose the paths of length KK.

For a fixed K,K, we can check whether it is possible to split the tree into paths of length KK in O(N)O(N) time, allowing us to solve the problem in O(N(# of divisors of N)).O(N⋅(# of divisors of N)). However, several solutions with this complexity ended up receiving TLE on test case 33, where N=83161N=83161 and N1N−1 has 128128 divisors. One option is to deal with the star case separately. Another is to write a checker that does not use recursion and is a constant factor faster, demonstrated below.

 

#include "bits/stdc++.h"

using namespace std;

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

#define f first
#define s second

const int MOD = 1e9+7;
const int MX = 1e5+5;

int N,sub[MX];
vector<int> adj[MX], num[MX];
bool bad = 0;
 
void dfs(int a, int b) {
	sub[a] = 1;
	for(auto& t: adj[a]) if (t != b) {
		dfs(t,a);
		sub[a] += sub[t];
		num[a].push_back(sub[t]);
	}
	if (sub[a] != N) num[a].push_back(N-sub[a]);
}
 
int cur[MX]; // basically unordered map
bool ok(int K) {
	if ((N-1)%K != 0) return 0;
	for (int i = 0; i < K; ++i) cur[i] = 0;
	for (int i = 1; i <= N; ++i) {
		int cnt = 0;
		for (auto& t: num[i]) {
			int z = t%K; if (z == 0) continue;
			if (cur[K-z]) cur[K-z] --, cnt --;
			else cur[z] ++, cnt ++;
		}
		if (cnt) return 0; // paths don't pair up
	}
	return 1;
}
 
int main() {
	setIO("deleg"); 
	cin >> N;
	for (int i = 1; i < N; ++i) {
		int a,b; cin >> a >> b;
		adj[a].push_back(b), adj[b].push_back(a);
	}
	dfs(1,0);
	for (int i = 1; i < N; ++i) {
		if (ok(i)) cout << 1;
		else cout << 0;
	}
	cout << "\n";
}

[/hide]

翰林国际教育资讯二维码