PATHETIC - Editorial

PROBLEM LINK:

Contest

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 :wink:


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';
  }
}
28 Likes

Nice! I reached observation 3 and got stuck at it :slight_smile:

2 Likes

Product of all primes should be less than 2e18, dammit, cost me a WA :frowning:
Nice question by the setter!

Bite me

7 Likes

+1

I solved using bipartitions on a tree. As always you get a bipartition on a tree. THus I coloured adjacent vertices different and colouring means prime p1, p2 in the editorial. Rest is similar with editorialist.

1 Like

Shit, I was so close like every observation is in my mind except the fourth one :grimacing:

Can you explain ?

I did brute force N^3. And it got AC.
Iterate all N^2 paths and if required multiply its smallest element by its length.
Is this correct ?
https://www.codechef.com/viewsolution/35798436

4 Likes

I just upsolved it now. I used a similar approach, I set the value of node at level “l” as “l*(2l-1)”. (Level of Root = 1) @rohitkv77

Brilliant editorial !

5 Likes

I tried this but got TLE.
Can you check were am I going wrong?
https://www.codechef.com/viewsolution/35809478

I have an alternative solution.
Root the tree. Then multiply the prime number p to every node at depth \frac{p}{2}, \frac{2p}{2}, \frac{3 p}{2}, \dots.
The ideas behind it is: a path of lenght l has at least an upwards path of lenght \frac{l}{2}, and therefore it will meet every prime factor of l, even if l is prime itself.

This way every node of the tree gets a value assigned less then 4 \cdot 10^{10}. And I assume you can make this bound even smaller…

Solution: https://www.codechef.com/viewsolution/35790072

Edit: Nevermind. There are much better solutions out there.

7 Likes

p1=1816798556036292277
p2=1269027849171992910
Allot p1 to all odd depth nodes, p2 to all even depth nodes.
(Logic- generated all prime numbers less than 100, then made two products which are <=2e18)

3 Likes

Imagine having all the ideas, splitting the primes into two buckets and even the bipartite bit, but missing one prime. I was dealing with 24 primes for almost half an hour and had no idea what was going wrong. I googled and found that there are 25 primes and managed to solve it. Note to self: Don’t do list initialization of primes by yourself. Please use a sieve

6 Likes

can anyone plz tell me what is wrong with my submission
logic- devide all the prime to x,y such that x<=2e18 and y<=2e18 than allot x and y alternatively from any node according to hieght ie nodes at the same height will get same values i.e eithe x or y

https://www.codechef.com/viewsolution/35806283

Bhai credit to de :sweat_smile:

1 Like

I thought for this approach but unable to implement…:frowning:

1 Like

Well it has sample time complexity but maybe 1.3-2 times slower because of vectors and stuff like that.
Mine passes in 0.80 secs.

2 Likes

Mine in 0.00 ,but it take a lot of time , for next problem I had no time left :confused:

1 Like