[Tutorial] 2018 PSUT Coding Marathon

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

If w + m ≤ d or w > d, we print "good luck". Otherwise, we print "see you next semester".

Complexity: O(1).

Solution

#include <bits/stdc++.h>
using namespace std;
int main() {
	int d, w, m;
	cin >> d >> w >> m;
	if (w + m <= d || w > d)
		printf("good luck\n");
	else
		printf("see you next semester\n");
	return 0;
}

B. Two Palindromes

We can always build a palindrome if we have at most one letter with odd frequency. Since both strings are palindromes, all letters have even frequencies, except he middle letter when the length of the string is odd. So the answer is NO only when both strings are of odd length and the middle letters are different.

Complexity: O(|s₁| + |s₂|) for reading, and O(1) to check.

Solution

#include <bits/stdc++.h>
using namespace std;
int main() {
	string a, b;
	cin >> a >> b;
	if (a.size() % 2 == 1 && b.size() % 2 == 1 && a[a.size() / 2] != b[b.size() / 2])
		puts("NO");
	else
		puts("YES");
	return 0;
}

C. Forest (A) — Egg

The number of trees is equal to the number of components in the graph. Initially, the number of components is n. Adding an edge will always decrease the number of components by 1 as the constructed graph doesn't have cycles.

We add an edge at node i if there's a value greater than value_i to its left. So we can solve the problem by reading values and keeping the maximum value updated. We add an edge when currentValue < maxValue and decrease the answer.

Complexity: O(n).

Solution

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	int maxValue = -1;
	int res = n;
	for (int i = 1; i <= n; ++i) {
		int currentValue;
		cin >> currentValue;
		if (currentValue < maxValue)
			--res;
		else
			maxValue = currentValue;
	}
	cout << res << endl;
	return 0;
}

D. Forest (B) — Chicken

If we have multiple trees in the forest, it is clear that the value at the root of the second tree must be greater than all values before it, otherwise it will have a parent.

Also, removing the root of a tree produces zero or more trees, the root of each of these trees must have a value greater than all values before it other than the removed root.

We can build the array as follows:

Let the sizes of the trees be s₁, s₂, ....

Pick the first tree, assign the value s₁ to the root, and give each child v of the root a consecutive range of values of size equal to the subtree at v. Then recursively, a child will be assigned to the maximum value in the given range, and the remaining range will be diveded over its children.

So the first tree is built using values [1, s₁], the second tree using values [s₁ + 1, s₁ + s₂], and so on.

Complexity: O(n).

Solution

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> p, sol, sz;
vector<vector<int> > g;
void build(int u, int l, int r) {
	printf("%d ", r);
	for (auto v : g[u]) {
		build(v, l, l + sz[v] - 1);
		l += sz[v];
	}
}
int main() {
	scanf("%d", &n);
	p.resize(n);
	sz.resize(n);
	g.resize(n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &p[i]);
		--p[i];
		if (p[i] != -1)
			g[p[i]].push_back(i);
	}
	for (int i = n - 1; i >= 0; --i) {
		++sz[i];
		if (p[i] != -1)
			sz[p[i]] += sz[i];
	}
	int l = 1, r = n;
	for (int i = 0; i < n; ++i)
		if (p[i] == -1) {
			build(i, l, l + sz[i] - 1);
			l += sz[i];
		}
	return 0;
}

E. Forest (C)

To increase the number of trees, some nodes must become roots. Roots don't have parents, so the values of these roots must be greater than all values to their left.

Can we make node i a root by removing at most one element before it? If v_i is greater than all values before it, we don't need to remove any element as i is already a root. Otherwise, we can make i a root if and only if it has only one value greater than it before i. Removing that value will leave i without a parent.

So we need the maximum value and the second maximum value before an element to decide if we can make it a root or not. And in case we can, we also need the indices of these maximums to know which element should be removed.

We can count for each index j the value f_j, the number of indices that need j to be removed to become a root. We also decrease f_j by one if j is a root, as we will lose one root by removing j.

For each starting element of a subarray i, we increment the end of the subarray j while updating the array f. As values in f are initially 0 or -1, then only increase, it is easy to keep the maximum value in f while increasing some elements.

Complexity: O(n²).

Solution

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	scanf("%d", &n);
	vector<int> v(n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &v[i]);
	long long res = 0;
	for (int i = 0; i < n; ++i) {
		vector<int> can(n);
		int mx1 = -1, mx2 = -1;
		int at1, at2;
		int comp = 0, best = 0;
		for (int j = i; j < n; ++j) {
			if (mx1 > v[j]) {
				--comp;
				if (mx2 < v[j]) {
					++can[at1];
					best = max(best, can[at1]);
				}
			}
			else
				can[j] = -1;
			if (mx2 < v[j]) {
				mx2 = v[j];
				at2 = j;
				if (mx1 < mx2) {
					swap(mx1, mx2);
					swap(at1, at2);
				}
			}
			++comp;
			res += comp + best;
		}
	}
	printf("%lld\n", res);
	return 0;
}

F. World Mug (A)

We can simulate the process recursively or using two vectors and swapping them. The first vector will represent the strengths of the teams in the current round, and the second vector will represent the winners of the current round.

Complexity: O(n).

Solution

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	scanf("%d", &n);
	vector<int> a(n), b;
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	long long res = 0;
	while (a.size() != 1) {
		b.clear();
		for (int i = 0; i < a.size(); i += 2) {
			res += abs(a[i] - a[i + 1]);
			b.push_back(max(a[i], a[i + 1]));
		}
		a.swap(b);
	}
	printf("%lld\n", res);
	return 0;
}

G. World Mug (B)

Let k be the height of the tree, that is, 2^k = n.

The winning team of the tournament will face k teams and beat them all, therefore contributing to the answer by k × s_1st.

The second-place team will also face k teams, winning k - 1 times and losing the last one. This will contribute to the answer by (k - 1) × s_2nd - s_2nd for a total of (k - 2) × s_2nd.

Through our previous observation of how much each team's individual strength contributes to the final answer, it is clear now that the first-place team should be assigned to the team with the maximum strength, and the second-place team to the team with the second maximum strength.

The next two teams in 3^rd and 4^th place each will win k - 2 times and lose once. 5^th to 8^th place will win k - 3 times and lose once, and so on. We should keep assigning places in decreasing order of strength for these teams.

Complexity: O(nlogn), as we need to sort the strengths.

Solution

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	scanf("%d", &n);
	vector<int> v(n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &v[i]);
	sort(v.begin(), v.end());
	int k = 0;
	while ((1 << k) < n)
		++k;
	long long res = v[n - 1] * (long long)k;
	int teams = 1, win = k - 1;
	int i = n - 2;
	while (i >= 0) {
		int count = teams;
		while (count--) {
			res += v[i] * (long long)(win-1);
			--i;
		}
		teams *= 2;
		--win;
	}
	printf("%lld\n", res);
	return 0;
}

H. Cylindrical Graphs

Note that in a cylinder, the degree of each node is 3. If we choose one of the vertical edges, mark one end in blue and the other in red, then do a multi-source BFS marking each adjacent node with the color if its parent, we will get one cycle colored in blue and the other colored in red! Check the following animated GIF:

Since we don't know if an edge is vertical or not, we can try all of the three edges of a node, if one of them produced two cycles of size $\text{[math]}$ , and those two cycles are connected using vertical edges, then we found a solution. Note that sometimes you need to reverse one of the cycles to align the vertical edges.

Complexity: O(n).

Solution

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	vector<vector<int> > g;
	scanf("%d", &n);
	g.resize(n);
	for (int u, v, i = 0; i < 3 * n / 2; ++i) {
		scanf("%d%d", &u, &v);
		--u; --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 0; i < n; ++i)
		if (g[i].size() != 3) {
			printf("NO\n");
			return 0;
		}
	for (int i = 0; i < 3; ++i) { // try all edges of node 0
		int u = 0, v = g[0][i];
		deque<int> cycle[2];
		queue<int> q;
		q.push(u);	q.push(v);
		vector<int> color(n, -1);
		color[u] = 0;	color[v] = 1;
		while (!q.empty()) {
			int w = q.front();
			q.pop();
			if (cycle[color[w]].size() % 2 == 0)
				cycle[color[w]].push_back(w);
			else
				cycle[color[w]].push_front(w);
			for (auto z : g[w])
				if (color[z] == -1) {
					color[z] = color[w];
					q.push(z);
				}
		}
		if (cycle[0].size() != n / 2 || cycle[1].size() != n / 2)
			continue;
		// check that the last two added nodes in each cycle are adjacent
		bool bad = false;
		for (int it = 0; it < 2; ++it) {
			int a = cycle[it].front();
			int b = cycle[it].back();
			if (find(g[a].begin(), g[a].end(), b) == g[a].end()) {
				bad = true;
				break;
			}
		}
		if (bad)
			continue;
		// rotate cycles until u and v are the first in each cycle
		for (int it = 0; it < 2; ++it) {
			while (cycle[it].front() != u) {
				cycle[it].push_back(cycle[it].front());
				cycle[it].pop_front();
			}
			swap(u, v);
		}
		bool ok = false;
		for (int it = 0; it < 2; ++it) { // check vertical edges and reverse one cycle if needed
			ok = true;
			for (int i = 0; i < n / 2; ++i) {
				int a = cycle[0][i];
				int b = cycle[1][i];
				if (find(g[a].begin(), g[a].end(), b) == g[a].end()) {
					ok = false;
					break;
				}
			}
			if (ok || it == 1)
				break;
			cycle[1].pop_front();
			reverse(cycle[1].begin(), cycle[1].end());
			cycle[1].push_front(v);
		}
		if (!ok)
			continue;
		printf("YES\n");
		for (int it = 0; it < 2; ++it) {
			for (int i = 0; i < n / 2; ++i)
				printf("%d ", cycle[it][i] + 1);
			printf("\n");
		}
		return 0;
	}
	printf("NO\n");
	return 0;
}

I. Tree Generators

The main idea is to build a weighted tree that contains only the nodes mentioned in the operations and/or the queries, plus few other nodes that can be the result of the LCA of some pairs.

We will keep a sorted list of the IDs that will be needed in the operations and the queries.

Each time we activate a generator, we know the number of nodes and the range of IDs that will be generated, if we number the required nodes of each generator in DFS order and sort them, then during our LCA operations we may need those nodes or the LCA of some consecutive nodes. So we add all these nodes to a weighted tree, where the weight of an edge is the number of edges between the two nodes. To find the weight of an edge, we can initially build a sparse table for each generator and store the depths of the nodes. We need the sparse tables for finding the LCAs too.

Finally, we build a sparse table for the weighted tree to answer the queries.

The total number of nodes in the weighted tree won't exceed 2 * (k + q). Multiplied by 2 because we add the LCA of consecutive nodes in DFS order.

Complexity: O(TlogT + NlogN), where T = 2 * (k + q) and N is the total number of nodes in all generators.

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k, q;
ll cur, sz;
char s[200001];
set<pair<int, int> > nodes;
map<ll, int> mp;
struct Tree {
	vector<vector<int> > g, dp;
	vector<vector<int> > w;
	vector<int> s, e, d;
	vector<ll> D;
	int dfs;
	void DFS(int u) {
		s[u] = ++dfs;
		for (int v, i = 0; i < g[u].size(); ++i) {
			v = g[u][i];
			d[v] = d[u] + 1;
			if (!w.empty())
				D[v] = D[u] + w[u][i];
			dp[0][v] = u;
			DFS(v);
		}
		e[u] = dfs;
	}
	void buildSparseTable() {
		s.resize(g.size());
		e.resize(g.size());
		d.resize(g.size());
		if (!w.empty())
			D.resize(g.size());
		dfs = 0;
		int l = 0;
		while ((1 << l) <= g.size())
			++l;
		dp.resize(l, vector<int>(g.size(), -1));
		DFS(0);
		for (int k = 1; k < l; ++k)
			for (int u = 0; u < g.size(); ++u)
				if (dp[k - 1][u] != -1)
					dp[k][u] = dp[k - 1][dp[k - 1][u]];
	}
	void build(char *str) {
		int cur = 0;
		stack<int> S;
		S.push(0);
		g.resize(1);
		for (int i = 0; str[i]; ++i)
			if (str[i] == '(') {
				g[S.top()].push_back(g.size());
				S.push(g.size());
				g.push_back(vector<int>());
			}
			else
				S.pop();
		buildSparseTable();
	}
	int LCA(int u, int v) {
		if (d[u] < d[v])
			swap(u, v);
		int l = 0;
		while ((1 << l) <= d[u])
			++l;
		--l;
		for (int i = l; i >= 0; --i)
			if (d[u] - (1 << i) >= d[v])
				u = dp[i][u];
		if (u == v)
			return u;
		for (int i = l; i >= 0; --i)
			if (dp[i][u] != dp[i][v]) {
				u = dp[i][u];
				v = dp[i][v];
			}
		return dp[0][u];
	}
	void addEdges(int u);
};
Tree G;
void Tree::addEdges(int u) {
	if (u && mp[sz + u] == 0) {
		mp[sz + u] = G.g.size();
		G.g.push_back(vector<int>());
		G.w.push_back(vector<int>());
	}
	auto it = nodes.lower_bound(make_pair(s[u], -1));
	if (it != nodes.end() && it->second == u)
		++it;
	while (it != nodes.end() && it->first <= e[u]) {
		addEdges(it->second);
		G.g[mp[u == 0 ? cur : sz + u]].push_back(mp[sz + it->second]);
		G.w[mp[u == 0 ? cur : sz + u]].push_back(d[it->second] - d[u]);
		it = nodes.erase(it);
	}
}
int main()
{
	scanf("%d%d%d", &n, &k, &q);
	vector<Tree> t(n);
	for (int i = 0; i < n; ++i) {
		scanf("%s", s);
		t[i].build(s);
	}
	vector<ll> seen;
	vector<pair<char, ll> > op(k);
	vector<pair<ll, ll> > queries(q);
	for (auto &o : op) {
		scanf(" %c%lld", &o.first, &o.second);
		if (o.first == 's')
			seen.push_back(o.second);
	}
	for (auto &q : queries) {
		scanf("%lld%lld", &q.first, &q.second);
		seen.push_back(q.first);
		seen.push_back(q.second);
	}
	sort(seen.begin(), seen.end());
	seen.resize(unique(seen.begin(), seen.end()) - seen.begin());
	mp[1] = 0;
	cur = 1;
	sz = 1;
	G.g.reserve(200000);
	G.g.resize(1);
	G.w.resize(1);
	for (auto &o : op) {
		if (o.first == 's')
			cur = o.second;
		else {
			Tree &tree = t[o.second - 1];
			ll l = sz + 1;
			ll r = sz + tree.g.size() - 1;
			vector<pair<int, int> > curNodes;
			for (int i = lower_bound(seen.begin(), seen.end(), l) - seen.begin();
				i < seen.size() && seen[i] <= r; ++i) {
				int u = seen[i] - sz;
				curNodes.push_back(make_pair(tree.s[u], u));
			}
			nodes.clear();
			sort(curNodes.begin(), curNodes.end());
			for (int i = 0; i < curNodes.size(); ++i) {
				nodes.insert(curNodes[i]);
				if (i + 1 == curNodes.size())
					break;
				int u = curNodes[i].second;
				int v = curNodes[i + 1].second;
				int lca = tree.LCA(u, v);
				nodes.insert(make_pair(tree.s[lca], lca));
			}
			tree.addEdges(0);
			sz += tree.g.size() - 1;
		}
	}
	G.buildSparseTable();
	for (auto &q : queries) {
		int u = mp[q.first];
		int v = mp[q.second];
		int lca = G.LCA(u, v);
		printf("%lld\n", G.D[u] + G.D[v] - 2 * G.D[lca]);
	}
	return 0;
}

J. Complete the Square

Drawing a side of a square that already has 3 drawn sides will get us one point and allow us to draw another edge.

Count for each square the number of missing sides, put all squares with 1 missing side in a queue and process them one by one by filling the missing side, increasing the answer by 1, and decreasing the number of missing sides of the adjacent square by 1. If the adjacent square now has one missing side, add it to the queue.

Be careful with your implementation. It is possible for an edge to complete two squares at the same moment. If the other square is already in the queue, you should not process it or increase the answer by 1.

Complexity: O(R × C).

Solution

#include <bits/stdc++.h>
using namespace std;
int R, C;
char g[2001][2001];
int in[2001][2001];
const int dr[4] = { -1,1,0,0 };
const int dc[4] = { 0,0,-1,1 };
int main()
{
	scanf("%d%d", &R, &C);
	queue<pair<int, int> > q;
	for (int i = 0; i < 2 * R - 1; ++i)
		scanf("%s", g[i]);
	for (int i = 1; i < 2 * R - 1; i += 2)
		for (int j = 1; j < 2 * C - 1; j += 2) {
			in[i][j] = 4;
			for (int d = 0; d < 4; ++d) {
				int r = i + dr[d];
				int c = j + dc[d];
				if (g[r][c] == '.')
					--in[i][j];
			}
			if (in[i][j] == 3)
				q.push(make_pair(i, j));
		}
	int res = 0;
	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();
		if (in[r][c] == 4)
			continue;
		in[r][c] = 4;
		++res;
		for (int d = 0; d < 4; ++d) { // find the missing side
			int nr = r + dr[d];
			int nc = c + dc[d];
			if (g[nr][nc] == '.') {
				g[nr][nc] = d < 2 ? '-' : '|';
				nr = r + 2 * dr[d];
				nc = c + 2 * dc[d];
				if (nr >= 0 && nr < 2 * R - 1 && nc >= 0 && nc < 2 * C - 1) {
					++in[nr][nc];
					if (in[nr][nc] == 4)
						++res;
					else if (in[nr][nc] == 3)
						q.push(make_pair(nr, nc));
				}
				break;
			}
		}
	}
	printf("%d\n", res);
	return 0;
}

Comments (8)

Write comment?

_bacali

6 years ago, # |

Whats wrong with test 12 in problem I. Tree Generators ??

→ Reply

Hasan0540

6 years ago, # ^ |

← Rev. 2 →

I think you are building the actual tree, which may contain up to 10¹⁰ nodes. So you are getting Runtime error because the number of nodes exceeds 10⁶.

I think that this phrase says that the maximum number of nodes is 10⁵ or not ?? Total number of characters over all generators will not exceed 2 × $10^5$.

That's the total number of nodes in the generators. But you can activate the same generator multiple times.

Test #12 has one generator of length 2 × 10⁵, and we activate this generator around 10⁵ times.

Ah it's ok thank you :D

C137

What is test 148 in problem H???

Answer is NO.

Some consecutive nodes in your cycles are not connected.

Such a stupid mistake, I can't believe it i got WA on test 148 :(

very strong tests, and very interesting problems, thanks lot enjoyed doing it :D

Hasan0540's blog