PROBLEM LINK:
Author: Shahjalal Shohag
Tester: Ildar Gainullin
Editorialist: Rajarshi Basu
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Basic Math, Implementation
PROBLEM:
You are given a tree with N \leq 100 nodes (numbered 1 through N). A tree is a connected undirected graph without cycles.
You have to assign an integer to each node; for each valid i, let’s denote the integer assigned to node i by A_i. This assignment must satisfy the following conditions:
- For each valid i, 1 \le A_i \le 2 \cdot 10^{18}.
- For each simple path in the tree, let’s denote the set of nodes in this path by S. Then, the product P = \prod_{v \in S} A_v is divisible by |S|.
There are 200 testcases.
EXPLANATION:
Brief Explanation
- Let all the primes less than 100 be denoted by the set P. Choose A and B such that A \cup B = P and A \cap B = \phi. Let p_A be the product of all primes in A and p_B be product of all primes in B.
- Root the tree at some node, and do a dfs. Set the value of all nodes at even depths to be p_A and set the value of all nodes at odd depths to be p_B.
===================
Observation 1
It seems that the prime factors should be important right? Instead of thinking about numbers, try to think about how to distribute the prime factors of all possible |S| values.
Observation 2
Why is N so small? One possible explanation might be that we are potentially looking for a N^2 or N^3 solution, but another more relevant thing that should jump out is that the number of prime numbers that are less than 100 are indeed very less. 25 to be precise.
Observation 3
What if, we just took the product of all the primes \leq 100 and placed that number in each of the nodes. Then we are obviously done, right?
The only problem is that the product of that will be greater than 2*10^{18}.
Observation 4
So, we can’t just take the product of all the primes. However, what if we could break the product of all primes into two parts p_1 and p_2, such that all primes \leq 100 are present in either p_1 or p_2. Turns out, it is possible to choose such p_1 and p_2 such that p_1,p_2 \leq 2*10^{18}.
How?
We can find p_1,p_2 by a greedy logic. Try to think about it on your own
Observation 5
If every adjacent two cells have p_1 and p_2 written on them, then we are also done. Think on why this is true as well. To reason with how a factor like p^k is dealt with, where p is some prime and k is some power, just notice that in a path of length X where essentially p^k | X, or rather X is some multiple of p^k, we have multiple occurrences of both p_1 and p_2 as well.
Observation 6
A tree is a bipartite graph. So we can just write p_1 on every element of one partite, and p_2 on the elements of the other partite. Essentially for trees, we can identify the partites based on the parity of their depths from any node that we select as the root. For the final algorithm, checkout the Brief Explanation.
SOLUTION:
Setter’s Code
#include<bits/stdc++.h>
using namespace std;
const long long M = 2e18 + 1;
bool is_prime(int n) {
if (n == 1) return false;
for (int i = 2; i < n; i++) {
if (n % i == 0) return false;
}
return true;
}
vector<int> primes(int n) {
vector<int> p;
for (int i = 1; i <= n; i++) {
if (is_prime(i)) {
p.push_back(i);
}
}
return p;
}
vector<int> g[105];
int dep[105];
void dfs(int u, int p = 0) {
dep[u] = dep[p] + 1;
for (auto v: g[u]) if (v ^ p) dfs(v, u);
}
struct DSU {
vector<int> par, rnk, sz; int c;
DSU(int n) : par(n + 1), rnk(n + 1,0), sz(n + 1,1), c(n) {
for (int i = 1; i <= n; ++i) par[i] = i;
}
int find(int i) { return (par[i] == i ? i : (par[i] = find(par[i]))); }
bool same(int i, int j) { return find(i) == find(j); }
int get_size(int i) { return sz[find(i)]; }
int count() { return c; } //connected components
int merge(int i, int j) {
if ((i = find(i)) == (j = find(j))) return -1; else --c;
if (rnk[i] > rnk[j]) swap(i, j);
par[i] = j; sz[j] += sz[i];
if (rnk[i] == rnk[j]) rnk[j]++;
return j;
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
auto p = primes(100);
vector<long long> v;
for (auto x: p) v.push_back(x);
while (1) {
sort(v.begin(), v.end());
int i = v.size() - 1;
while (i && v[0] >= M / v[i]) i--;
if (i <= 0) break;
auto x = v[0];
auto y = v[i];
v.erase(v.begin() + i);
v.erase(v.begin());
v.push_back(x * y);
}
int t; cin >> t;
assert(1 <= t && t <= 200);
while (t--) {
int n; cin >> n;
assert(1 <= n && n <= 100);
DSU d(n);
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
assert(1 <= min(u, v) && max(u, v) <= n);
d.merge(u, v);
g[u].push_back(v);
g[v].push_back(u);
}
assert(d.count() == 1);
dfs(1);
for (int i = 1; i <= n; i++) {
cout << v[dep[i] & 1] << ' ';
}
cout << '\n';
for (int i = 1; i <= n; i++) g[i].clear();
}
return 0;
}
Tester’s Code
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n = 100;
cin >> n;
vector <int> arr;
for (int i = 2; i <= n; i++) {
bool prime = true;
for (int j = 2; j < i; j++) {
if (i % j == 0) {
prime = false;
}
}
if (prime) {
arr.push_back(i);
}
}
ll l = 1, r = 1;
multiset <ll> z;
for (int x : arr) z.insert(x);
ll lim = 2e18;
while (z.size() > 2) {
ll a = *z.begin();
z.erase(z.begin());
auto it = z.upper_bound(lim / a);
it--;
ll b = *it;
z.erase(it);
z.insert(a * b);
}
while (z.size() < 2) z.insert(1);
vector <vector <int> > g(n);
vector <int> d(n, -1);
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
d[0] = 0;
vector <int> q = {0};
for (int i = 0; i < (int) q.size(); i++) {
int v = q[i];
for (int j : g[v]) {
if (d[j] == -1) {
d[j] = d[v] + 1;
q.push_back(j);
}
}
}
for (int i = 0; i < n; i++) {
if (d[i] % 2 == 0) cout << *z.begin() << ' ';
else cout << *z.rbegin() << ' ';
}
cout << '\n';
}
}
