Blog entries - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Polyn0mial's blog

What's your major in university?

By Polyn0mial, history, 2 years ago, In English

I have many friends doing competitive programming but did not study computer science related subjects in college, and I'm interested that what subjects do competitive programmer study in college? And what's your preferences? Feel free to discuss!

A Quick Survey

Full text and comments »

Polyn0mial
2 years ago
2

Getting Runtime Error in SPOJ K-th Number (MKTHNUM) with Wavelet Tree

By Polyn0mial, history, 2 years ago, In English

I've been trying to solve this problem with wavelet tree, and optimize by discrete the values from $$$[-10^9, 10^9]$$$ to $$$[0, N - 1]$$$. I keep getting runtime error.

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

struct splitmix64_hash {
	static unsigned long long splitmix64(unsigned long long x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	unsigned long long operator()(unsigned long long x) const {
		static const unsigned long long FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

template<class T, class U, class H = splitmix64_hash> using hash_map = gp_hash_table<T, U, H>;
template<class T, class H = splitmix64_hash> using hash_set = hash_map<T, null_type, H>;

template<class T>
class wavelet {
public:
	wavelet(T* from, T* to, T L, T R) : low(L), high(R) {
		if(low == high || from >= to) {
			return;
		}
		T mid = low + (high - low) / 2;
		auto f = [mid](T x) {
			return x <= mid;
		};
		a.reserve(to - from + 1);
		a.push_back(0);
		for(auto it = from; it != to; ++it) {
			a.push_back(a.back() + f(*it));
		}
		auto p = stable_partition(from, to, f);
		l = new wavelet(from, p, low, mid);
		r = new wavelet(p, to, mid + 1, high);
	}

	// return kth smallest element in [L, R]
	T kth(int L, int R, int k) {
		if(L > R) {
			return 0;
		}
		if(low == high) {
			return low;
		}
		int lb = a[L - 1];
		int rb = a[R];
		int lhs = rb - lb;
		if(k <= lhs) {
			return l->kth(lb + 1, rb, k);
		}
		return r->kth(L - lb, R - rb, k - lhs);
	}

	// return number of elements in [L, R] <= k
	int leq(int L, int R, T k) {
		if(L > R || k < low) {
			return 0;
		}
		if(high <= k) {
			return R - L + 1;
		}
		int lb = a[L - 1];
		int rb = a[R];
		return l->leq(lb + 1, rb, k) + r->leq(l - lb, r - rb, k);
	}

	// return number of elements in [L, R] == k
	int count(int L, int R, T k) {
		if(L > R || k < low || k > high) {
			return 0;
		}
		if(low == high) {
			return R - L + 1;
		}
		int lb = a[L - 1];
		int rb = a[R];
		T mid = low + (high - low) / 2;
		if(k <= mid) {
			return l->count(lb + 1, rb, k);
		}
		return r->count(L - lb, R - rb, k);
	}

	~wavelet() {
		delete l;
		delete r;
	}

private:
	T low, high;
	wavelet* l;
	wavelet* r;
	vector<T> a;
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	int* a = new int[n];
	vector<int> xs(n);
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
		xs[i] = a[i];
	}
	sort(xs.begin(), xs.end());
	hash_map<int, int> mp;
	for(int i = 0; i < n; ++i) {
		int id = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin();
		mp[id] = a[i];
		a[i] = id;
	}
	wavelet<int> T(a, a + n, 0, n - 1);
	while(q--) {
		int l, r, k;
		cin >> l >> r >> k;
		cout << mp[T.kth(l, r, k)] << "\n";
	}
	return 0;
}

Full text and comments »

Polyn0mial
2 years ago
0

Need help in construting flow graph

By Polyn0mial, 2 years ago, In English

I'm solving ABC 259 pG.

Here's the article that I found.

I can understand "The project selection problem" part, but doesn't know how to modify it. To be clear, if $$$task_i$$$ is dependent on $$$task_j$$$, we simply add an edge from $$$i$$$ to $$$j$$$ with $$$\infty$$$ weight. What if we want a penalty when both $$$i$$$ and $$$j$$$ are chosen? How do we reconstruct the edges? (Actually from the code of leaderboard it seems like we add an edge from $$$i$$$ to $$$j$$$ with $$$penalty$$$ weight, but why? Adding an edge with $$$\infty$$$ weight means we can't cut the edge there, but what if the weight isn't $$$\infty$$$? What does it mean when the cut is in the middle?)

Also, are there more resources that I can read for constructing flows? I've googled it and most of them were talking about flow algorithms instead of flow constructions.

Full text and comments »

maxflow, constructive algorithms

Polyn0mial
2 years ago
2

How to optimize my code (CSES Hamiltonian Flights)

By Polyn0mial, history, 2 years ago, In English

Link to the problem I use bottom up DP, where $$$dp[\text{mask of visited vertices}][\text{ending vertex}]$$$. I'm pretty sure my time complexity is $$$O(N \cdot 2^N + 2^N \cdot N^2)$$$ however it gives TLE. Are there any way to optimize my code, and what's the reason for TLE (probably big constant factor?)

My code

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

const int M = 1e9 + 7;

const int N = 20;

int dp[1 << N][N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<tuple<int, int, int>> edges(m);
	for(int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		edges[i] = {u, v, (1 << u) | (1 << v)};
	}
	vector<pair<int, int>> masks;
	for(int i = 0; i < (1 << n); ++i) {
		int j = __builtin_popcount(i);
		if(j >= 2) {
			masks.emplace_back(j, i);
		}
	}
	sort(masks.begin(), masks.end());
	dp[1][0] = 1;
	for(int id = 0; id < (int) masks.size(); ++id) {
		int mask = masks[id].second;
		for(auto& [u, v, c] : edges) {
			if((mask & c) == c) {
				dp[mask][v] = (dp[mask][v] + dp[mask ^ (1 << v)][u]) % M;
			}
		}
	}
	cout << dp[(1 << n) - 1][n - 1] << "\n";
	return 0;
}

Full text and comments »

dp, #hamiltonian-path, graph

Polyn0mial
2 years ago
10

Gaussian elimination with restricted solution

By Polyn0mial, 3 years ago, In English

I was solving this problem.

My idea is to map bits into linear equations.

Try all possible number of bits set to 1 in the final array (0~30 in this problem).

Take sample input 1 as an example.

Let's say we want $$$(S = 2)$$$ bits set to 1, here's the linear equations:

$$$(1 - A) + (1 - B) + (1 - C) = 2$$$

$$$A + (1 - B) + C = 2$$$

Do some simplifications,

$$$(-1) * A + (-1) * B + (-1) * C = -1$$$

$$$1 * A + (-1) * B + 1 * C = 1$$$

One possible solution for $$$(A, B, C)$$$ is $$$(0, 0, 1)$$$ = $$$1(001)_2$$$.

However gaussian elimination doesn't ensure the solution having integer solution (and also =0 or =1 in this problem).

When there're infinite solutions, is there a way to check if there exist a solution $$$(x_0, x_1, \dots, x_{30}), x_i = 0$$$ or $$$x_i = 1$$$?

My submission

Full text and comments »

Polyn0mial
3 years ago
0

Problem with SPOJ GCDEX

By Polyn0mial, history, 3 years ago, In English

I was solving this problem. The formula for this problem can be founded here. I've stress tested my code, and found out that this is the smallest test case where my code failed (answer for n <= 225537 are all correct).

Input

Output

Expect

It is obvious that my output is wrong, since $$$answer(n) > answer(n-1)$$$. I have no idea why my code doesn't work.

Code

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

const int N = 1e6 + 5;

bool isprime[N];
vector<int> prime;
int mobius[N];
int phi[N];
int phi_pref[N];

void init() {
	fill(isprime, isprime + N, true);
	isprime[0] = isprime[1] = false;
	mobius[1] = 1;
	phi[1] = 1;
	for(int i = 2; i < N; ++i) {
		if(isprime[i]) {
			prime.push_back(i);
			mobius[i] = -1;
			phi[i] = i - 1;
		}
		for(auto& p : prime) {
			if(p * i >= N) {
				break;
			}
			isprime[p * i] = false;
			mobius[p * i] = mobius[p] * mobius[i];
			phi[p * i] = phi[p] * phi[i];
			if(i % p == 0) {
				mobius[p * i] = 0;
				phi[p * i] = phi[i] * p;
				break;
			}
		}
	}
	for(int i = 1; i < N; ++i) {
		phi_pref[i] = phi_pref[i - 1] + phi[i];
	}
}

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	init();
	int n;
	while(cin >> n && n) {
		long long ans = 0;
		for(int i = 1, j; i <= n; i = j) {
			int p = n / i;
			j = n / p + 1;
			ans += 1LL * p * (p - 1) / 2 * (phi_pref[j - 1] - phi_pref[i - 1]);
		}
		cout << ans << "\n";
	}
	return 0;
}

Full text and comments »

number theory, gcd

Polyn0mial
3 years ago
2

problem with counting coprime pairs in an array

By Polyn0mial, history, 3 years ago, In English

I was reading this article, and saw example 1 (number of coprime pairs in range [1, n]). I tried to solve this problem with similar formula. Here's what I wrote:

$$$\sum_{i=1}^n \sum_{j=1}^n [gcd(a_i, a_j) = 1]$$$

$$$ = \sum_{i=1}^n \sum_{j=1}^n \sum_{d|gcd(a_i, a_j)} \mu{(d)}$$$

$$$ = \sum_{i=1}^n \sum_{j=1}^n \sum_{d=1}^{\infty} [d|a_i][d|a_j]\mu{(d)}$$$

$$$ = \sum_{d=1}^{\infty} \mu{(d)} (\sum_{i=1}^n [d|a_i]) (\sum_{j=1}^n [d|a_j])$$$

$$$ = \sum_{d=1}^{\infty} \mu{(d)} (\sum_{i=1}^n [d|a_i])^2$$$

We can calculate $$$\mu{(d)}$$$ using linear sieve in $$$O(max(a_i))$$$

and $$$\sum_{i=1}^n [d|a_i]$$$ for each $$$d$$$ in $$$O(n * \sqrt{max(a_i)})$$$

But it turns out that when the input is

2
1 2

mu = {1, -1}

cnt = {2, 1}

Gives output of $$$1 * 2^2 + -1 * 1^2 = 3$$$ which is absolutely wrong.

Can anyone point out my mistake? Thanks.

Full text and comments »

Polyn0mial
3 years ago
2

Having trouble with problem related to Mo's algo on tree (SPOJ COT2)

By Polyn0mial, history, 3 years ago, In English

I was solving this Problem Link and encountered a bug. I'm getting WA on test 10, but I run stress test locally on my PC and didn't found any counter test cases. Please take a look on my code.

Approach that I used to solve this problem

Here are my code.

Test Case Generator

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

using ll = long long;

const int N = 100;

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	mt19937_64 rnd(atoi(argv[1]));

	auto next = [&](ll x) {
		return rnd() % x;
	};

	auto randRange = [&](ll a, ll b) {
		return a + rnd() % (b - a + 1);
	};

	int n = randRange(2, N);
	int q = randRange(1, N);

	cout << n << " " << q << "\n";

	for(int i = 0; i < n; ++i)
		cout << randRange(0, 2147483647) << " \n"[i == n - 1];

	vector<int> a(1), b(n - 1);

	iota(b.begin(), b.end(), 1);
	random_shuffle(b.begin(), b.end(), next);

	while(!b.empty()) {
		int u = a[next((int) a.size())];
		int v = b.back();
		if(next(2) == 1)
			swap(u, v);

		cout << u + 1 << " " << v + 1 << "\n";

		a.push_back(b.back());
		b.pop_back();
	}

	for(int i = 0; i < q; ++i)
		cout << randRange(1, n) << " " << randRange(1, n) << "\n";
	
	return 0;
}

Brute force solution

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

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;

	vector<int> a(n);
	for(auto& x : a)
		cin >> x;

	vector<vector<int>> adj(n);
	for(int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	vector<int> parent(n);
	vector<int> depth(n);
	function<void(int, int)> dfs = [&](int u, int p) {
		parent[u] = p;
		depth[u] = (u == 0 ? 0 : depth[p] + 1);
		for(int& v : adj[u]) {
			if(v == p)
				continue;
			dfs(v, u);
		}
	};

	dfs(0, -1);

	while(q--) {
		int u, v;
		cin >> u >> v;
		--u, --v;

		if(depth[u] < depth[v])
			swap(u, v);

		set<int> s;
		s.insert(a[u]);
		s.insert(a[v]);

		while(depth[u] > depth[v]) {
			u = parent[u];
			s.insert(a[u]);
		}

		while(u != v) {
			u = parent[u];
			v = parent[v];
			s.insert(a[u]);
			s.insert(a[v]);
		}

		cout << s.size() << "\n";
	}
	return 0;
}

My submission

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

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;

	vector<int> a(n);
	for(auto& x : a)
		cin >> x;

	vector<int> b(a);
	sort(b.begin(), b.end());
	for(auto& x : a)
		x = lower_bound(b.begin(), b.end(), x) - b.begin();

	vector<vector<int>> adj(n);
	for(int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	vector<vector<int>> dp(n, vector<int>(20));
	vector<int> depth(n);
	vector<int> in(n), out(n);
	vector<int> order;
	order.reserve(n * 2);
	function<void(int, int)> dfs = [&](int u, int p) {
		dp[u][0] = (u == 0 ? 0 : p);
		depth[u] = (u == 0 ? 0 : depth[p] + 1);
		in[u] = (int) order.size();
		order.push_back(u);

		for(int& v : adj[u])
			if(v != p)
				dfs(v, u);

		out[u] = (int) order.size();
		order.push_back(u);
	};

	dfs(0, -1);
	
	for(int x = 1; x < 20; ++x)
		for(int i = 0; i < n; ++i)
			dp[i][x] = dp[dp[i][x - 1]][x - 1];

	auto lift = [&](int u, int step) -> int {
		int r = 0;
		while(step) {
			if(step & 1)
				u = dp[u][r];
			step >>= 1;
			r <<= 1;
		}
		return u;
	};

	auto lca = [&](int x, int y) -> int {
		if(depth[x] < depth[y])
			swap(x, y);

		x = lift(x, depth[x] - depth[y]);

		if(x == y)
			return x;

		for(int i = 19; i >= 0; --i) {
			int new_x = dp[x][i];
			int new_y = dp[y][i];

			if(new_x != new_y) {
				x = new_x;
				y = new_y;
			}
		}

		assert(dp[x][0] == dp[y][0]);
		return dp[x][0];
	};

	vector<tuple<int, int, int, int>> qry(q);
	for(int i = 0; i < q; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;

		if(depth[u] > depth[v])
			swap(u, v);

		int z = lca(u, v);

		if(u == z)
			qry[i] = {in[u], in[v], -1, i};
		else
			qry[i] = {out[u], in[v], z, i};
	}

	const int m = sqrt(n * 2) + 1;
	sort(qry.begin(), qry.end(), [&](const tuple<int, int, int, int>& x, const tuple<int, int, int, int>& y) {
		if(get<0>(x) / m == get<0>(y) / m)
			return (get<0>(x) / m & 1 ? get<1>(x) > get<1>(y) : get<1>(x) < get<1>(y));

		return get<0>(x) < get<0>(y);
	});

	vector<int> occurrence(n);
	vector<int> cnt((int) b.size());
	int counter = 0;

	auto add = [&](int u) {
		++occurrence[u];
		if(occurrence[u] % 2 == 0) {
			--cnt[a[u]];

			if(cnt[a[u]] == 0)
				--counter;
		} else {
			++cnt[a[u]];

			if(cnt[a[u]] == 1)
				++counter;
		}
	};

	auto remove = [&](int u) {
		--occurrence[u];
		if(occurrence[u] % 2 == 0) {
			--cnt[a[u]];

			if(cnt[a[u]] == 0)
				--counter;
		} else {
			++cnt[a[u]];

			if(cnt[a[u]] == 1)
				++counter;
		}
	};

	vector<int> ans(q);
	int l = 0, r = 0;
	add(order[0]);
	for(int i = 0; i < q; ++i) {
		int L, R, z, id;
		tie(L, R, z, id) = qry[i];

		while(l < L) {
			remove(order[l]);
			++l;
		}
		while(l > L) {
			--l;
			add(order[l]);
		}
		while(r < R) {
			++r;
			add(order[r]);
		}
		while(r > R) {
			remove(order[r]);
			--r;
		}

		if(z != -1)
			add(z);

		ans[id] = counter;

		if(z != -1)
			remove(z);
	}
	for(auto& x : ans)
		cout << x << "\n";
	return 0;
}

EDIT: SOLVED. Stupid mistake in binary lifting function.

Full text and comments »

Polyn0mial
3 years ago
4