Hello everyone,

The problem set of the 2019 PSUT Coding Marathon will be available in Codeforces Gym on Apr/30/2019 18:00 (Moscow time).

You will be given 5 hours to solve 11 problems of difficulty similar to Div.2 contests. The problems are sorted by their estimated difficulty but we recommend reading all problems.

The problems were written by Reem and Hasan0540. Thanks to Jester, Vendetta. and Dark for helping us in preparing some of the problems.

Errichto will be solving the problems in a live stream soon (the time and links will be posted here later). We believe it would be a great learning opportunity to participate in the contest and try all problems and then to watch the stream.

We hope you enjoy the problems and we welcome all feedback!

UPD: Errichto will do the live stream tomorrow, more details here.

UPD: PSUT Coding Marathon 2019 — solving with commentary

Hello everyone!

The problem set of the 2018 ACM Syrian Collegiate Programming Contest will be available in Codeforces Gym on Nov/23/2018 17:00 (Moscow time).

You will have 12 problems and 5 hours to solve them.

The contest was intended for teams, but I believe it is more interesting for yellow and red coders if they participate individually as they will get to try all the problems.

Your solution should read the input from file, and output to the standard output (stdout).

Problem setters are Motarack, Vendetta., Reem, Dark, and Hasan0540.

Thanks to Jester, Hiasat, Noureldin, Badry, sqr_hussain, Mohammad Asaad, and Majd Akleh for the help in preparing and testing the problems.

I hope that you will find some interesting problems for you. Any feedback is appreciated!

Hello everyone,

In 2015, around one month after announcing the beginning of Educational Rounds, me and my friend SaMer prepared this contest inspired by the title "Educational Rounds".

In that contest, we tried to introduce SQRT-decomposition in a set of 5 problems, where each of the first three problems explained one part of the topic and asked to solve a small related task before moving to the next part. The last two problems were general problems that can be solved using SQRT-decomposition.

You may be able to create more interesting problems to present the subject, or make it easier to understand. Having more problems would help too, but I think you got the idea.

What do you think about having similar rounds? A possible format would be to have 3-6 problems explaining a subject, plus two or three problems that can be solved using it (they don't have to be classical).

A. Two Fashillows

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

Complexity: O(1).

#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.

#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).

#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).

#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²).

#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).

#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.

#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 , 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).

#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.

#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).

#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;
}

Hello Everyone!

The problem set of PSUT Coding Marathon 2018, which was held last Saturday, will be available in Codeforces Gym tomorrow, May/16/2018 19:35 (Moscow time).

Previous problem sets:

2017 PSUT Coding Marathon

2016 PSUT Coding Marathon

2015 PSUT Coding Marathon

Contest length is 4 hours, with 10 problems to solve. Difficulty of the contest is similar to Codeforces Div.2 rounds. Contest is more suitable for individual participation.

Problems were prepared by me and linkinu. Thanks to Maram Tuffaha for reviewing the statements and to Vendetta. for preparing the tests of one of the problems.

UPD: Contest starts in less than 15 minutes.

Please note that the memory limit for problem C should be 4 MB according to the problem statement. However, I couldn't set it to 4 MB because Java solutions won't run (initial heap size > 4). The memory limit is there to make you think a little bit more and write less.

UPD1: As Codeforces was down, the contest will start at May/16/2018 19:35 (Moscow time).

Good luck and have fun!

UPD2: Tutorial

Hello again,

Thank you for participating. It was a great experience for me and I learned a lot. Hope you learned something as well! I'll try to avoid the issues some of you complained about, next time.

The tutorial of problems [A-C] was written by Motarack, [D-E] by Dark, and all were reviewed by Reem. Thank you guys!

Solution: https://ideone.com/EEORpR

Hello everyone!

I would like to invite you to participate in Codeforces Round 480 (Div. 2), it will take place tomorrow, May/08/2018 18:05 (Moscow time).

The round consists of 6 problems and you will have two hours to solve them.

The problems were prepared by me with great help from linkinu and Reem. I would like to thank KAN for his great efforts in reviewing the problems and for his suggestions, it is really amazing to see the work done behind every round. Also thanks to Tommyr7, Livace and mike_live for testing the problems, and to arsor for translating the statements into Russian.

This is my first round on Codeforces, I hope that you will find some interesting problems for you.

Note that the round is rated for everyone with rating below 2100.

Good luck and have fun!

UPD: Congratulations to the winners:

Div. 2:

1. phongthan

2. allllekssssa

3. veterfrank

4. lagin

5. Fekete

Div. 1+2:

1. eddy1021

2. phongthan

3. Andreikkaa

4. step_by_step

5. cerberus97

UPD1: Editorial

Hello Everyone,

The problem set of 2017 ACM Jordanian Collegiate Programming Contest will be available in Codeforces Gym on Saturday, Nov/11/2017 18:00.

The problems were prepared by Hasan0540, justHusam, Lvitsa, and Maram Tuffaha. Thanks to ahmed_aly for reviewing the statements and giving some suggestions.

Note that your solution should read the input from file and write to the standard output. You can find the input file name below the title of the problem.

Hope you like the problems. Any feedback is appreciated!

Good luck!

Hello Everyone,

The problem set of the 2017 PSUT Coding Marathon will be available in Codeforces Gym today at 17:00.

You will have 10 problems and 5 hours to solve them (prepared to be an individual contest).

The problem set was prepared by Hasan0540, Vendetta., SaMer, and Maram Tuffaha.

UPD: Please note that the description of part B (and C) of each problem depends on part A.

Good luck!

Hello Everyone,

The problem set of the 2017 Hackatari Codeathon will be available in Codeforces Gym tomorrow, Monday Feb/13/2017 19:00.

You will have 9 problems and 5 hours to solve them. However, the problems' difficulty is similar to Div.2 contests, so you might only need half of that time to solve them.

The problem set was prepared by Hasan0540, linkinu, and Maram Tuffaha.

Thanks to RetiredAmrMahmoud and Pepe.Chess for testing the problem set.

Good luck!

A. Coins

Instead of having one DP table that combines all states for both Hasan and Bahosain, and having too many parameters (and therefore, huge complexity), we can build two tables, one for each person.

Let A[0][i] be the number of ways in which Hasan can pay i dollars using all coins from index 0 to the end, and B[0][i] similar but for Bahosain, then we can compute the final answer by using these two tables as follows:

for (int hasan = 0; hasan <= W; ++hasan) {
   int bahosain = W - hasan;
   if (abs(hasan - bahosain) <= K)
      res += A[0][hasan] * B[0][bahosain];
}

Building each table is a simple DP problem.

Complexity: O((N + M) * W)

B. The Little Match Girl

Instead of trying to move some sticks as the problem suggests, let's count the total number of matchsticks we have and build the maximum possible number of N digits using all these sticks.

We can fill the N digits starting from the left using a simple greedy algorithm. We try to put 9 in the current digit if it is possible to to fill the remaining digits with the remaining sticks, if that's not possible, we try 8, then 7 and so on...

How do we check if it's possible to fill X digits using Y sticks? The digit 1 requires two sticks, so Y should be at least 2X to be able to fill all the digits with at least two sticks. Also, since we can't fill a digit with more than 7 sticks (the digit 8), Y should not exceed 7X, otherwise we will have some unused sticks at the end.

Digit 3 requires one more stick than 1, digit 4 requires two more, digit 5 requires 3 more, and digit 6 requires 4 more. So the conditions Y ≥ 2X and Y ≤ 7X are sufficient as we can use any remaining number of sticks to fill one digit that is not 8.

Complexity: O(10N)

C. Bored Judge

We can simulate what's happening in the scoreboard using a set, as we need the erase method to remove the team from the set, update it's score, and insert it back to the set. After each event, if the team at set.begin() has changed, we update our answer.

I used a set<pair<int,int> >, where the pair.first is the score of the team multiplied by -1 to make the maximum score comes first in the set, and pair.second is the index of the team. This way the team with the maximum score will be at set.begin(), and if there are multiple teams with the same score, the one with the smallest index will come first. You can create a struct or a class with an operator to sort them correctly instead of multiplying by -1, that would be more clean.

To update the score of a team in the set, you need to know it's current score:

set.erase(make_pair(-currentScore[x], x))); // remove
currentScore[x] += y; // update
set.insert(make_pair(-currentScore[x], x))); // insert

Complexity: O(QlogN)

D. Rectangles

E. Ya Rajaie and Books

The answer is ceil(N / 5). To use only integers, you may output (N + 4) / 5.

Complexity: O(1)

F. Exchange

We may iterate over the string from left to right and try to swap the current letter with another one that is smaller in the alphabetical order, if such letter doesn't exist in the string, we move to the next index. Otherwise, we update the string and print it. This solution would fail on this simple case: ab, as it allows the letter b to be swapped with a. To fix this, we should only allow swapping letter A with letter B if the first occurrence of A is before the first occurrence of B and B comes first in the alphabetical order.

We can build an array F where F[c] is the position of the first occurrence of the letter c, or  - 1 if it doesn't exist in the string. Then the solution would be:

for (int i = 0; i < s.length(); ++i) { if (F[s[i]] != i) // this's just to improve the complexity from O(26*N) to O(26*26+N). continue; for(int j = 'a'; j < s[i]; ++j) if (F[j] > F[s[i]]){ // No need to check that F[j] != -1 as -1 isn't greater than F[i]. // exchange the letter s[i] with the letter j, print the string, and exit both loops. } }

Complexity: O(26 * 26 + N)

G. Notes

We will start with the brute force solution and see if it's going to work. Here are some notes:

• We won't need more than 8 notes of the first type (1 JD). If we want to pay 9 JDs, we may use one note of the second type and four notes of the first type (5 + 4 = 9).

• We won't need more than 2 notes of the second type (5 JDs) or the third type (10 JDs).

• We won't need more than 4 notes of the forth type (20 JDs). Do we need four? Yes, when we have -for example- 80 JDs and need to be able to pay 40 and 80.

Now we can have 4 for loops that try all possible answers for the first four types, [0-8] × [0-2] × [0-2] × [0-4], in O(405). We know that the remaining amount of money should be a multiple of 50. This leaves only 9 possible solutions in the worst case (http://ideone.com/QrdG5D).

So now we have a number of notes of each type, we should check if it is possible to pay for every item in the input. We may solve this problem using Dynamic Programming for each of the nine possible solutions.

Complexity: O(9 * (8 + 2 + 2 + 4) * N)

H. Cinema

First, let's increase K by one to include Rami in the required number of empty seats. Then we may check if there's a substring of length K that consists only of zeros as follows:

int count=0;
for (int i = 0; i < C; ++i){
   if (str[i] == '0')
      ++count;
   else
      count = 0;
   if(count == k)
      break;
}
if (count == k)
   printf("yes\n");
else
   printf("no\n");

Complexity: O(C)

I. Simple Robot

Note that the answer for each dimension is not affected by the other one, so we may write one function that solves the 1D version and call it twice. The first time with the left/right instructions and the second time with the up/down instructions.

To solve the problem for one dimension, we may start at 0 and follow the instructions while keeping the min and the max position we reached. We ignore any instruction that will make maxX - minX ≥ N, where N is the size of the dimension.

Another solution is using ternary search as moving away from the optimal position would increase the number of skipped instructions.

Complexity: O(strLength) or O(strLength * (logR + logC))

J. Divisible Numbers

K. Topological Sort

L. Starry Night

Hello Everyone,

The problem set of 2016 ACM Amman Collegiate Programming Contest will be available in Codeforces Gym on Tuesday, Sep/27/2016 10:00.

The problem set was prepared by Hasan0540, SaMer, and AU.Bahosain.

Thanks to RetiredAmrMahmoud for testing one of the problems (in case he participated), and to Dark for helping me preparing the contest on Polygon.

I hope more orange and red coders will participate than in the last contest I've prepared :(

Good luck!

Hello Everyone,

ACM SCPC 2015 (Syrian Collegiate Programming Contest) problem set will be available in Codeforces Gym on Sunday, Sep/11/2016 21:00.

The problem set was prepared by Hasan0540, hyoussef, SaMer, AU.Bahosain, fegla, Nicole Hosh, and Mohammad Asaad.

Thanks to RetiredAmrMahmoud, Amirnasr, eagle93, TahaMahmoud, ghooo, osamahatem, and hossameldeenfci for testing.

Good luck, and I hope you can enjoy the problem set as much as we enjoyed creating it.

Update: The contest was shifted 11 hours (Sunday, Sep/11/2016 21:00) in order for it not to intersect with the Mirror of Bubble Cup Finals.

Hello Competitors,

I would like to invite you all to participate in the follow up of Third Coding Marathon of Princess Sumaya University for Technology. The contest was originally held on April 30, and it will launch in Codeforces Gym tomorrow; May/07/2016 10:00.

The problems were prepared by Hasan0540, SaMer, and Dr. Ibrahim (earlgray).

The contest will be held with extended ACM ICPC rules. You'll be given 14 problems to solve within 270 minutes. Some of the problems have two parts (A and B), where A is easier than B, and the statement of B depends on the statement of A. The difficulty of the contest is similar to Codeforces Div. 2 contests.

Good luck to you, and I hope you can enjoy the problemset.

Note: Don't forget to use fast I/O methods.

A. Who Is The Winner

We can keep the name of the winner team while reading the input, if the current team solved more problems than the current winner, or solved the same number of problems but with less penalty, we set the current team as the winner:

cin >> curTeam >> curSolved >> curPenalty;
if (curSolved > winSolved || curSolved == winSolved && curPenalty < winPenalty){
	winTeam = curTeam;
	winSolved = curSolved;
	winPenalty = curPenalty;
}

Complexity: O(N)

B. Rock-Paper-Scissors

Let's start with the brute force solution, we can try all possible pairs (X, Y), if we know X and Y, then Z = N - X - Y.

The number of times Bahosain wins depends on the number of Scissors in the first X rounds, the number of Rocks in the next Y rounds, and the number of Papers in the last Z rounds.

We can find the number of times he will lose in a similar way.

int res = 0;
for (int X = 0; X <= N; ++X)
	for (int Y = 0; Y <= N; ++Y){
		int winCount = countInRange(0, X - 1, 'S')	 //     Rock > Scissors
			     + countInRange(X, X + Y - 1, 'R')   //    Paper > Rock
			     + countInRange(X + Y, N - 1, 'P');  // Scissors > Paper
		int loseCount = countInRange(0, X - 1, 'P')      //     Rock < Paper
			      + countInRange(X, X + Y - 1, 'S')  //    Paper < Scissors
			      + countInRange(X + Y, N - 1, 'R'); // Scissors < Rock
		if(winCount > loseCount)
			++res;
	}

This solution works in O(N³) if the function countInRange works in O(N), we can improve it using prefix sum (cumulative sum).

Create 3 arrays: rockSum, paperSum, and scissorsSum. We set rockSum[i] = 1 if there is a rock at index i. We fill the other two arrays in a similar way.

After calculating the prefix sums, we can modify countInRange to work in O(1). For example, to find the number of rocks in a range [L, R], we can use rockSum[R] - rockSum[L - 1] (watch out when L > R or L = 0).

Complexity: O(N²)

C. Street Lamps

If we don't have any asterisk *, then for each 3 dots we need one lamp, so the answer is , where D is the number of dots.

We can solve the problem by creating a copy of the given string, and for each asterisk in the first string we place an asterisk at it's adjacent indices in the second string. So if the given string is ...**.., the second one will be ..****..

After that, we count the number of dots in each block of consecutive dots and find the number of needed lamps for that block.

Complexity: O(N)

D. Alternating Strings

This problem can be solved using dynamic programming.

Let dp[i] be the minimum number of partitions needed for the suffix that starts at i, we try all possible cuts [i...j]. A cut is possible if i = j, or the substring S(i...j) is not alternating and j - i + 1 ≤ K.

dp[s.length()] = 0;
for (int i = s.length() - 1; i >= 0; --i){
	bool isAlter = true;
	dp[i] = 1e9;
	for (int j = i; j - i + 1 <= k && j<s.size(); ++j){
		if (j>i && s[j] == s[j - 1])
			isAlter = false;
		if (i == j || isAlter == false)
			dp[i] = min(dp[i], 1 + dp[j + 1]);
	}
}

Finally, the answer will be dp[0] - 1, because dp[0] represents the number of partitions, not cuts.

Complexity: O(NK)

E. Epic Professor

Let M be the maximum mark of a student, then the maximum possible bonus marks will be 100 - M.

We can find the maximum mark in one loop, and then count the number of students such that Mark_student + 100 - M ≥ 50.

Complexity: O(N)

F. Travelling Salesman

We can greedily keep adding the edges with the minimum length to the graph until we have one component, then the answer is the length of the last added edge.

This can be done using disjoint-sets data structure. The number of components in the graph will decrease by 1 after merging two components.

Note that the answer is the same as the maximum length of an edge in a minimum spanning tree.

Complexity: O(MlogM)

G. Heavy Coins

We need to find the maximum size of a subset such that the sum of it's values sum ≥ S and the minimum value in the subset is greater than sum - S.

Since N is small, we can try all possible subsets recursively, or iteratively using a bitmask.

int res = 0;
for (int mask = 1; mask < (1 << n); ++mask){
	int sum = 0, size = 0, minVal = 1e9;
	for (int i = 0; i<n; ++i)
		if((mask>>i)&1){
			sum += val[i];
			++size;
			minVal = min(minVal, val[i]);
		}
	if (sum >= s && minVal > sum - s)
		res = max(res, size);
}

Complexity: iterative solution O(2^NN), recursive solution O(2^N)

H. Bridges

After removing bridges from the graph, we will have one or more components with no bridges.

Imagine each component as one big node, and connect those big nodes using the removed bridges:

The resulting graph is a tree, each edge in this tree is a bridge in the original graph, we need to remove the maximum possible number of bridges by adding one edge.

Adding an edge between two nodes will remove a number of bridges equal to the number of edges on the unique path between them, so we need to remove the longest path in this tree.

The final answer is the number of bridges in the graph minus the longest path in the tree.

Mapping each component into one node can be done using disjoint-sets. It is possible to solve the problem without actually building the tree, check I_love_Tanya_Romanova's comment.

Complexity: O(N + M)

I. Bahosain and Digits

We can try all possible K, we also try all possible digits D, that is we want to make all digits in the string equal to D.

To check if that's possible, we add the needed value to the first digit to make it equal to D (mod10), we should add the same value to the next K - 1 digits, some contestants did this using segment tree and got TLE.

To do this efficiently, we can keep a variable add that represents the total added value, and an array remove to mark that when we are at index i, we should subtract remove[i] from add, please check the code if that wasn't clear:

int add = 0, remove[251] = {};
for (int i = 0; i + k <= digits.length(); ++i){
	add -= remove[i];
	int curDigit = (digits[i] - '0' + add) % 10;
	int need = (10 - curDigit + D) % 10;
	add += need;
	remove[i + k] = need;
}
// after that we need to check that we won't need more
// operations to make the last K digits equal to D.

Complexity: O(10|digits|²)

J. Candy

Let's create two frequency arrays, one for ages and one for packet sizes, after that we can match ages with packet sizes greedily.

We keep matching the minimum age i with the minimum possible packet size j such that freqAge[i] ≤ freqSize[j]. Note that we can't use sizes less than j after that because the problem says that older students must get more candies.

bool yes = true;
for (int age = 5, size = 1; age <= 15; ++age){
	if(freqAge[age] == 0)
		continue;
	while (size <= 50 && freqAge[age]>freqSize[size])
		++size;
	if (size == 51){
		yes = false;
		break;
	}
	++size;
}

Complexity: O(15 + 50)

K. Runtime Error

Many contestants got runtime error in this problem because of dividing by zero.

We can solve the problem in O(N) using an array that tells us if we have some number or not.

bool have[100001] = {};
int X = 1e9, Y;
for (int val, i = 0; i<n; ++i){
	cin >> val;
	if (val>0 && k%val == 0 && have[k / val]){
		int curX = min(val, k / val);
		int curY = k / curX;
		if (curX<X){
			X = curX;
			Y=curY;
		}
	}
	have[val] = true;
}

There are other solutions that use frequency arrays or binary search. Be careful in case K is a square number like 25 and there is one 5.

Complexity: O(N)

L. Alternating Strings II

Let's go back to the solution of problem D, notice that once the substring is not alternating, it won't be alternating again, so we just choose the minimum value in the range [x, i + k - 1], where x is the first position after i such that S(i...x) is not alternating. In other words, S_x - 1 = S_x.

We can use segment tree to get the minimum value of dp in the required range.

Complexity: O(NlogN)

Can anyone explain why does the first code get Runtime Error?

RTE: http://ideone.com/7UNoVJ

OK: http://ideone.com/fOWbj3

Thanks!