Contest Based on Brain Craft Intra SUST Programming Contest 2023

#	User	Rating
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

#	User	Contrib.
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	141
5	Errichto	139
6	adamant	137
7	AmShZ	135
8	BledDest	132
9	maroonrk	131
10	qwexd	129

Hello, Codeforces!

The flagship contest of SUST is here everyone! There will be 12 problems and the problemset is based on Brain Craft Intra SUST Programming Contest 2023. We cordially invite you to participate in this contest. Also, we encourage you to participate as teams. Please make sure that you read ALL the problems!

The contest will be held on Apr/07/2023 11:05 (Moscow time) and will run for 5 hours.

The setters of this contest are: Alfeh, Kawchar85, Mac_prime, magic_kiri, nh_nayeem, Raiden, ShikariSohan, ShinnirKolaChori, susmoydhar7, Tahseen

Contest link: Contest Based on Brain Craft Intra SUST Programming Contest 2023

UPD: Congratulations to the winners of the round!

Top 5 of all participants:

Place	Participant	Problem solved	=
1	satyam343	10	1274
2	lukameladze1, keta_tsimakuridze, Phantom_Performer	10	1341
3	Adam_GS	10	2116
4	Coder_Nayak, sloppy_coder, Krypto_Ray	7	588
5	MinhazIbnMizan, BrehamPie, Arnob	7	652

Participants who sent the first correct solution to the problems:

Task	Participant	Penalty
A	thisIsMorningstar	01:07
B	short-circuit	00:05
C	lukameladze1, keta_tsimakuridze, Phantom_Performer	00:34
D	MinhazIbnMizan, BrehamPie, Arnob	01:42
E	satyam343	01:12
F	CoronaVirus216753	00:04
G	Coder_Nayak, sloppy_coder, Krypto_Ray	00:06
H	merlin_	00:28
i	CoronaVirus216753	00:24
J	satyam343	00:54
K	JanekKwadrat, _supernalu_	02:25
L	-	-

UPD2:

Solutions

104283A - Yet Another Short Statement
ideas: Kawchar85
prepared: steinum

Solution (steinum)

/* steinum */
#include<bits/stdc++.h>
using namespace std;

string num, num2;
long long dp[2][20][20 * 9];
int casio[2][20][20 * 9], cas = 1;
long long yo(int x,int pos,int sum){
	if(sum < 0) return 0;
	if(pos<0){
		return sum == 0;
	} long long &res=dp[x][pos][sum]; int &cs=casio[x][pos][sum];
	if(~res && (x==0 || cs==cas))return res; cs=cas; res=0;
	for(int i = 0, en = (x ? num[pos]-'0' : 9); i <= en; i++) {
		res += yo(x&&i==en, pos - 1, sum - i);
	} return res;
}

long long get(long long n, long long x){
	if(n == 0) return 0;
	num = to_string(n);
	reverse(num.begin(), num.end());
	if(x > (int)num.size() * 9) return 0;
	cas++; long long ans = yo(1, num.size()-1, x);
	return ans;
}

void dfs(int x, int pos, int sum, long long k) {
	if(sum < 0) return;
	if(pos < 0) return;
	for(int i = 0, en = (x ? num[pos]-'0' : 9); i <= en; i++) {
		long long res = yo(x&&i==en, pos - 1, sum - i);
		if(res >= k) {
			num2 += ('0' + i);
			dfs(x&&i==en, pos - 1, sum - i, k);
			return;
		} else {
			k -= res;
		}
	}
}

long long kth(long long n, long long x, long long k) {
	if(get(n, x) >= k) {
		num2 = "";
		dfs(1, num.size()-1, x, k);
		long long ans = stoll(num2.c_str());
		return ans;
	} else {
		return -1;
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
	memset(dp,-1,sizeof dp);
	int t; cin >> t; while(t--) {
		long long l, r, k, x; cin >> l >> r >> k >> x;
		k += get(l - 1, x);
		long long ans = kth(r, x, k);
		cout << ans << '\n';
	}
	return 0;
}

104283B - Johny English and Group Formation
ideas: Raiden
prepared: Raiden

Solution (Raiden)

/* Raiden */
#include<bits/stdc++.h>
using namespace std;

const int mx = 1e5 + 5;
int cnt[mx];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, ma = 0; cin >> n;
	for(int i = 1; i <= n; i++){
		int x; cin >> x;
		ma = max(ma, ++cnt[x]);
	}
	int x = min(n / 2, n - ma);
	x += n - 2 * x;
	cout << x << '\n';
	return 0;
}

104283C - Johnny English Strikes Again
ideas: Raiden
prepared: Raiden

Solution (Raiden)

/* Raiden */
#include<bits/stdc++.h>
using namespace std;

const int mx = 2e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> g[mx];
int get(int x, int l, int r) {
	return (int)(upper_bound(g[x].begin(), g[x].end(), r) - lower_bound(g[x].begin(), g[x].end(), l));
}
int arr[10 * mx];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		int x; cin >> x;
		arr[i] = x;
		g[x].push_back(i);
	}
	while(q--) {
		int l, r; cin >> l >> r;
		int len = (r - l + 1);
		int a = 0, b = 0;
		for(int it = 0; it <= 30; it++) {
			a = max(a, get(arr[l + rng() % len], l, r));
			if(n - len) {
				int x = 1 + rng() % (n - len);
				if(x >= l) x += len;
				b = max(b, (int) g[arr[x]].size() - get(arr[x], l, r));
			}
		}
		int ans = 0;
		ans += min(len / 2, len - a) + min((n - len) / 2, (n - len) - b);
		ans += (n - 2 * ans);
		cout << ans << '\n';
	}
	return 0;
}

104283D - Search For Beauty
ideas: Kawchar85
prepared: Kawchar85

Solution (Kawchar85)

/* Kawchar85 */
#include <bits/stdc++.h>
using namespace std;

const int mx = 1e5 + 5;
int phi[mx], nod[mx];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(int i = 0; i < mx; i++) phi[i] = i;
	for(int i = 2; i < mx; i++) {
		if(phi[i] == i) {
			phi[i] = i - 1;
			for(int j = i + i; j < mx; j += i) {
				phi[j] = phi[j] / i * (i - 1);
			}
		}
	}
	for(int i = 1; i < mx; i++) {
		for(int j = i; j < mx; j += i) {
			nod[j]++;
		}
	}
	int t; cin >> t; while(t--) {
		int n; cin >> n;
		cout << 1LL * nod[n] * phi[n] << '\n';
	}
	return 0;
}

104283E - Tree query with update
ideas: Alfeh
prepared: Alfeh

Solution (Alfeh)

/* Alfeh */
#include <bits/stdc++.h>
using namespace std;

int n;
struct segtree {
	static const int maxn = 2e5 + 10;
	int tree[maxn << 2] = {0};
	void update(int pos, int v, int node = 1, int l = 1, int r = n) {
		if (r < pos || l > pos) return;
		if (pos == l && pos == r) {
			tree[node] = v;
			return;
		} int mid = l + r >> 1;
		update(pos, v, node << 1, l, mid);
		update(pos, v, node << 1 | 1, mid + 1, r);
		tree[node] = max(tree[node << 1] , tree[node << 1 | 1]);
	}
	int query(int i, int j, int node = 1, int l = 1, int r = n) {
		if (l > r || r < i || l > j) return -1;
		if (i <= l && r <= j) {
			return tree[node];
		} int mid = l + r >> 1;
		return max(query(i, j, node << 1, l, mid) , query(i, j, node << 1 | 1, mid + 1, r));
	}
} sg;

const int mx = 2e5 + 10;
vector<int> g[mx];
int arr[mx], tim, st[mx], en[mx], lvl[mx], sp[21][mx];
void dfs(int u, int p = 0) {
	st[u] = ++tim;
	lvl[u] = lvl[p] + 1;
	sp[0][u] = p;
	for(int i = 1; i <= 20; i++) sp[i][u] = sp[i - 1][sp[i - 1][u]];
	for(int v: g[u]) {
		if(v != p) {
			dfs(v, u);
		}
	}
	en[u] = tim;
}
inline bool is_parent(int a, int b) { return st[a] <= st[b] && en[b] <= en[a]; }
int lca(int a, int b) {
	for(int i = 20; i >= 0; i--) {
		if((1 << i) <= b) a = sp[i][a], b -= (1 << i);
	}
	return a;
}
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t; while(t--) {
		cin >> n;
		for(int i = 1; i <= n; i++) cin >> arr[i];
		for(int i = 1; i < n; i++) {
			int u, v; cin >> u >> v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		dfs(1);
		for(int i = 1; i <= n; i++) sg.update(st[i], arr[i]);
		int q; cin >> q; while(q--) {
			int ty; cin >> ty;
			if(ty == 1) {
				int u, x; cin >> u >> x;
				sg.update(st[u], x);
			} else {
				int u, v; cin >> u >> v;
				if(u == v) {
					cout << sg.query(1, n) << '\n';
				} else if(is_parent(v, u)) {
					u = lca(u, lvl[u] - lvl[v] - 1);
					cout << max(sg.query(1, st[u] - 1), sg.query(en[u] + 1, n)) << '\n';
				} else {
					cout << sg.query(st[v], en[v]) << '\n';
				}
			}
		}
		for(int i = 1; i <= n; i++) g[i].clear();
		tim = 0;
	}
	return 0;
}

104283F - Find GCD
ideas: Kawchar85
prepared: Kawchar85

Solution (Kawchar85)

/* Kawchar85 */
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7, mx = 1e5 + 10;
int f[mx];
int power(int a, int b) {
	int x = 1;
	while (b) {
		if (b & 1) x = 1LL * x * a % mod;
		a = 1LL * a * a % mod;
		b >>= 1;
	} return x;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	f[0] = 1;
	for(int i = 1; i < mx; i++) f[i] = 1LL * f[i - 1] * i % (mod - 1);
	int t; cin >> t; while(t--) {
		int a, b, n; cin >> a >> b >> n;
		cout << power(n, f[min(a, b)]) << '\n';
	}
	return 0;
}

104283G - Another Tree Query
ideas: Alfeh
prepared: Alfeh

Solution (Alfeh)

/* Alfeh */
#include <bits/stdc++.h>
using namespace std;

const int mx = 2e5 + 10;
vector<int> g[mx];
int tim, st[mx], en[mx], lvl[mx], sp[21][mx], par[mx];
int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }
void dfs(int u, int p = 0) {
	st[u] = ++tim;
	lvl[u] = lvl[p] + 1;
	sp[0][u] = p;
	for(int i = 1; i <= 20; i++) sp[i][u] = sp[i - 1][sp[i - 1][u]];
	for(int v: g[u]) {
		if(v != p) {
			dfs(v, u);
		}
	}
	en[u] = tim;
}
inline bool is_parent(int a, int b) { return st[a] <= st[b] && en[b] <= en[a]; }
inline int distance(int a, int b) {
	if(lvl[a] > lvl[b]) swap(a, b);
	if(is_parent(a, b)) {
		return lvl[b] - lvl[a];
	}
	int ans = 0;
	for(int i = 20; i >= 0; i--) {
		if(lvl[sp[i][b]] >= lvl[a]) {
			ans += (1 << i);
			b = sp[i][b];
		}
	}
	for(int i = 20; i >= 0; i--) {
		if(sp[i][a] != sp[i][b]) {
			ans += (2 << i);
			a = sp[i][a];
			b = sp[i][b];
		}
	}
	if(a != b) ans += 2;
	return ans;
}
int lca(int a, int b) {
	for(int i = 20; i >= 0; i--) {
		if((1 << i) <= b) a = sp[i][a], b -= (1 << i);
	}
	return a;
}
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t; while(t--) {
		int n, m; cin >> n >> m;
		vector<pair<int, int>> nodes(n + 1);
		vector<int> diameter(n + 1);
		vector<array<int, 3>> query(m);
		for(auto &[id, u, v]: query) {
			cin >> id >> u;
			if(id == 1) {
				cin >> v;
				g[u].push_back(v);
				g[v].push_back(u);
			}
		}
		dfs(1);
		for(int i = 1; i <= n; i++) {
			par[i] = i;
			nodes[i] = {i, i};
		}
		for(auto &[id, u, v]: query) {
			if(id == 1) {
				u = find(u);
				v = find(v);
				tie(diameter[v], nodes[v]) = max({
					make_pair(diameter[u], nodes[u]),
					make_pair(diameter[v], nodes[v]),
					make_pair(distance(nodes[u].first, nodes[v].first), make_pair(nodes[u].first, nodes[v].first)),
					make_pair(distance(nodes[u].first, nodes[v].second), make_pair(nodes[u].first, nodes[v].second)),
					make_pair(distance(nodes[u].second, nodes[v].second), make_pair(nodes[u].second, nodes[v].second)),
					make_pair(distance(nodes[u].second, nodes[v].first), make_pair(nodes[u].second, nodes[v].first)),
				});
				par[u] = v;
			} else {
				v = find(u);
				int d1 = distance(nodes[v].first, u);
				int d2 = distance(nodes[v].second, u);
				if(d1 > d2) cout << d1 << ' ' << nodes[v].first << '\n';
				else cout << d2 << ' ' << nodes[v].second << '\n';
			}
		}
		for(int i = 1; i <= n; i++) g[i].clear();
		tim = 0;
	}
	return 0;
}

104283H - Sequential Nim
ideas: Kawchar85
prepared: Kawchar85

Solution (Raiden)

/* Raiden */
#include <bits/stdc++.h>
using namespace std;

const int mx = 1e5 + 5;
int a[mx];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	set<int> st;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		if(a[i] > 1) {
			st.insert(i);
		}
	}
	while(q--) {
		int t; cin >> t;
		if(t == 1) {
			int x, y; cin >> x >> y;
			st.erase(x);
			if(y > 1) st.insert(x);
		} else {
			int l, r; cin >> l >> r;
			auto it = st.lower_bound(l);
			if(it == st.end() || *it > r) {
				cout << ((r - l) & 1 ? "Second": "First") << '\n';
			} else {
				cout << ((*it - l) & 1 ? "Second": "First") << '\n';
			}
		}
	}
	return 0;
}

104283I - The Secret Key
ideas: Kawchar85
prepared: Kawchar85

Solution (steinum)

/* steinum */
#include <bits/stdc++.h>
using namespace std;

const int mx = 5e5 + 10;
vector<int> d[mx];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	for(int i = 1; i < mx; i++) {
		for(int j = i; j < mx; j += i) {
			d[j].push_back(i);
		}
	}
	int t; cin >> t; while(t--) {
		int a, b, m1, m2; cin >> a >> b >> m1 >> m2;
		int g = abs(__gcd(a - m1, b - m2));
		if(g == 0) {
			cout << max(a, b) + 1 << '\n';
		} else {
			auto it = upper_bound(d[g].begin(), d[g].end(), max(m1, m2));
			if(it == d[g].end() || a % (*it) != m1 || b % (*it) != m2) {
				cout << -1 << '\n';
			} else {
				cout << *it << '\n';
			}
		}
	}
	return 0;
}

104283J - Magic Balls
ideas: Raiden
prepared: Raiden

Solution (nh_nayeem)

/* nh_nayeem */
#include <bits/stdc++.h>
using namespace std;

const int mx = 1e5 + 5;
int n, m, k;
int c[mx], p[mx], vis[mx];
vector<int> g[mx];
int dfs(int u) {
	vis[u] = 1;
	int ret = c[u];
	for(int v: g[u]) {
		if(!vis[v]) {
			ret += dfs(v);
		}
	}
	return ret;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t; while(t--) {
		cin >> n >> m >> k;
		memset(c, 0, sizeof c);
		for(int i = 1, x; i <= n; i++) {
			cin >> x;
			c[x]++;
			g[i].clear();
		}
		for(int i = 1; i <= n; i++) cin >> p[i];
		for(int i = 1, u, v; i <= m; i++) {
			cin >> u >> v;
			g[v].push_back(u);
		}
		vector<int> a(n);
		iota(a.begin(), a.end(), 1);
		sort(a.begin(), a.end(), [](int i, int j) { return p[i] > p[j]; });
		long long res = 0;
		memset(vis, 0, sizeof vis);
		for(int i: a) {
			if(vis[i]) continue;
			int cnt = dfs(i);
			int x = min(cnt, k);
			k -= x;
			res += 1LL * p[i] * x;
		}
		cout << res << '\n';
	}
	return 0;
}

104283K - Special Lattice Path
ideas: magic_kiri
prepared: steinum

Solution (steinum)

/* steinum */
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<tuple<int, int, int>> a(n);
	for(int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		a[i] = {i, x + y, 0};
	}
	sort(a.begin(), a.end(), [](tuple<int, int, int> &x, tuple<int, int, int> &y) {
		return get<1>(x) < get<1>(y);
	});
	int i = 0, cur = 1, nxt = 2;
	for(auto &[ind, j, ans]: a) {
		while(i < j) i++, tie(cur, nxt) = make_pair(nxt, (2LL * (i + 1) * nxt + 1LL * i * cur) % mod);
		ans = cur;
	}
	sort(a.begin(), a.end());
	for(auto &[ind, j, ans]: a) {
		cout << ans << '\n';
	}
	return 0;
}

104283L - Ultimate Game
ideas: ShinnirKolaChori
prepared: Raiden

Solution (steinum)

/* steinum */
#include <bits/stdc++.h>
using namespace std;

const int mx = 1e6 + 10, mod = 1e9 + 7;
int n, m;
int a[mx], dl[mx], dr[mx];

int power(int a, int b) {
	int r = 1; while(b) {
		if(b & 1) r = 1LL * r * a % mod;
		a = 1LL * a * a % mod;
		b >>= 1;
	}
	return r;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++) cin >> a[i];
	sort(a + 1, a + 1 + m);
	for(int i = 1, x[2] = {}; i <= m; i++) {
		int g = a[i] - 1 - a[i - 1];
		x[i & 1] ^= g;
		dl[i] = x[i & 1];
	}
	a[m + 1] = n;
	for(int i = 1, x[2] = {}, j = m; i <= m; i++, j--) {
		int g = a[j + 1] - 1 - a[j];
		x[i & 1] ^= g;
		dr[j] = x[i & 1];
	}
	int total = 0, win = 0;
	for(int i = 0, j = 1; i < n; i++) {
		while(a[j] <= i) j++;
		total++;
		int x = 0;
		if(1 <= j - 1 && j - 1 <= m) x ^= dl[j - 1];
		if(1 <= j && j <= m) x ^= dr[j];
		win += !!x;
	}
	cout << 1LL * win * power(total, mod - 2) % mod << '\n';
	return 0;
}

Comments (57)

Show archived | Write comment?

delwar_03_

3 years ago, hide # |

+10

Supper Excited

→ Reply

NAF15

Thanks for the contest(:

Raiden

+28

There are some very interesting problems. I'd suggest everyone to read all the problems. Also participating as a team is recommended.

ShinnirKolaChori

+29

The tasks are worth brainstorming I assure! Good luck people!

nh_nayeem

As a setter and tester I can assure you that the problems are quite interesting and you will enjoy it.

Kawchar85

+21

As a setter & tester, the tasks are quite interesting and the statements are clear.

SajidZakaria

As a participant, I will not do this contest again.

ID3

Very Eagerly waiting!

Halawany

I'm excited to participate with my team

ABID_ISRTDU

excited to participate but it will coincide with the iftar time.

steinum

3 years ago, hide # ^ |

who knows! you might packet the set within 4hour! see you at standing :D

CoronaVirus216753

Thanks for contest.

vrintle

← Rev. 3 →

What was the intended time complexity on I ?

My solution had a complexity of

Unable to parse markup [type=CF_MATHJAX]

, where div(N) is count of all the divisors of N = max(A, B). And, still my solution didn't fit into the limit. I changed long long to int and it passed, nice.

Chimpanzee

I think you mean T*div(max(A,B)), where T is number of testcases. My solution using long long initially TLed but passed using fast io.

Yes, thanks. Idk, I had even fast io, still I had hard time getting AC.

Snapper_001

Can you share the solution of tree query problem both E and G

← Rev. 2 →

$$$\mathcal{O}(t\times log(\sigma_{0}(n))$$$

MultiThread

how to prove D?

_Aryan_

approach pls

satyam343

$$$X$$$ should be the divisor of $$$g=\gcd(A-m_1,B-m_2)$$$. You can check all divisors of $$$g$$$. You need to be careful when $$$A=m_1$$$ and $$$B=m_2$$$. In that case, answer is $$$\max(A,B)+1$$$.

did same but was getting WA

In addition to what @satyam343 has said, you have to handle cases when either A or B is equal to its remainder or less than its remainder.

Easier version of G. Also, how to do A? I thought of digit dp + binary search, but number of operations per testcase would be 162*18*10*log(k), which will TL over 1e5 testcases

How to do G , Any hint??

Suppose you have two components, and you know the endpoints of a diameter for both. Suppose [P1, P2] is a diameter of the first component, [Q1, Q2] is a diameter of the second component. After merging these two components, the resulting diameter will have endpoints among [P1, P2, Q1, Q2]. We can check all these distances in logarithmic time using LCA, and update the diameter accordingly

Can you please share your solution. It is difficult for me to understand. by seeing code and what you say , I can interpret the idea behind the solution I will be vey thankful to you.

https://codeforces.me/gym/104283/submission/201124545

we can not see the submissions, you can paste in ideone then i am able to see

Go to common standings, double click on any AC cell in that particular task, you'll be able to see it

they restricted the submission

Rudro25

you have permission to see only the solved problem solution.

those question which i have solved why we see them again :)))))

because you have many things to learn from other's solution :| @Snapper_001

here is Chimpanzee's solution on ideone

Thanks bro for the solution

I see your code , i am getting some idea. Actually you are merging and keep track of diameter end point of these two components and we have our full tree also which give us distance so we can figure out the new diameter end point. Thanks for your solution

instead of binary search you can just walk on dp table. again if you take a smaller number for any position, you can save the state for all test case

How to see others solution? If it is restricted please make it open , it will be very helpful Thanks

afiak there is no option to do that.

Krypto_Ray

How to solve D ?

$$$\sigma_0{(n)}\phi{(n)}$$$

Adam_GS

why

Madboly

9 days passed, when you are going to provide explaination for the problems lmfao

we are not publishing official editorial.

that doesn't make any sense, what about for those who want to upsolve ? i really liked the problems but now i cant solve them now because there's no official/unofficial solution/ideas !

Sunk_Cost

where is YouKn0wWho? surprising to see a Shahjalal University contest without Shahjalal.xD

Saimon08035

Anyone give me B and F solution, please.

B: https://ideone.com/g8xAMe

How to solve D, any hints? I tried to solve J considering strongly connected component of a directed graph. I tried to maximize the prizes of each balls accordingly. what was wrong?

How to solve F? was gettin tle

L2L

Fermat's little theorem follow this link

thnx

_gyrFalcon_

+14

I love whole Problem Set, Can anyone give me some hints for Ques A). Yet Another Short Statement

hint

Can you Please attach Editorial along with Solution...It's tough to get it from code

A_xor_A

In Problem E solution. The Function is_parent() is actually checking if a is anchestor of b, not only direct parent. Correct me if I'm wrong. And I didn't get the u = Lca(u, lvl[u]-lv[v]-1) part.. Please help...Alfeh

Alfeh

Yes, is_parent(a, b) function is actually checking if a is one of the ancestors of b, not only the direct one.

Lca(a,b) function find bth ancestor of node a. Sorry for misguiding function name. Maybe kth_ancestor(a, k) would be a good name.

steinum's blog

Solutions