PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
DFS
PROBLEM:
There’s a tree with N magnets, one at each vertex.
When an external magnet is placed at a vertex, attracts every magnet on the tree one step closer towards it. It is then removed from the tree.
You must place a magnet at each vertex exactly once.
Find an ordering of doing this such that in the end, not every magnet is at the same position.
EXPLANATION:
First, observe that if the tree is a “star”, meaning there’s a single vertex connected to every other vertex, then it’s impossible to achieve what we want.
This is because placing a magnet at the center of the star will accumulate all N magnets there; after which they’ll never be separated again.
Next, suppose that the tree is not a star.
Then, there will exist some edge (x, y) in the tree such that neither x nor y are leaf vertices.
This is easy to prove: take an arbitrary edge of the tree, and if one endpoint is a leaf, look at all neighbors of the other endpoint - at least one of them must be a non-leaf, otherwise the tree would be a star.
Let’s find such an edge (x, y), and delete it from the tree.
We now have two disjoint trees, both containing at least two vertices.
Let them be T_1 and T_2, where T_1 contains x and T_2 contains y.
Perform a DFS on T_1 starting from x, and on T_2 starting from y.
Arrange vertices in order of this DFS, first everything from T_1 and then everything from T_2.
This is a valid order!
Proof
Since x and y are not leaves, there exist vertices u \neq y and v\neq x that are adjacent to x and y, respectively.
Consider what happens when we perform the DFS on T_1, starting from x.
The very first move is on x itself.
After this, the magnet originally on u moves to x, while the one on v moves to y - in particular, they’re adjacent to each other.
For ease of notation, let m_1 be the magnet currently on x, and m_2 be the one on y.
Now, note that when two magnets are on adjacent vertices, the only way to make them end up on the same vertex is to place a magnet on one of these two vertices - nothing else will do it.
Since we operate on T_1 in DFS order, magnet m_1 will always be on a vertex we’ve operated on previously: in particular, we will never operate on the vertex containing m_1.
The same applies to m_2: on every move except the first, m_2 will be on a vertex that was previously operated on - and for the first move, m_2 is on y (which isn’t even in T_1); meaning we also never operate on the vertex containing m_2.
So, while performing operations on T_1, m_1 and m_2 will remain separated.
However, note that the exact same analysis applies to our operations on T_2 as well - at any point of time, m_1 and m_2 will be either outside T_2 entirely, or on some previously-operated vertices; so they will remain separated.
Bonus: Can you implement a checker for this task?
That is, given a tree and a sequence of operations, find out whether all magnets lie on the same vertex in the end or not.
You can test your implementation on DMOJ: YAC7 P4 - Paparazzi.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct ufds{
vector <int> root, sz;
int n;
void init(int nn){
n = nn;
root.resize(n + 1);
sz.resize(n + 1, 1);
for (int i = 1; i <= n; i++) root[i] = i;
}
int find(int x){
if (root[x] == x) return x;
return root[x] = find(root[x]);
}
bool unite(int x, int y){
x = find(x); y = find(y);
if (x == y) return false;
if (sz[y] > sz[x]) swap(x, y);
sz[x] += sz[y];
root[y] = x;
return true;
}
};
void Solve()
{
ufds uf;
int n; cin >> n;
uf.init(n);
assert(n >= 2);
vector <int> sz(n + 1), d(n + 1, 0);
vector<vector<int>> adj(n + 1);
for (int i = 1; i < n; i++){
int u, v; cin >> u >> v;
assert(uf.unite(u, v));
adj[u].push_back(v);
adj[v].push_back(u);
d[u]++;
d[v]++;
}
for (int i = 1; i <= n; i++) if (d[i] == n - 1){
cout << -1 << "\n";
return;
}
// for (int i = 1; i <= n; i++){
// cout << i << " \n"[i == n];
// }
// return;
auto dfs = [&](auto self, int u, int par) -> void{
sz[u] = 1;
for (int v : adj[u]) if (v != par){
self(self, v, u);
sz[u] += sz[v];
}
};
dfs(dfs, 1, -1);
int cent = -1;
for (int i = 1; i <= n; i++){
bool good = true;
int lim = n / 2;
for (int v : adj[i]) if (sz[v] < sz[i]){
good &= sz[v] <= lim;
}
good &= (n - sz[i]) <= lim;
if (good){
cent = i;
break;
}
}
vector<vector<int>> b;
vector<int> c;
auto dfs2 = [&](auto self, int u, int par) -> void{
c.push_back(u);
for (int v : adj[u]) if (v != par){
self(self, v, u);
}
};
for (int v : adj[cent]){
c.clear();
dfs2(dfs2, v, cent);
b.push_back(c);
}
set <pair<int, int>> st;
vector <int> ans;
for (int i = 0; i < b.size(); i++){
st.insert({b[i].size(), i});
}
int last = -1;
for (int i = 0; i < n - 1; i++){
auto id = (--st.end());
if ((*id).second == last){
--id;
}
auto pi = *id;
st.erase(id);
pi.first--;
st.insert(pi);
int j = pi.second;
ans.push_back(b[j].back());
b[j].pop_back();
last = j;
}
for (int i = 0; i < ans.size(); i++){
cout << ans[i] << " ";
if (i == 0) cout << cent << " ";
}
cout << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
vector<ll> adj[N];
struct lca_algo {
// LCA template (for graphs with 1-based indexing)
int LOG = 1;
vector<int> depth;
vector<vector<int>> up;
vector<int> tin, tout;
int timer = 1;
lca_algo() {
}
lca_algo(int n) {
lca_init(n);
}
void lca_init(int n) {
while ((1 << LOG) < n) LOG++;
up = vector<vector<int>>(n + 1, vector<int>(LOG, 1));
depth = vector<int>(n + 1);
tin = vector<int>(n + 1);
tout = vector<int>(n + 1);
lca_dfs(1, -1);
}
void lca_dfs(int node, int par) {
tin[node] = timer++;
trav(child, adj[node]) {
if (child == par) conts;
up[child][0] = node;
rep1(j, LOG - 1) {
up[child][j] = up[up[child][j - 1]][j - 1];
}
depth[child] = depth[node] + 1;
lca_dfs(child, node);
}
tout[node] = timer-1;
}
int lift(int u, int k) {
rep(j, LOG) {
if (k & (1 << j)) {
u = up[u][j];
}
}
return u;
}
int query(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int k = depth[u] - depth[v];
u = lift(u, k);
if (u == v) return u;
rev(j, LOG - 1, 0) {
if (up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
}
u = up[u][0];
return u;
}
int get_dis(int u, int v) {
int lca = query(u, v);
return depth[u] + depth[v] - 2 * depth[lca];
}
bool is_ances(int u, int v){
return tin[u] <= tin[v] and tout[u] >= tout[v];
}
};
pll diam;
void dfs1(ll u, ll p, ll d){
pll px = {d,u};
amax(diam,px);
trav(v,adj[u]){
if(v == p) conts;
dfs1(v,u,d+1);
}
}
vector<ll> curr_path,path;
void dfs2(ll u, ll p, ll des){
curr_path.pb(u);
if(u == des){
path = curr_path;
}
trav(v,adj[u]){
if(v == p) conts;
dfs2(v,u,des);
}
curr_path.pop_back();
}
void solve(int test_case)
{
ll n; cin >> n;
rep1(i,n){
adj[i].clear();
}
rep1(i,n-1){
ll u,v; cin >> u >> v;
adj[u].pb(v), adj[v].pb(u);
}
lca_algo LCA(n);
diam = {-1,-1};
dfs1(1,-1,0);
ll s = diam.ss;
diam = {-1,-1};
dfs1(s,-1,0);
ll t = diam.ss;
dfs2(s,-1,t);
if(sz(path) <= 3){
cout << -1 << endl;
return;
}
vector<bool> active(n+5,1);
ll first_active = 1;
auto f = [&](ll u, ll v){
// next node on the path from u to v
ll lca = LCA.query(u,v);
if(u != lca) return LCA.up[u][0];
return LCA.lift(v,LCA.depth[v]-LCA.depth[u]-1);
};
vector<ll> ans;
ans.pb(path[2]), ans.pb(path[3]), ans.pb(path[1]), ans.pb(path[0]);
trav(x,ans) active[x] = 0;
ll u = path[0], v = path[1];
rep1(i,n-4){
while(!active[first_active]){
first_active++;
}
ll nxt = first_active;
while(!adj[u].empty()){
if(active[adj[u].back()]){
break;
}
else{
adj[u].pop_back();
}
}
while(!adj[v].empty()){
if(active[adj[v].back()]){
break;
}
else{
adj[v].pop_back();
}
}
if(!adj[u].empty()){
nxt = adj[u].back();
}
else if(!adj[v].empty()){
nxt = adj[v].back();
}
ans.pb(nxt);
active[nxt] = 0;
u = f(u,nxt);
v = f(v,nxt);
assert(u != v);
}
trav(x,ans) cout << x << " ";
cout << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector adj(n, vector<int>());
for (int i = 0; i < n-1; ++i) {
int u, v; cin >> u >> v;
adj[u-1].push_back(v-1);
adj[v-1].push_back(u-1);
}
int x = -1, y = -1;
for (int i = 0; i < n; ++i) for (int u : adj[i]) {
if (adj[i].size() == 1) continue;
if (adj[u].size() == 1) continue;
x = i, y = u;
}
if (x == -1) {
cout << -1 << '\n';
continue;
}
auto dfs = [&] (const auto &self, int u, int p) -> void {
cout << u+1 << ' ';
for (int v : adj[u]) if (v != p)
self(self, v, u);
};
dfs(dfs, x, y);
dfs(dfs, y, x);
}
}