710A - King Moves

Easy to see that there are only three cases in this problem. If the king is in the corner of the board the answer is 3. If the king is on the border of the board but not in a corner then the answer is 5. Otherwise the answer is 8.

char c, d;

bool read() {
	return !!(cin >> c >> d);
}

void solve() {
	int cnt = 0;
	if (c == 'a' || c == 'h') cnt++;
	if (d == '1' || d == '8') cnt++;
	if (cnt == 0) puts("8");
	else if (cnt == 1) puts("5");
	else if (cnt == 2) puts("3");
	else throw;
}

Complexity: O(1).

710B - Optimal Point on a Line

The function of the total distance is monotonic between any pair of adjacent points from the input, so the answer is always in some of the given points. We can use that observation to solve the problem by calculating the total distance for each point from the input and finding the optimal point.

The other solution uses the observation that the answer is always is the middle point (by index) in the sorted list of the given points. The last fact is also can be easily proven.

const int N = 300300;

int n, a[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n) assert(scanf("%d", &a[i]) == 1);
	return true;
}

void solve() {
	sort(a, a + n);

	li suml = 0, sumr = accumulate(a, a + n, 0ll);
	li ansv = LLONG_MAX, ansp = LLONG_MIN;
	forn(i, n) {
		li curv = li(i) * a[i] - suml;
		curv += sumr - li(n - i) * a[i];
		if (ansv > curv) {
			ansv = curv;
			ansp = a[i];
		}
		suml += a[i];
		sumr -= a[i];
	}
	assert(sumr == 0);

	assert(ansv != LLONG_MAX);
	cerr << "ansv: " << ansv << endl;
	cout << ansp << endl;
}

Complexity: O(nlogn).

710C - Magic Odd Square

The problem was suggested by Resul Hangeldiyev Resul.

The solution can be got from the second sample testcase. Easy to see that if we place all odd numbers in the center in form of rhombus we will get a magic square.

int n;

bool read() {
	return !!(cin >> n);
}

const int N = 101;

int a[N][N];

void solve() {
	memset(a, 0, sizeof(a));

	forn(i, n / 2) {
		int len = n / 2 - i;
		forn(j, len) {
			int x1 = i, x2 = n - 1 - i;
			int y1 = j, y2 = n - 1 - j;
			a[x1][y1] = 1;
			a[x1][y2] = 1;
			a[x2][y1] = 1;
			a[x2][y2] = 1;
		}
	}

	int odd = 1, even = 2;
	forn(i, n)
		forn(j, n)
			if (a[i][j]) a[i][j] = even, even += 2;
			else a[i][j] = odd, odd += 2;

	forn(i, n) {
		forn(j, n) {
			if (j) putchar(' ');
			printf("%d", a[i][j]);
		}
		puts("");
	}
}

Complexity: O(n²).

710D - Two Arithmetic Progressions

I wanted to give this problem a lot of time ago. I thought it is very standard problem, but I underestimated its difficulty.

Let's write down the equation describing the problem: a₁k + b₁ = a₂l + b₂ → a₁k - a₂l = b₂ - b₁. So we have linear Diofant equation with two variables: Ax + By = C, A = a₁, B =  - a₂, C = b₂ - b₁. The solution has the form: , where the last equation can be solved by extended Euclid algorithm and p is any integral number. The variable p should satisfy two conditions: and . The values A and B are fixed, so we can get the segment of possible values for the values p. The length of the segment is the answer for the problem.

li a1, b1, a2, b2, l, r;

bool read() {
	return !!(cin >> a1 >> b1 >> a2 >> b2 >> l >> r);
}

li _ceil(li, li);
li _floor(li a, li b) { return b < 0 ? _floor(-a, -b) : a < 0 ? -_ceil(-a, b) : a / b; }
li _ceil(li a, li b) { return b < 0 ? _ceil(-a, -b) : a < 0 ? -_floor(-a, b) : (a + b - 1) / b; }

li gcd(li a, li b, li& x, li& y) {
	if (!a) {
		x = 0, y = 1;
		return b;
	}
	li xx, yy, g = gcd(b % a, a, xx, yy);
	x = yy - b / a * xx;
	y = xx;
	return g;
}

void solve() {
	l = max(0ll, _ceil(l - b1, a1));
	r = _floor(r - b1, a1);
	if (l > r) {
		puts("0");
		return;
	}

	li A = a1, B = -a2, C = b2 - b1;
	li x0, y0;
	li g = gcd(A, B, x0, y0);
	if (C % g) {
		puts("0");
		return;
	}

	if (g < 0) {
		g = -g;
		x0 = -x0;
		y0 = -y0;
	}

	li L = _ceil(r * g - x0 * C, B);
	li R = _floor(l * g - x0 * C, B);
	R = min(R, _floor(y0 * C, A));

	li ans = max(0ll, R - L + 1);
	cout << ans << endl;
}

Complexity: O(log(max(a₁, a₂))).

710E - Generate a String

The problem was suggested by Zi Song Yeoh zscoder.

This problem has a simple solution described by participants in the comments.

My solution is a little harder. Let's solve it using dynamic programming. Let z_n be the smallest amount of time needed to get n letters 'a'. Let's consider transitions: the transition for adding one letter 'a' can be simply done. Let's process transitions for multiplying by two and subtraction by one simultaneously: let's decrease the number 2·i i times by one right after getting it. Easy to see that such updates never include each other, so we can store them in queue by adding the new update at the tail of the queue and taking the best update from the head.

The solution is hard to describe, but it is very simple in the code, so please check it to understand the idea :-)

int n;
li x, y;

bool read() {
	return !!(cin >> n >> x >> y);
}

const int N = 20 * 1000 * 1000 + 13;

li z[N];

void solve() {
	forn(i, N) z[i] = LLONG_MAX;

	list<pair<li, int>> q;

	z[0] = 0;
	forn(i, n + 1) {
		while (!q.empty() && q.front().y < i) q.pop_front();

		if (!q.empty()) z[i] = min(z[i], q.front().x - i * x);
		assert(z[i] != LLONG_MAX);

		pair<li, int> cur(z[i] + y + 2 * i * x, 2 * i);
		while (!q.empty() && q.back().x > cur.x) q.pop_back();
		q.pb(cur);

		z[i + 1] = min(z[i + 1], z[i] + x);
	}

	cout << z[n] << endl;
}

Complexity: O(n).

710F - String Set Queries

The problem was suggested by Alexandr Kulkov adamant.

Let's get rid of the queries for deleting a string. There are no strings that will be added two times, so we can calculate the answer for the added (but not deleted strings) and for the deleted separately and subtract the second from the first to get the answer. So we can consider that there are no queries of deletion.

Now let's use Aho-Corasik algorithm. The only difficulty is that the strings are adding in online mode, but Aho-Corasik algorithm works only after adding all the strings. Note that the answer for the given set of strings equal to the answer for any part of the set plus the answer for the remaining part. Let's use the trick with converting the static data structure (Aho-Corasik in this case) to the dynamic one.

For the set of n strings let's maintain a set of no more than logn sets of the strings with sizes of different powers of two. After adding new string we should move the sets from the lowest powers of two to the largest until we got an invariant set of sets.

Easy to see that each string will be moved no more than logm times, so we can process each query in O(logn) time.

const int N = 4 * 300300, A = 26, LOGN = 20;

struct node {
    char c;
    int parent, link, output;
    int next[A], automata[A];
		int cnt;
    
    node(char c = -1, int parent = -1, int link = -1, int output = -1, int cnt = -1):
        c(c), parent(parent), link(link), output(output), cnt(cnt) {
        memset(next, -1, sizeof(next));
        memset(automata, -1, sizeof(automata));
    }
};
node t[N];

vector<int> ids;
inline int get_idx() {
	assert(!ids.empty());
	int ans = ids.back();
	ids.pop_back();
	t[ans] = node();
	return ans;
}
inline void return_idx(int idx) {
	ids.pb(idx);
}

inline int add(const string& s, int root) {
    int v = root;
    forn(i, sz(s)) {
        if (t[v].next[s[i] - 'a'] == -1) {
					int idx = get_idx();
					t[v].next[s[i] - 'a'] = idx;
					t[idx] = node(s[i], v, -1, -1);
        }
        v = t[v].next[s[i] - 'a'];
    }
    t[v].output = v;
    return v;
}
int link(int v, int root) {
    int& ans = t[v].link;
    if (ans != -1) return ans;
		if (v == root || t[v].parent == root) return ans = root;
    char c = t[v].c;
    int vv = link(t[v].parent, root);
    while (vv != root && t[vv].next[c - 'a'] == -1)
        vv = link(vv, root);
    return ans = (t[vv].next[c - 'a'] == -1? root: t[vv].next[c - 'a']);
}
int output(int v, int root) {
    int& ans = t[v].output;
    if (ans != -1) return ans;
    return ans = (v == root? root: output(link(v, root), root));
}
int cnt(int v, int root) {
	int& ans = t[v].cnt;
	if (ans != -1) return ans;
	v = output(v, root);
	if (v == root) return ans = 0;
	return ans = 1 + cnt(link(v, root), root);
}
int next(int v, char c, int root) {
    int& ans = t[v].automata[c - 'a'];
    if (ans != -1) return ans;
    if (t[v].next[c - 'a'] != -1)
        return ans = t[v].next[c - 'a'];
    return ans = (v == root? root: next(link(v, root), c, root));
}

void dfs_clear(int v) {
	forn(i, A) if (t[v].next[i] != -1) dfs_clear(t[v].next[i]);
	return_idx(v);
}

string a[N];

int build(int root, const vector<int>& ids) {
	dfs_clear(root);
	root = get_idx();
	forn(i, sz(ids)) add(a[ids[i]], root);
	return root;
}

int calc(int root, int idx) {
	int ans = 0;
	const string& s = a[idx];
	int v = root;
	forn(i, sz(s)) {
		v = next(v, s[i], root);
		ans += cnt(v, root);
	}
	return ans;
}

int m;

bool read() {
	return !!(cin >> m);
}

struct blocks {
	int root[LOGN];
	vector<int> block[LOGN];

	void clear() {
		forn(i, LOGN) {
			block[i].clear();
			root[i] = get_idx();
		}
	}

	void insert(int i) {
		vector<int> cur(1, i);
		forn(i, LOGN)
			if (sz(block[i]) == sz(cur)) {
				cur.insert(cur.end(), all(block[i]));
				block[i].clear();
				root[i] = build(root[i], block[i]);
			} else {
				block[i] = cur;
				root[i] = build(root[i], block[i]);
				break;
			}
	}

	li calc2(int idx) {
		li ans = 0;
		forn(i, LOGN) {
			ans += calc(root[i], idx);
		}
		return ans;
	}
};

char buf[N];
blocks z1, z2;

void solve() {
	ids.clear();
	nfor(i, N) ids.pb(i);

	z1.clear();
	z2.clear();

	forn(i, m) {
		int type;
		assert(scanf("%d%s", &type, buf) == 2);
		a[i] = buf;

		if (type == 1) {
			z1.insert(i);
		} else if (type == 2) {
			z2.insert(i);
		} else if (type == 3) {
			li ans = z1.calc2(i) - z2.calc2(i);
			printf("%lld\n", ans);
			fflush(stdout);
		} else throw;
	}
}

Complexity: O((slen + m)logm), where slen is the total length of the string from the input.

Hello, Codeforces!

Educational Codeforces Round 16 will take place on 22 August 2016 at 17:00 MSK for the first and the second divisions.

It will be the last educational round prepared by me. As I earlier said I started to work at the great team of AIM Tech and now have less time to prepare a rounds. To leave the rounds interesting and qualitative another guy will continue to prepare them.

The problemset was partially suggested by Codeforces users. The problem C was suggested by user Resul Hangeldiyev Resul. The problem E is the next problem suggested by Zi Song Yeoh zscoder. The problem F was suggested Alexandr Kulkov adamant. Other problems was suggested by me (they are standard, but it is important to be able to solve them).

All the problems was prepared by me (Edvard Davtyan). Thanks to Tatiana Semyonova Tatiana_S for checking the English statements. Thanks a lot to Ivan Popovich NVAL for testing the problems A-E and Alexandr Kulkov adamant for testing the problem F.

I hope you will enjoy the problems! I think the problemset is little bit more difficult than usual, but I'm sure that it will not stop you :-)

Good luck and have fun!

UPD 1: The testing on hacks is completed. Thank you for participation!

UPD 2: The editorial is ready.

691A - Fashion in Berland

The problem was suggested and prepared by Arthur Jaworski KingArthur.

In this problem you should simply check the conditions from the problem statement.

const int N = 1010;

int n, a[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n) assert(cin >> a[i]);
	return true;
}

void solve() {
	int cnt = accumulate(a, a + n, 0);
	if (n == 1) puts(cnt == 1 ? "YES" : "NO");
	else puts(cnt == n - 1 ? "YES" : "NO");
}

Complexity: O(n).

691B - s-palindrome

The problem was suggested by Nikita Melnikov nickmeller.

In this problem you should simply find the symmetric letters by picture and also observe that the pairs (b, d) and (p, q) is the symmteric reflections.

string s;

bool read() {
	return !!getline(cin, s);
}

string symmetric = "AHIMOoTUVvWwXxY";
map<char, char> opposite = {{'p', 'q'}, {'q', 'p'}, {'d', 'b'}, {'b', 'd'}};

void solve() {
	forn(i, sz(s)) {
		if (symmetric.find(s[i]) != string::npos) {
			if (s[sz(s) - 1 - i] != s[i]) {
				puts("NIE");
				return;
			}
		} else if (opposite.count(s[i])) {
			if ((sz(s) & 1) && i == (sz(s) >> 1)) {
				puts("NIE");
				return;
			}
			if (s[sz(s) - 1 - i] != opposite[s[i]]) {
				puts("NIE");
				return;
			}
		} else {
			puts("NIE");
			return;
		}
	}
	puts("TAK");
}

Complexity: O(n).

691C - Exponential notation

The problem was suggsted by user blowUpTheStonySilence.

This is an implementation problem. You should do exactly what is written in the problem statement. On my mind the simplest way is to find the position of the first not zero digit and the position of the dot. The difference between that positions is the value of b (if the value is positive you should also decrease it by one).

string s;

bool read() {
	return !!getline(cin, s);
}

void solve() {
	int pos = int(find_if(all(s), [](char c) { return c != '0' && c != '.'; }) - s.begin());;
	size_t dot_pos = s.find('.');
	if (dot_pos == string::npos) {
		dot_pos = s.size();
	} else {
		s.erase(dot_pos, 1);
	}

	int expv = (int) dot_pos - pos;
	if (expv > 0) expv--;
	forn(t, 2) {
		while (s.back() == '0') s.pop_back();
		reverse(all(s));
	}
	if (sz(s) > 1) s.insert(1, ".");
	if (expv == 0) printf("%s\n", s.c_str());
	else printf("%sE%d\n", s.c_str(), expv);
}

Complexity: O(n).

691D - Swaps in Permutation

The problem was suggested by Zi Song Yeoh zscoder.

Consider a graph with n vertices whose edges is the pairs from the input. It's possible to swap any two values with the positions in some connected component in that graph. So we can sort the values from any component in decreasing order. Easy to see that after sorting the values of each component we will get the lexicographically maximal permutation.

const int N = 1200300;

int n, m;
int p[N];
pti a[N];

bool read() {
	if (!(cin >> n >> m)) return false;
	forn(i, n) {
		assert(scanf("%d", &p[i]) == 1);
		p[i]--;
	}
	forn(i, m) {
		assert(scanf("%d%d", &a[i].x, &a[i].y) == 2);
		a[i].x--, a[i].y--;
	}
	return true;
}

bool used[N];
vector<int> g[N];
vector<int> perm, pos;

void dfs(int v) {
	if (used[v]) return;
	used[v] = true;
	pos.pb(v);
	perm.pb(p[v]);

	for (auto to : g[v]) dfs(to);
}

int ans[N];

void solve() {
	forn(i, n) {
		g[i].clear();
		used[i] = false;
	}

	forn(i, m) {
		g[a[i].x].pb(a[i].y);
		g[a[i].y].pb(a[i].x);
	}

	int cnt = 0;
	forn(i, n)
		if (!used[i]) {
			cnt++;
			pos.clear();
			perm.clear();
			dfs(i);
			sort(all(pos));
			sort(all(perm), greater<int>());
			forn(j, sz(perm))
				ans[pos[j]] = perm[j];
		}

	forn(i, n) {
		if (i) putchar(' ');
		printf("%d", ans[i] + 1);
	}
	puts("");
}

Complexity: O(n + m).

691E - Xor-sequences

The problem was suggested by Zi Song Yeoh zscoder.

Let z_ij be the number of xor-sequences of length i with the last element equal to a_j. Let g_ij be equal to one if contains the number of ones in binary presentation that is multiple of three. Otherwise let g_ij be equal to zero. Consider a vectors z_i = {z_ij}, z_i - 1 = {z_{i - 1, j}} and a matrix G = {g_ij}. Easy to see that z_i = G × z_i - 1. So z_n = Gⁿz₀. Let's use the associative property of matrix multiplication: at first let's calculate Gⁿ with binary matrix exponentiation and then multiply it to the vector z₀.

const int N = 101;

int n;
li k;
li a[N];

bool read() {
	if (!(cin >> n >> k)) return false;
	forn(i, n) assert(cin >> a[i]);
	return true;
}

const int mod = 1000 * 1000 * 1000 + 7;

inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
inline void inc(int& a, int b) { a = add(a, b); }
inline int mul(int a, int b) { return int(a * 1ll * b % mod); }

int count(li x) {
	int ans = 0;
	while (x) {
		ans++;
		x &= x - 1;
	}
	return ans;
}

void mul(int a[N][N], int b[N][N], int n) {
	static int c[N][N];
	forn(i, n)
		forn(j, n) {
			c[i][j] = 0;
			forn(k, n) inc(c[i][j], mul(a[i][k], b[k][j]));
		}
	forn(i, n) forn(j, n) a[i][j] = c[i][j];
}

void bin_pow(int a[N][N], li b, int n) {
	static int ans[N][N];
	forn(i, n) forn(j, n) ans[i][j] = i == j;

	while (b) {
		if (b & 1) mul(ans, a, n);
		mul(a, a, n);
		b >>= 1;
	}

	forn(i, n) forn(j, n) a[i][j] = ans[i][j];
}

void solve() {
	static int a[N][N];
	memset(a, 0, sizeof(a));
	forn(i, n) {
		forn(j, n)
			a[i][j] = count(::a[i] ^ ::a[j]) % 3 == 0;
		a[i][n] = 1;
	}

	//forn(i, n + 1) clog << mp(a[i], n + 1) << endl;

	bin_pow(a, k, n + 1);

	int ans = 0;
	forn(i, n + 1) inc(ans, a[i][n]);
	cout << ans << endl;
}

Complexity: O(n³logk).

691F - Couple Cover

The problem was suggested by Michael Kirsche mkirsche.

Let's count the number of pairs with multiple less than p. To get the number of not less pairs we should sumply subtract from n·(n - 1) the number of less pairs. Let cnt_i be the number of values in a equal to i and z_j be the number of pairs from a with the multiple equal to j. To calculate the values from z we can use something like Eratosthenes sieve: let's iterate over the first multiplier a and the multiple of it b = ka and increment z_b by the value cnt_a·cnt_k. After calculating the array z we should calculate the array of its partial sums and find the number of less pairs in O(1) time.

const int N = 3100300;

int n, m;
int a[N], p[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n) assert(scanf("%d", &a[i]) == 1);
	assert(cin >> m);
	forn(i, m) assert(scanf("%d", &p[i]) == 1);
	return true;
}

int cnt[N];
li z[N];

void solve() {
	memset(cnt, 0, sizeof(cnt));

	forn(i, n) cnt[a[i]]++;

	fore(a, 1, N) {
		if (!cnt[a]) continue;
		for (int b = a; b < N; b += a) {
			if (b / a != a) z[b] += li(cnt[a]) * cnt[b / a];
			else z[b] += li(cnt[a]) * (cnt[a] - 1);
		}
	}

	fore(i, 1, N) z[i] += z[i - 1];

	forn(i, m) {
		li ans = li(n) * (n - 1) - z[p[i] - 1];
		printf("%lld\n", ans);
	}
}

Complexity: O(n + XlogX), where X is the maximal value in p.

Hello, Codeforces!

Educational Codeforces Round 14 will take place on 13 July 2016 at 19:00 MSK for the first and the second divisions.

<I already have a long list of problems, so don't be upset if your problems wasn't used yet>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks (of course the difficult tasks are also needed). Please send only the problems for which you know the solution with clear statement (the story is not required). And also please add one or two samples to make the problem statement more clear.

Thanks a lot to them and all others who are sending the problems! The number of unused problems are increasing. If I didn't miss anything I already replied to all who sent me the problems at least 5-6 days ago. Please be patient if your problem was not used a long while.

</I already have a long list of problems, so don't be upset if your problems wasn't used yet>

The problemset was suggested by Codeforces users. The problem А was suggested and prepared by user Arthur Jaworski KingArthur. The problem B was suggested by Nikita Melnikov nickmeller. The problem C was suggested by user blowUpTheStonySilence. The problem D and E was suggested by Zi Song Yeoh zscoder (he is on IMO now, so good luck to him). The problem F was suggested Michael Kirsche mkirsche.

As I said the problem A is prepared by Arthur Jaworski KingArthur. All other problems was prepared by me (Edvard Davtyan). Thanks to Tatiana Semyonova Tatiana_S for checking the English statements. The problems was tested by users suggested them, respectively: Arthur Jaworski KingArthur, Nikita Melnikov nickmeller, user blowUpTheStonySilence and Michael Kirsche mkirsche. Thanks a lot to all of them!

I hope you will enjoy the problems! I think the problemset is balanced and not difficult.

Good luck and have fun!

UPD 1: All the hacks for the problem D will be rejudged.

UPD 2: Hack phase will be extended until tomorrow.

UPD 3: Sorry for the problems in the problem D. The solutions that got WA3 were rejudged. The problem is OK now.

UPD 4: The contest is finished. All the solutions were judged on the full testsets. The editorial will be published soon.

UPD 5: The editorial is published.

678A - Johny Likes Numbers

The problem was suggested by Abdrakhman Ismail bash.

We should find minimal x, so x·k > n. Easy to see that . To learn more about floor/ceil functions I reccomend the book of authors Graham, Knuth, Patashnik "Concrete Mathematics". There is a chapter there about that functions and their properties.

li n, k;

bool read() {
	return !!(cin >> n >> k);
}

void solve() {
	cout << (n / k + 1) * k << endl;
}

Complexity: O(1).

678B - The Same Calendar

The problem was suggested by Arthur Jaworski KingArthur.

Two calendars are same if and only if they have the same number of days and starts with the same day of a week. So we should simply iterate over years and maintain the day of a week of January, 1st (for example). Easy to see that the day of a week increases by one each year except of the leap years, when it increases by two.

int y;

bool read() {
	return !!(cin >> y);
}

bool leap(int y) {
	return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}

void solve() {
	bool is_leap = leap(y);
	int d = 0;
	do {
		d++;
		if (leap(y)) d++;
		y++;
		d %= 7;
	} while (d || leap(y) != is_leap);
	cout << y << endl;
}

Complexity: O(1) — easy to see that we will not iterate more than some small fixed constant times.

678C - Joty and Chocolate

The problem was suggested by Sheikh Monir skmonir.

Easy to see that we can paint with both colours only tiles with the numbers multiple of lcm(a, b). Obviously that tiles should be painted with more expensive colour. So the answer equals to .

li n, a, b, p, q;

bool read() {
	return !!(cin >> n >> a >> b >> p >> q);
}

li gcd(li a, li b) { return !a ? b : gcd(b % a, a); }
li lcm(li a, li b) { return a / gcd(a, b) * b; }

void solve() {
	li ans = 0;
	ans += (n / a) * p;
	ans += (n / b) * q;
	ans -= (n / lcm(a, b)) * min(p, q);
	cout << ans << endl;
}

Complexity: O(log(max(a, b))).

678D - Iterated Linear Function

The problem was suggested by Zi Song Yeoh zscoder.

The problem can be solved using closed formula: it's need to calculate the sum of geometric progression. The formula can be calculated using binary exponentiation.

I'll describe more complicated solution, but it's more general. If we have a set of variables and at each step all variables are recalculating from each other using linear function, we can use binary matrix exponentiation. There is only one variable x in our problem. The new variable x' is calculating using formula A·x + B. Consider the matrix z = [[A, B], [0, 1]] and the vector v = [0, 1]. Let's multiply z and v. Easy to see that we will get the vector v' = [x', 1]. So to make n iterations we should multiply z and v n times. We can do that using binary matrix exponentiation, because matrix multiplication is associative.

As an exercise try to write down the matrix for the Fibonacci numbers and calculate the n-th Fibonacci number in O(logn) time. The matrix and the vector is under the spoiler.

int A, B, x;
li n;

bool read() {
	return !!(cin >> A >> B >> n >> x);
}

const int mod = 1000 * 1000 * 1000 + 7;

inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
inline int mul(int a, int b) { return int(a * 1ll * b % mod); }
inline void inc(int& a, int b) { a = add(a, b); }

void mul(int a[2][2], int b[2][2]) {
	static int res[2][2];
	forn(i, 2)
		forn(j, 2) {
			res[i][j] = 0;
			forn(k, 2) inc(res[i][j], mul(a[i][k], b[k][j]));
		}
	forn(i, 2) forn(j, 2) a[i][j] = res[i][j];
}

void bin_pow(int a[2][2], li b) {
	static int res[2][2];
	forn(i, 2) forn(j, 2) res[i][j] = i == j;

	while (b) {
		if (b & 1) mul(res, a);
		mul(a, a);
		b >>= 1;
	}

	forn(i, 2) forn(j, 2) a[i][j] = res[i][j];
}

void solve() {
	int z[2][2] = {
		{ A, B },
		{ 0, 1 }
	};
	bin_pow(z, n);
	int result = add(mul(z[0][0], x), z[0][1]);
	cout << result << endl;
}

Complexity: O(logn).

678E - Another Sith Tournament

The problem was suggested and prepared by Alexey Dergunov dalex.

Let's solve the problem using dynamic programming. z_mask, i — the maximal probability of Ivans victory if the siths from the mask already fought and the i-th sith left alive. To calculate that DP we should iterate over the next sith (he will fight against the i-th sith): .

const int N = 20, EXPN = (1 << 18) + 3;

int n;
ld p[N][N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n) forn(j, n) assert(cin >> p[i][j]);
	return true;
}

ld z[EXPN][N];

ld solve(int mask, int i) {
	ld& ans = z[mask][i];
	if (ans > -0.5) return ans;
	if (mask == (1 << n) - 1) return ans = !i;
	ans = 0;
	forn(j, n)
		if (!(mask & (1 << j))) {
			ld cur = 0;
			cur += solve(mask | (1 << j), i) * p[i][j];
			cur += solve(mask | (1 << j), j) * p[j][i];
			ans = max(ans, cur);
		}
	return ans;
}

void solve() {
	if (n == 1) {
		puts("1");
		return;
	}

	forn(i, 1 << n) forn(j, n) z[i][j] = -1;

	ld ans = 0;
	forn(i, n)
		forn(j, i) {
			int mask = (1 << i) | (1 << j);
			ld cur = 0;
			cur += solve(mask, i) * p[i][j];
			cur += solve(mask, j) * p[j][i];
			ans = max(ans, cur);
		}
	cout << ans << endl;
}

Time complexity: O(2ⁿn²).

Memory complexity: O(2ⁿn).

678F - Lena and Queries

The problem was suggested by AmirMohammad Dehghan PrinceOfPersia.

Let's interpret the problem geometrically: the pairs from the set are the lines and the problem to find to topmost intersection of the vertical line with the lines from the set.

Let's split the queries to blocks. Consider the lines added before the current block and that will not deleted in the current block. Let's build the lower envelope by that lines. Now to calculate the answer to the query we should get maximum over the lines from the envelope and the lines from the block before the current query that is not deleted yet. There are no more than lines from the block, so we can iterate over them. Let's find the answers from the envelope for all queries of the third type from the block at once: we should sort them and iterate over envelope using two pointers technique.

const int N = 300300;

int n;
int t[N], a[N], b[N], id[N], q[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n) {
		assert(scanf("%d", &t[i]) == 1);
		if (t[i] == 1) {
			assert(scanf("%d%d", &a[i], &b[i]) == 2);
		} else if (t[i] == 2) {
			assert(scanf("%d", &id[i]) == 1);
			id[i]--;
		} else if (t[i] == 3) {
			assert(scanf("%d", &q[i]) == 1);
		} else throw;
	}
	return true;
}

bool in_set[N], deleted[N];
vector<pair<pti, int>> lines;
vector<pti> envelope;

void build_envelope() {
	envelope.clear();
	envelope.reserve(n);

	forn(ii, sz(lines)) {
		int i = lines[ii].y;
		if (in_set[i] && !deleted[i]) {
			assert(t[i] == 1);
			pti c(a[i], b[i]);
			while (!envelope.empty()) {
				pti b = envelope.back();
				if (b.x == c.x) {
					envelope.pop_back();
					continue;
				} else if (sz(envelope) > 1) {
					pti a = envelope[sz(envelope) - 2];

					ld xc = ld(c.y - a.y) / (a.x - c.x);
					ld xb = ld(b.y - a.y) / (a.x - b.x);

					if (xc < xb) {
						envelope.pop_back();
						continue;
					}
				}
				break;
			}
			envelope.pb(c);
		}
	}
}

li ans[N];
vector<pti> qs;

void process_qs() {
	sort(all(qs));

	int p = 0;
	forn(i, sz(qs)) {
		li q = qs[i].x;
		int id = qs[i].y;

		while (p + 1 < sz(envelope)) {
			li cval = envelope[p].x * q + envelope[p].y;
			li nval = envelope[p + 1].x * q + envelope[p + 1].y;
			if (cval > nval) break;
			p++;
		}

		if (p < sz(envelope)) {
			ans[id] = envelope[p].x * q + envelope[p].y;
		}
	}
}

void solve() {
	lines.clear();
	lines.reserve(n);
	forn(i, n) if (t[i] == 1) lines.pb(mp(mp(a[i], b[i]), i));
	sort(all(lines));

	memset(in_set, false, sizeof(in_set));
	memset(deleted, false, sizeof(deleted));
	forn(i, n) ans[i] = LLONG_MIN;

	int blen = int(sqrtl(n));
	blen = 2500;
	for (int l = 0; l < n; l += blen) {
		int r = min(n, l + blen);

		memset(deleted, false, sizeof(deleted));
		fore(i, l, r) if (t[i] == 2) deleted[id[i]] = true;
		build_envelope();

		qs.clear();
		qs.reserve(r - l);
		fore(i, l, r) if (t[i] == 3) qs.pb(mp(q[i], i));
		process_qs();

		fore(i, l, r) {
			if (t[i] == 1) in_set[i] = true;
			else if (t[i] == 2) in_set[id[i]] = false;
			else {
				fore(j, l, r) {
					if (t[j] == 1 && in_set[j])
						ans[i] = max(ans[i], li(a[j]) * q[i] + b[j]);
					else if (t[j] == 2 && in_set[id[j]])
						ans[i] = max(ans[i], li(a[id[j]]) * q[i] + b[id[j]]);
				}
				if (ans[i] != LLONG_MIN) printf("%lldn", ans[i]);
				else puts("EMPTY SET");
			}
		}
	}
}

Complexity: .

Hello, Codeforces!

Educational Codeforces Round 13 will take place on 13 June 2016 at 19:00 MSK for the first and the second divisions. Almost two months passed from the previous round. That is due the next reasons: 1) I coordinated regular CF-round at the end of April; 2) about whole CP community were busy with preparing and competing in ACM ICPC WF in May; 3) at the beginning of this month I start to work at AimTech (I hope that I'll have enough time to continue prepare ERs).

<It's need to read at least once maybe you'll find something interesting>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks (of course the difficult tasks are also needed). Please send only the problems for which you know the solution with clear statement (the story is not required). And also please add one or two samples to make the problem statement more clear.

</It's need to read at least once maybe you'll find something interesting>

The problemset was suggested by Codeforces users. The problem А was suggested by user Abdrakhman Ismail bash. The problem B was suggested by Arthur Jaworski KingArthur. The problem C was suggested by Sheikh Monir skmonir. The problem D was suggested by Zi Song Yeoh zscoder (there are a lot of unused his problems). The problem E was suggested and prepared by Alexey Dergunov dalex. The simpler version of the problem F was suggested by AmirMohammad Dehghan PrinceOfPersia.

Thanks a lot to them and all others who are sending the problems! The number of unused problems are increasing. If I didn't miss anything I already replied to all who sent me the problems at least 5-6 days ago. Please be patient if your problem was not used a long while.

As I said the problem E is prepared by Alexey Dergunov dalex. All other problems was prepared by me (Edvard Davtyan). Thanks to Tatiana Semyonova Tatiana_S for checking the English statements. The problems was tested by users suggested them, respectively: Abdrakhman Ismail bash, Arthur Jaworski KingArthur, Sheikh Monir skmonir, Zi Song Yeoh zscoder, Alexey Dergunov dalex and AmirMohammad Dehghan PrinceOfPersia. Thanks a lot to all of them!

I hope you will enjoy the problems! Previous time the problems were too hard. I've tried to fix that. The problems should be simpler than usual.

Good luck and have fun!

UPD: The round is finished. The editorial is published.

It's the first summer round :-)

Hey, Codeforces!

I've just submitted a solution for a SPOJ problem and get strange verdict. I'm using SPOJ for the first time and can't find any FAQ section there. What does it mean? And why my submission is black?

665A - Buses Between Cities

The problem was suggested by Sergey Erlikh unprost.

Consider the time interval when Simion will be on the road strictly between cities (x₁, y₁) (x₁ = 60h + m, y₁ = x₁ + t_a). Let's iterate over the oncoming buses. Let (x₂, y₂) be the time interval when the oncoming bus will be strictly between two cities. If the intersection of that intervals (x = max(x₁, x₂), y = min(y₁, y₂)) is not empty than Simion will count that bus.

int a, ta;
int b, tb;
int h, m;

bool read() {
	if (!(cin >> a >> ta)) return false;
	assert(cin >> b >> tb);
	assert(scanf("%d:%d", &h, &m) == 2);
	return true;
}

void solve() {
	int x1 = h * 60 + m;
	int y1 = x1 + ta;

	int ans = 0;
	for (int x2 = 5 * 60 + 0; x2 < 24 * 60; x2 += b) {
		int y2 = x2 + tb;
		int x = max(x1, x2), y = min(y1, y2);
		if (x < y)
			ans++;
	}
	cout << ans << endl;
}

Complexity: O(1).

665B - Shopping

The problem was suggested by Ayush Anand JeanValjean01.

In this problem you should simply do what was written in the problem statement. There are no tricks.

const int N = 111;

int n, m, k;
int p[N];
int a[N][N];

bool read() {
	if (!(cin >> n >> m >> k)) return false;
	forn(i, k) {
		assert(scanf("%d", &p[i]) == 1);
		p[i]--;
	}
	forn(i, n)
		forn(j, m) {
			assert(scanf("%d", &a[i][j]) == 1);
			a[i][j]--;
		}
	return true;
}

void solve() {
	int ans = 0;
	forn(i, n)
		forn(j, m) {
			int pos = int(find(p, p + k, a[i][j]) - p);
			ans += pos + 1;
			nfor(l, pos) p[l + 1] = p[l];
			p[0] = a[i][j];
		}
	cout << ans << endl;
}

Complexity: O(nmk).

665C - Simple Strings

The problem was suggested by Zi Song Yeoh zscoder.

There are two ways to solve this problem: greedy approach and dynamic programming.

The first apprroach: Considerr some segment of consecutive equal characters. Let k be the length of that segment. Easy to see that we should change at least characters in the segment to remove all the pairs of equal consecutive letters. On the other hand we can simply change the second, the fourth etc. symbols to letter that is not equal to the letters before and after the segment.

const int N = 200200;

int n;
char s[N];

bool read() {
	if (!gets(s)) return false;
	n = int(strlen(s));
	return true;
}

void solve() {
	for (int i = 0, j = 0; i < n; i = j) {
		while (j < n && s[j] == s[i]) j++;
		char c = 'a';
		while (c == s[i] || (i > 0 && c == s[i - 1]) || (j < n && c == s[j]))
			c++;
		fore(k, i, j)
			if ((i + k) & 1)
				s[k] = c;
	}
	puts(s);
}

The second approach: Let z_ka be the minimal number of changes so that the prefix of length k has no equal consecutive letters and the symbol s'_k equals to a. Let's iterate over the letter on the position k + 1 and if it is not equal to a make transition. The cost of the transition is equal to 0 if we put the same letter as in the original string s on the position k + 1. Otherwise the cost is equal to 1.

const int N = 1200300, A = 27;

int n;
char s[N];

bool read() {
	if (!gets(s)) return false;
	n = int(strlen(s));
	return true;
}

int z[N][A];
int p[N][A];
char ans[N];

void solve() {
	memset(z, 63, sizeof(z));

	z[0][A - 1] = 0;
	forn(i, n) {
		int c = int(s[i] - 'a');
		forn(j, A) {
			int dv = z[i][j];
			if (dv > INF / 2) continue;
			forn(nj, A - 1) {
				if (nj == j) continue;
				int ct = nj != c;
				if (z[i + 1][nj] > dv + ct) {
					z[i + 1][nj] = dv + ct;
					p[i + 1][nj] = j;
				}
			}
		}
	}

	int idx = int(min_element(z[n], z[n] + A) - z[n]);

	for (int i = n, j = idx; i > 0; j = p[i][j], i--)
		ans[i - 1] = char('a' + j);
	ans[n] = 0;

	cerr << z[n][idx] << endl;
	puts(ans);
}

Complexity: O(n).

665D - Simple Subset

The problem was suggested by Zi Song Yeoh zscoder.

Consider the subset A that is the answer to the problem. Let a, b, c be the arbitrary three elements from A and let no more than one of them is equal to 1. By the pigeonhole principle two of three elements from a, b, c have the same parity. So we have two integers with even sum and only one of them is equal to 1, so their sum is also greater than 2. So the subset A is not simple. In this way A consists of only two numbers greater than one (with a prime sum) or consists of some number of ones and also maybe other value x, so that x + 1 is a prime.

We can simply process the first case in O(n²) time. The second case can be processed in linear time. Also we should choose the best answer from that two.

To check the value of order 2·10⁶ for primality in O(1) time we can use the simple or the linear Eratosthenes sieve.

const int N = 1010, X = 2100300;

int n, a[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n) assert(scanf("%d", &a[i]) == 1);
	return true;
}

int szp, p[X];
int mind[X];

void prepare() {
	fore(i, 2, X) {
		if (!mind[i]) {
			p[szp++] = i;
			mind[i] = i;
		}
		for (int j = 0; j < szp && p[j] <= mind[i] && i * p[j] < X; j++)
			mind[i * p[j]] = p[j];
	}
}

void printAns(int cnt1, int a = -1, int b = -1) {
	vector<int> ans;
	forn(i, cnt1) ans.pb(1);
	if (a != -1) ans.pb(a);
	if (b != -1) ans.pb(b);
	assert(!ans.empty());
	random_shuffle(all(ans));

	cout << sz(ans) << endl;
	forn(i, sz(ans)) {
		if (i) putchar(' ');
		printf("%d", ans[i]);
	}
	puts("");
}

void solve() {
	int cnt1 = (int) count(a, a + n, 1);

	function<bool(int)> isPrime = [](int p) { return mind[p] == p; };

	if (cnt1 > 0)
		forn(i, n)
			if (a[i] != 1 && isPrime(a[i] + 1)) {
				printAns(cnt1, a[i]);
				return;
			}

	if (cnt1 > 1) {
		printAns(cnt1);
		return;
	}

	forn(i, n)
		forn(j, i)
			if (isPrime(a[i] + a[j])) {
				printAns(0, a[i], a[j]);
				return;
			}

	printAns(0, a[0]);
}

Complexity: O(n² + X), where X is the maximal value in a.

665E - Beautiful Subarrays

The problem was suggested by Zi Song Yeoh zscoder.

The sign is used for the binary operation for bitwise exclusive or.

Let s_i be the xor of the first i elements on the prefix of a. Then the interval (i, j] is beautiful if . Let's iterate over j from 1 to n and consider the values s_j as the binary strings. On each iteration we should increase the answer by the value z_j — the number of numbers s_i (i < j) so . To do that we can use the trie data structure. Let's store in the trie all the values s_i for i < j. Besides the structure of the trie we should also store in each vertex the number of leaves in the subtree of that vertex (it can be easily done during adding of each binary string). To calculate the value z_j let's go down by the trie from the root. Let's accumulate the value cur equals to the xor of the prefix of the value s_j with the already passed in the trie path. Let the current bit in s_j be equal to b and i be the depth of the current vertex in the trie. If the number cur + 2ⁱ ≥ k then we can increase z_j by the number of leaves in vertex , because all the leaves in the subtree of tha vertex correspond to the values s_i that for sure gives . After that we should go down in the subtree b. Otherwise if cur + 2ⁱ < k then we should simply go down to the subtree and recalculate the value cur = cur + 2ⁱ.

const int N = 1200300, LOGN = 30, V = N * LOGN;

int n, k;
int a[N];

bool read() {
	if (!(cin >> n >> k)) return false;
	forn(i, n) assert(scanf("%d", &a[i]) == 1);
	return true;
}

int tsz;
int nt[V][2];
int cnt[V];

void clear() {
	forn(i, V) {
		nt[i][0] = nt[i][1] = -1;
		cnt[i] = 0;
	}
	tsz = 1;
}

void add(int x) {
	int v = 0;
	cnt[v]++;

	nfor(i, LOGN) {
		int b = (x >> i) & 1;
		if (nt[v][b] == -1) {
			assert(tsz < V);
			nt[v][b] = tsz++;
		}
		v = nt[v][b];
		cnt[v]++;
	}
}


int calc(int x) {
	int v = 0;
	int ans = 0;

	auto getCnt = [](int v) { return v == -1 ? 0 : cnt[v]; };

	int cur = 0;
	nfor(i, LOGN) {
		if (v == -1) break;
		int b = (x >> i) & 1;
		if ((cur | (1 << i)) >= k) {
			ans += getCnt(nt[v][b ^ 1]);
			v = nt[v][b];
		} else {
			v = nt[v][b ^ 1];
			cur |= (1 << i);
		}
	}
	if (cur >= k) ans += getCnt(v);
	return ans;
}

void solve() {
	clear();

	add(0);

	li ans = 0;
	int s = 0;
	forn(i, n) {
		s ^= a[i];
		li cur = calc(s);
		ans += cur;
		add(s);
	}
	cout << ans << endl;
}

Comlpexity by the time and the memory: O(nlogX), where X is the maximal xor on the prefixes.

665F - Four Divisors

The editorial for this problem is a little modification of the materials from the lecture of Mikhail Tikhomirov Endagorion of the autumn of 2015 in Moscow Institute of Physics and Technology. Thanks a lot to Endagorion for that materials.

Easy to see that only the numbers of the form p·q and p³ (for different prime p, q) have exactly four positive divisors.

We can easily count the numbers of the form p³ in , where n is the number from the problem statement.

Now let p < q and π(k) be the number of primes from 1 to k. Let's iterate over all the values p. Easy to see that . So for fixed p we should increase the answer by the value .

So the task is ot to find — the number of primes not exceeding , for all p.

Denote p_j the j-th prime number. Denote dp_n, j the number of k such that 1 ≤ k ≤ n, and all prime divisors of k are at least p_j (note that 1 is counted in all dp_n, j, since the set of its prime divisors is empty). dp_n, j satisfy a simple recurrence:

1. dp_n, 1 = n (since p₁ = 2)

2. dp_n, j = dp_{n, j + 1} + dp_{⌊ n / pj⌋, j}, hence dp_{n, j + 1} = dp_n, j - dp_{⌊ n / pj⌋, j}

Let p_k be the smallest prime greater than . Then π(n) = dp_n, k + k - 1 (by definition, the first summand accounts for all the primes not less than k).

If we evaluate the recurrence dp_n, k straightforwardly, all the reachable states will be of the form dp_{⌊ n / i⌋, j}. We can also note that if p_j and p_k are both greater than , then dp_n, j + j = dp_n, k + k. Thus, for each ⌊ n / i⌋ it makes sense to keep only values of dp_{⌊ n / i⌋, j}.

Instead of evaluating all DP states straightforwardly, we perform a two-step process:

1. Choose K.

2. Run recursive evaluation of dp_n, k. If we want to compute a state with n < K, memorize the query ``count the numbers not exceeding n with all prime divisors at least k''.

3. Answer all the queries off-line: compute the sieve for numbers up to K, then sort all numbers by the smallest prime divisor. Now all queries can be answered using RSQ structure. Store all the answers globally.

4. Run recurisive evaluation of dp_n, k yet again. If we want to compute a state with n < K, then we must have preprocessed a query for this state, so take it from the global set of answers.

The performance of this approach relies heavily on Q — the number of queries we have to preprocess.

Statement. .

Proof:

Each state we have to preprocess is obtained by following a dp_{⌊ n / pj⌋, j} transition from some greater state. It follows that Q doesn't exceed the total number of states for n > K.

The preprocessing of Q queries can be done in , and it is the heaviest part of the computation. Choosing optimal , we obtain the complexity .

li n;

bool read() {
	return !!(cin >> n);
}

const int K = 10 * 1000 * 1000;
const int N = K;
const int P = 700100;
const int Q = 25 * 1000 * 1000;

int szp, p[P];
int mind[N];

void prepare() {
	szp = 0;
	forn(i, N) mind[i] = -1;
	fore(i, 2, N) {
		if (mind[i] == -1) {
			assert(szp < P);
			mind[i] = szp;
			p[szp++] = i;
		}
		for (int j = 0; j < szp && j <= mind[i] && i * p[j] < N; j++)
			mind[i * p[j]] = j;
	}
}

inline int getk(li n) {
	int lf = 0, rg = szp - 1;
	while (lf != rg) {
		int md = (lf + rg) >> 1;
		if (p[md] * 1ll * p[md] > n) rg = md;
		else lf = md + 1;
	}
	assert(p[lf] * 1ll * p[lf] > n);
	return lf;
}

int t[K];
void inc(int i, int val) {
	for ( ; i < K; i |= i + 1)
		t[i] += val;
}
int sum(int i) {
	int ans = 0;
	for ( ; i >= 0; i = (i & (i + 1)) - 1)
		ans += t[i];
	return ans;
}

int szq;
pti q[Q];
int ans[Q];
vector<int> vs[P];

void process() {
	sort(q, q + szq, greater<pti> ());
	memset(t, 0, sizeof(t));

	forn(i, szp) vs[i].clear();
	fore(i, 2, K)
		vs[mind[i]].pb(i);

	inc(1, +1);

	int p = szp - 1;
	for (int i = 0, j = 0; i < szq; i = j) {
		while (p >= q[i].x) {
			for (auto v : vs[p])
				inc(v, +1);
			p--;
		}

		while (j < szq && q[j].x == q[i].x) {
			ans[j] = sum(q[j].y);
			j++;
		}
	}
}

map<pair<li, int>, li> z;

li solve(li n, int jj, bool fs) {
	if (!n) return 0;
	int j = min(jj, getk(n));
	if (!j) return n + j - jj;

	li ans = 0;
	if (n < K) {
		pti p(j, (int) n);
		if (fs) {
			assert(szq < Q);
			q[szq++] = p;
			ans = 0;
			return 0;
		} else {
			int idx = int(lower_bound(q, q + szq, p, greater<pti> ()) - q);
			assert(idx < szq && q[idx] == p);
			ans = ::ans[idx];
		}
	} else {
		if (!z.count(mp(n, j))) {
			ans = solve(n, j - 1, fs);
			ans -= solve(n / p[j - 1], j - 1, fs);
			z[mp(n, j)] = ans;
		} else {
			ans = z[mp(n, j)];
		}
	}

	ans += j - jj;

	return ans;
}

inline li pi(li n, bool fs) {
	int k = szp - 1;
	return solve(n, k, fs) + k - 1;
}

void solve() {
	szq = 0;
	z.clear();
	for (int j = 0; p[j] * 1ll * p[j] <= n; j++) {
		li nn = n / p[j];
		if (nn > p[j]) {
			pi(n / p[j], true);
		}
	}

	process();

	z.clear();
	li ans = 0;
	for (int j = 0; p[j] * 1ll * p[j] <= n; j++) {
		li nn = n / p[j];
		if (nn > p[j]) {
			ans += pi(n / p[j], false);
			ans -= j + 1;
		}
	}

	for (int i = 0; i < szp && p[i] * 1ll * p[i] * 1ll * p[i] <= n; i++)
		ans++;

	cout << ans << endl;
}

Complexity: .

Hello, Codeforces!

Note! The day of the contest here was wrong. Now it's fixed.

Educational Codeforces Round 12 will take place on 20 april 2016 at 18:00 MSK for the first and the second divisions.

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks (of course the difficult tasks are also needed). Please send only the problems for which you know the solution with clear statement (the story is not required). And also please add one or two samples to make the problem statement more clear.

The problemset was suggested by Codeforces users (it's time to lift this sentence inside the tegs). The problem А was suggested by user unprost. The problem B was suggested by Ayush Anand JeanValjean01. The problems C, D and E was suggested by Zi Song Yeoh zscoder. Sheikh Monir skmonir a long ago sent me a problem with difficulty C or D. I improved it by significant increase of the constraints (thanks to Mikhail Tikhomirov Endagorion who told how to solve such things). So the problem F was born.

Thanks a lot to them and all others who are sending the problems! The number of unused problems are increasing. If I didn't miss anything I already replied to all who sent me the problems at least 5-6 days ago. Please be patient if your problem was not used a long while.

The problems was prepared by me (Edvard Davtyan). Thanks to Maria Belova Delinur for checking the English statements. The problems was tested by users suggested them, respectively: unprost, Ayush Anand JeanValjean01, Zi Song Yeoh zscoder and Sheikh Monir skmonir. Thanks a lot to all of them!

I hope you will enjoy the problems! On my mind all the problems except of F is easier than usual, but F is harder.

Good luck and have fun!

Only 30 days left to the ACM ICPC World Finals!

It will be difficult to focus on the problems in such a beautiful place :-)

UPD1: The first part of the contest is finished. The open hacks will be opened in a few minutes.

UPD2: The editorial is ready for the problem F.

UPD3: The editorial is ready.

660A - Co-prime Array

The problem was suggested by Ali Ibrahim C137.

Note that we should insert some number between any adjacent not co-prime elements. On other hand we always can insert the number 1.

const int N = 1010;

int n, a[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n) assert(scanf("%d", &a[i]) == 1);
	return true;
}

void solve() {
	function<int(int, int)> gcd = [&](int a, int b) { return !a ? b : gcd(b % a, a); };

	vector<int> ans;
	forn(i, n) {
		ans.pb(a[i]);
		if (i + 1 < n && gcd(a[i], a[i + 1]) > 1)
			ans.pb(1);
	}

	cout << sz(ans) - n << endl;
	forn(i, sz(ans)) {
		if (i) putchar(' ');
		printf("%d", ans[i]);
	}
	puts("");
}

Complexity: O(nlogn).

660B - Seating On Bus

The problem was suggested by Srikanth Bhat bharsi.

In this problem you should simply do what was written in the problem statement. There are no tricks.

int n, m;

bool read() {
	return !!(cin >> n >> m);
}

const int N = 111;

int a[N][4];

void solve() {
	forn(i, n) {
		a[i][0] = 2 * i;
		a[i][1] = 2 * (n + i);
		a[i][2] = 2 * (n + i) + 1;
		a[i][3] = 2 * i + 1;
	}

	vector<int> ans;
	forn(i, n) {
		ans.pb(a[i][1]);
		ans.pb(a[i][0]);
		ans.pb(a[i][2]);
		ans.pb(a[i][3]);
	}

	nfor(i, sz(ans)) // inverse order
		if (ans[i] >= m)
			ans.erase(ans.begin() + i);

	forn(i, m) {
		if (i) putchar(' ');
		printf("%d", ans[i] + 1);
	}
	puts("");
}

Complexity: O(n).

660C - Hard Process

The problem was suggested by Mohammad Amin Raeisi Smaug.

Let's call the segment [l, r] good if it contains no more than k zeroes. Note if segment [l, r] is good than the segment [l + 1, r] is also good. So we can use the method of two pointers: the first pointer is l and the second is r. Let's iterate over l from the left to the right and move r while we can (to do that we should simply maintain the number of zeroes in the current segment).

const int N = 1200300;

int n, k;
int a[N];

bool read() {
	if (!(cin >> n >> k)) return false;
	forn(i, n) assert(scanf("%d", &a[i]) == 1);
	return true;
}

void solve() {
	int ansl = 0, ansr = 0;
	int j = 0, cnt = 0;
	forn(i, n) {
		if (j < i) {
			j = i;
			cnt = 0;
		}

		while (j < n) {
			int ncnt = cnt + !a[j];
			if (ncnt > k) break;
			cnt += !a[j];
			j++;
		}
		
		if (j - i > ansr - ansl)
			ansl = i, ansr = j;

		if (cnt > 0) cnt -= !a[i];
	}

	cout << ansr - ansl << endl;
	fore(i, ansl, ansr) a[i] = 1;
	forn(i, n) {
		if (i) putchar(' ');
		printf("%d", a[i]);
	}
	puts("");
}

Complexity: O(n).

660D - Number of Parallelograms

The problem was suggested by Sadegh Mahdavi smahdavi4.

It's known that the diagonals of a parallelogram split each other in the middle. Let's iterate over the pairs of points a, b and consider the middle of the segment : . Let's calculate the value cnt_c for each middle. cnt_c is the number of segments a, b with the middle c. Easy to see that the answer is .

const int N = 2020;

int n;
int x[N], y[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n)
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	return true;
}

inline li C2(li n) { return n * (n - 1) / 2; }

void solve() {
	map<pti, int> cnt;

	forn(i, n)
		forn(j, i) {
			int cx = x[i] + x[j];
			int cy = y[i] + y[j];
			cnt[{cx, cy}]++;
		}

	li ans = 0;
	for (const auto& p : cnt)
		ans += C2(p.y);
	cout << ans << endl;
}

Complexity: O(n²logn).

660E - Different Subsets For All Tuples

The problem was suggested by Lewin Gan Lewin.

Let's consider some subsequence with the length k > 0 (the empty subsequences we will count separately by adding the valye mⁿ at the end) and count the number of sequences that contains it. We should do that accurately to not count the same sequence multiple times. Let x₁, x₂, ..., x_k be the fixed subsequence. In the original sequence before the element x₁ can be some other elements, but none of them can be equal to x₁ (because we want to count the subsequence exactly one time). So we have m - 1 variants for each of the elements before x₁. Similarly between elements x₁ and x₂ can be other elements and we have m - 1 choices for each of them. And so on. After the element x_k can be some elements (suppose there are j such elements) with no additional constraints (so we have m choices for each of them). We fixed the number of elements at the end j, so we should distribute n - k - j numbers between numbers before x₁, between x₁ and x₂, \ldots, between x_k - 1 and x_k. Easy to see that we have choices to do that (it's simply binomial coefficient with allowed repititions). The number of sequences x₁, x₂, ..., x_k equals to m^k. So the answer is . Easy to transform the last sum to the sum . Note the last inner sum can be calculating using the formula for parallel summing: . So the answer equals to . Also we can get the closed formula for the last sum to get logarithmic solution, but it is not required in the problem.

int n, m;

bool read() {
	return !!(cin >> n >> m);
}

const int N = 1200300;

const int mod = 1000 * 1000 * 1000 + 7;

int gcd(int a, int b, int& x, int& y) {
	if (!a) {
		x = 0, y = 1;
		return b;
	}
	int xx, yy, g = gcd(b % a, a, xx, yy);
	x = yy - b / a * xx;
	y = xx;
	return g;
}

inline int inv(int a) {
	int x, y;
	assert(gcd(a, mod, x, y) == 1);
	x %= mod;
	return x < 0 ? x + mod : x;
}

inline int mul(int a, int b) { return int(a * 1ll * b % mod); }
inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
inline int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }

inline void inc(int& a, int b) { a = add(a, b); }

int fact[N], ifact[N];

inline int C(int n, int k) {
	if (k < 0 || k > n) return 0;
	return mul(fact[n], mul(ifact[k], ifact[n - k]));
}

int pm[N], pm1[N];

void solve() {
	const int N = n + 1;

	fact[0] = 1; fore(i, 1, N) fact[i] = mul(fact[i - 1], i);
	forn(i, N) ifact[i] = inv(fact[i]);

	pm[0] = 1; fore(i, 1, N) pm[i] = mul(pm[i - 1], m);
	pm1[0] = 1; fore(i, 1, N) pm1[i] = mul(pm1[i - 1], sub(m, 1));

	int ans = pm[n];
	fore(s, 1, n + 1) {
		int cur = 1;
		cur = mul(cur, pm[s]);
		cur = mul(cur, pm1[n - s]);
		cur = mul(cur, C(n, s - 1));
		inc(ans, cur);
	}
	cout << ans << endl;
}

Complexity: O((n + m)log MOD), где MOD = 10⁹ + 7.

660F - Bear and Bowling 4

The problem was prepared by Kamil Debowski Errichto. The problem analysis is also prepared by him.

The key is to use divide and conquer. We need a recursive function f(left, right) that runs f(left, mid) and f(mid+1, right) (where mid = (left + right) / 2) and also considers all intervals going through mid. We will eventually need a convex hull of lines (linear functions) and let's see how to achieve it.

For variables L, R (, ) we will try to write the score of interval [L, R] as a linear function. It would be good to get something close to a_L·x_R + b_L where a_L and b_L depend on L, and x_R depends on R only.

For each L we should find a linear function f_L(x) = a_L·x + b_L where a_L, b_L should fit the equation ( * ):

Now we have a set of linear functions representing all possible left endpoints L. For each right endpoint R we should find x_R and const_R to fit equation ( * ) again. With value of x_R we can iterate over functions f_L to find the one maximizing value of b_L + a_L·x_R. And (still for fixed R) we should add const_R to get the maximum possible score of interval ending in R.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nax = 1e6 + 5;
ll ans;
ll t[nax];

struct Fun {
	ll a, b;
	ll getValue(ll x) { return a * x + b; }
};

void rec(int first, int last) {
	if(first == last) {
		ans = max(ans, t[first]);
		return;
	}
	int mid = (first + last) / 2;
	
	rec(first, mid); // the left half is [first, mid]
	rec(mid+1, last); // the right half is [mid+1, last]
	
	// we must consider all intervals starting in [first,mid] and ending in [mid+1, last]
	
	vector<Fun> functions;
	ll sum_so_far = 0; // t[i]+t[i+1]+...+t[mid]
	ll score_so_far = 0; // t[i]*1 + t[i+1]*2 + ... + t[mid]*(mid-i+1)
	for(int i = mid; i >= first; --i) {
		sum_so_far += t[i];
		score_so_far += sum_so_far;
		functions.push_back(Fun{mid - i + 1, score_so_far});
	}
	
	sum_so_far = 0;
	score_so_far = 0;
	for(int i = mid+1; i <= last; ++i) {
		sum_so_far += t[i];
		score_so_far += t[i] * (i - mid);
		for(Fun & f : functions) {
			ll score = score_so_far + f.getValue(sum_so_far);
			ans = max(ans, score);
		}
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
	rec(1, n);
	printf("%lldn", ans);
	return 0;
}

Now let's make it faster. After finding a set of linear functions f_L we should build a convex hull of them (note that they're already sorted by slope). To achieve it we need something to compare 3 functions and decide whether one of them is unnecessary because it's always below one of other two functions. Note that in standard convex hull of points you also need something similar (but for 3 points). Below you can find an almost-fast-enough solution with a useful function bool is_middle_needed(f1, f2, f3). You may check that numbers calculated there do fit in long long.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nax = 1e6 + 5;
ll ans;
ll t[nax];

struct Fun {
	ll a, b;
	ll getValue(ll x) { return a * x + b; }
};

bool is_middle_needed(const Fun & f1, const Fun & f2, const Fun & f3) {
	// we ask if for at least one 'x' there is f2(x) > max(f1(x), f3(x))
	assert(0 < f1.a && f1.a < f2.a && f2.a < f3.a);
	
	// where is the intersection of f1 and f2?
	// f1.a * x + f1.b = f2.a * x + f2.b
	// x * (f2.a - f1.a) = f1.b - f2.b
	// x = (f1.b - f2.b) / (f2.a - f1.a)
	ll p1 = f1.b - f2.b;
	ll q1 = f2.a - f1.a;
	// and the intersection of f1 and f3
	ll p2 = f1.b - f3.b;
	ll q2 = f3.a - f1.a;
	assert(q1 > 0 && q2 > 0);
	// return p1 / q1 < p2 / q2
	return p1 * q2 < q1 * p2;
}

void rec(int first, int last) {
	if(first == last) {
		ans = max(ans, t[first]);
		return;
	}
	int mid = (first + last) / 2;
	
	rec(first, mid); // the left half is [first, mid]
	rec(mid+1, last); // the right half is [mid+1, last]
	
	// we must consider all intervals starting in [first,mid] and ending in [mid+1, last]
	
	vector<Fun> functions;
	ll sum_so_far = 0; // t[i]+t[i+1]+...+t[mid]
	ll score_so_far = 0; // t[i]*1 + t[i+1]*2 + ... + t[mid]*(mid-i+1)
	for(int i = mid; i >= first; --i) {
		sum_so_far += t[i];
		score_so_far += sum_so_far;
		Fun f = Fun{mid - i + 1, score_so_far};
		while(true) {
			int s = functions.size();
			if(s >= 2 && !is_middle_needed(functions[s-2], functions[s-1], f))
				functions.pop_back();
			else
				break;
		}
		functions.push_back(f);
	}
	
	sum_so_far = 0;
	score_so_far = 0;
	for(int i = mid+1; i <= last; ++i) {
		sum_so_far += t[i];
		score_so_far += t[i] * (i - mid);
		for(Fun & f : functions) {
			ll score = score_so_far + f.getValue(sum_so_far);
			ans = max(ans, score);
		}
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
	rec(1, n);
	printf("%lldn", ans);
	return 0;
}

Finally, one last thing is needed to make it faster than O(n²). We should use the fact that we have built a convex hull of functions (lines). For each R you should binary search optimal function. Alternatively, you can sort pairs (x_R, const_R) and then use the two pointers method — check the implementation in my solution below. It gives complexity because we sort by x_R inside of a recursive function. I think it's possible to get rid of this by sorting prefixes in advance because it's equivalent to sorting by x_R. And we should use the already known order when we run a recursive function for smaller intervals. So, I think is possible this way — anybody implemented it?

// O(n log^2(n))
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nax = 1e6 + 5;
ll ans;
ll t[nax];

struct Fun {
	ll a, b;
	ll getValue(ll x) { return a * x + b; }
};

bool is_middle_needed(const Fun & f1, const Fun & f2, const Fun & f3) {
	// we ask if for at least one 'x' there is f2(x) > max(f1(x), f3(x))
	assert(0 < f1.a && f1.a < f2.a && f2.a < f3.a);
	
	// where is the intersection of f1 and f2?
	// f1.a * x + f1.b = f2.a * x + f2.b
	// x * (f2.a - f1.a) = f1.b - f2.b
	// x = (f1.b - f2.b) / (f2.a - f1.a)
	ll p1 = f1.b - f2.b;
	ll q1 = f2.a - f1.a;
	// and the intersection of f1 and f3
	ll p2 = f1.b - f3.b;
	ll q2 = f3.a - f1.a;
	assert(q1 > 0 && q2 > 0);
	// return p1 / q1 < p2 / q2
	return p1 * q2 < q1 * p2;
}

void rec(int first, int last) {
	if(first == last) {
		ans = max(ans, t[first]);
		return;
	}
	int mid = (first + last) / 2;
	
	rec(first, mid); // the left half is [first, mid]
	rec(mid+1, last); // the right half is [mid+1, last]
	
	// we must consider all intervals starting in [first,mid] and ending in [mid+1, last]
	
	vector<Fun> functions;
	ll sum_so_far = 0; // t[i]+t[i+1]+...+t[mid]
	ll score_so_far = 0; // t[i]*1 + t[i+1]*2 + ... + t[mid]*(mid-i+1)
	for(int i = mid; i >= first; --i) {
		sum_so_far += t[i];
		score_so_far += sum_so_far;
		Fun f = Fun{mid - i + 1, score_so_far};
		while(true) {
			int s = functions.size();
			if(s >= 2 && !is_middle_needed(functions[s-2], functions[s-1], f))
				functions.pop_back();
			else
				break;
		}
		functions.push_back(f);
	}
	
	vector<pair<ll, ll>> points;
	sum_so_far = 0;
	score_so_far = 0;
	for(int i = mid+1; i <= last; ++i) {
		sum_so_far += t[i];
		score_so_far += t[i] * (i - mid);
		points.push_back({sum_so_far, score_so_far});
		/*for(Fun & f : functions) {
			ll score = score_so_far + f.getValue(sum_so_far);
			ans = max(ans, score);
		}*/
	}
	
	sort(points.begin(), points.end());
	int i = 0; // which function is the best
	for(pair<ll, ll> p : points) {
		sum_so_far = p.first;
		score_so_far = p.second;
		while(i + 1 < (int) functions.size()
			&& functions[i].getValue(sum_so_far) <= functions[i+1].getValue(sum_so_far))
				++i;
		ans = max(ans, score_so_far + functions[i].getValue(sum_so_far));
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
	rec(1, n);
	printf("%lldn", ans);
	return 0;
}

Complexity: O(nlog²n).

Hello, Codeforces!

Educational Codeforces Round 11 will take place on 8 april 2016 at 18:00 MSK for the first and the second divisions.

<The changes in the last paragraph>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks (of course the difficult tasks are also needed). Please send only the problems for which you know the solution with clear statement (the story is not required). And also please add one or two samples to make the problem statement more clear.

</The changes in the last paragraph>

The problemset was suggested by Codeforces users. The problem А was suggested by Ali Ibrahim C137. The problem B was suggested by Srikanth Bhat bharsi. Mohammad Amin Raeisi Smaug sent the problem C. The problem D was suggested by Sadegh Mahdavi smahdavi4 a long ago. The problem E is the last (the fourth) problem suggested by Lewin Gan Lewin. The problem F is the last (if I'm not wrong the third) problem suggested by Kamil Debowski Errichto.

Thanks a lot to them and all others who are sending the problems! At this point I've checked all the problems sent to me (except maybe for the problems sent in last week). I hope that I've replied to all of you. I have a list with all problems sent to me, so be sure I don't forget about your problem.

The problems F was prepared by Kamil Debowski Errichto. Other problems was prepared by me (Edvard Davtyan). Thanks to Maria Belova Delinur for checking the English statements. The problems was tested by users suggested them, respectively: Ali Ibrahim C137, Srikanth Bhat bharsi, Mohammad Amin Raeisi Smaug, Sadegh Mahdavi smahdavi4, Lewin Gan Lewin and Kamil Debowski Errichto. Thanks a lot to all of them!

I hope you will enjoy the problems! I'm considering the possibility to copy the problem E with larger constraints as problem G. What do you think about that?

Good luck and have fun!

P.S.: The bus from the problem B.

UPD: The contest is finished. Congrats to tribute_to_Ukraine_2022 and uwi with the win and halyavin with 93 hacks! The editorial is ready.

652A - Gabriel and Caterpillar

The problem was suggested by unprost.

Let's consider three cases.

1. h₁ + 8a ≥ h₂ — in this case the caterpillar will get the apple on the same day, so the answer is 0.

2. The first condition is false and a ≤ b — in this case the caterpillar will never get the apple, because it can't do that on the first day and after each night it will be lower than one day before.

3. If the first two conditions are false easy to see that the answer equals to .

int h1, h2;
int a, b;

bool read() {
	return !!(cin >> h1 >> h2 >> a >> b);
}

void solve() {
	if (h1 + 8 * a >= h2)
		puts("0");
	else if (a > b) {
		int num = h2 - h1 - 8 * a, den = 12 * (a - b);
		cout << (num + den - 1) / den << endl;
	} else
		puts("-1");
}

Also this problem can be solved by simple modelling, because the heights and speeds are small.

Complexity: O(1).

652B - z-sort

The problem was suggested by Smaug.

Easy to see that we can z-sort any array a. Let be the number of even positions in a. We can assign to those positions k maximal elements and distribute other n - k elements to odd positions. Obviously the resulting array is z-sorted.

const int N = 1010;

int n, a[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n) assert(scanf("%d", &a[i]) == 1);
	return true;
}

int ans[N];

void solve() {
	sort(a, a + n);

	int p = 0, q = n - 1;
	forn(i, n)
		if (i & 1) ans[i] = a[q--];
		else ans[i] = a[p++];
	assert(q + 1 == p);

	forn(i, n) {
		if (i) putchar(' ');
		printf("%d", ans[i]);
	}
	puts("");
}

Complexity: O(nlogn).

652C - Foe Pairs

This is one of the problems suggested by Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A.

Let's precompute for each value x its position in permutation pos_x. It's easy to do in linear time. Consider some foe pair (a, b) (we may assume pos_a < pos_b). Let's store for each value a the leftmost position pos_b such that (a, b) is a foe pair. Denote that value as z_a. Now let's iterate over the array a from right to left and maintain the position rg of the maximal correct interval with the left end in the current position lf. To maintain the value rg we should simply take the minimum with the value z[lf]: rg = min(rg, z[lf]). And finally we should increment the answer by the value rg - lf + 1.

const int N = 300300;

int n, m;
int p[N];
pt b[N];

bool read() {
	if (!(cin >> n >> m)) return false;
	forn(i, n) {
		assert(scanf("%d", &p[i]) == 1);
		p[i]--;
	}
	forn(i, m) {
		int x, y;
		assert(scanf("%d%d", &x, &y) == 2);
		x--, y--;
		b[i] = pt(x, y);
	}
	return true;
}

int pos[N];
vector<int> z[N];

void solve() {
	forn(i, n) pos[p[i]] = i;
	forn(i, n) z[i].clear();
	forn(i, m) {
		int x = pos[b[i].x], y = pos[b[i].y];
		if (x > y) swap(x, y);
		z[x].pb(y);
	}

	li ans = 0;
	int rg = n;
	nfor(i, n) {
		forn(j, sz(z[i])) rg = min(rg, z[i][j]);
		ans += rg - i;
	}
	cout << ans << endl;
}

Complexity: O(n + m).

652D - Nested Segments

The problem was suggested by Alexey Dergunov dalex.

This problem is a standard two-dimensional problem that can be solved with one-dimensional data structure. In the same way a lot of other problems can be solved (for example the of finding the maximal weighted chain of points so that both coordinates of each point are greater than the coordinates of the predecessing point). Rewrite the problem formally: for each i we should count the number of indices j so that the following conditions are hold: a_i < a_j and b_j < a_j. Let's sort all segments by the left ends from right to left and maintain some data structure (Fenwick tree will be the best choice) with the right ends of the processed segments. To calculate the answer for the current segment we should simple take the prefix sum for the right end of the current segment.

So the condition a_i < a_j is hold by sorting and iterating over the segments from the right to the left (the first dimension of the problem). The condition b_j < a_j is hold by taking the prefix sum in data structure (the second dimension).

const int N = 1200300;

int n;
pair<pti, int> a[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n) assert(scanf("%d%d", &a[i].x.x, &a[i].x.y) == 2), a[i].y = i;
	return true;
}

int t[N];
vector<int> ys;

inline void inc(int i, int val) {
	for ( ; i < sz(ys); i |= i + 1)
		t[i] += val;
}

inline int sum(int i) {
	int ans = 0;
	for ( ; i >= 0; i = (i & (i + 1)) - 1)
		ans += t[i];
	return ans;
}

int ans[N];

void solve() {
	ys.clear();
	forn(i, n) ys.pb(a[i].x.y);
	sort(all(ys));
	ys.erase(unique(all(ys)), ys.end());
	forn(i, sz(ys)) t[i] = 0;

	sort(a, a + n);
	nfor(i, n) {
		int idx = int(lower_bound(all(ys), a[i].x.y) - ys.begin());
		ans[a[i].y] = sum(idx);
		inc(idx, +1);
	}

	forn(i, n) printf("%dn", ans[i]);
}

Complexity: O(nlogn).

652E - Pursuit For Artifacts

The problem was suggested by Alexey Dergunov dalex.

Edge biconnected component in an undirected graph is a maximal by inclusion set of vertices so that there are two edge disjoint paths between any pair of vertices. Consider the graph with biconnected components as vertices. Easy to see that it's a tree (if it contains some cycle then the whole cycle is a biconnected component). All edges are destroying when we passing over them so we can't returnto the same vertex (in the tree) after leaving it by some edge.

Consider the biconncted components that contains the vertices a and b. Let's denote them A and B. Statement: the answer is YES if and only if on the path in the tree from the vertex A to the vertex B there are an edge with an artifact or there are a biconnected component that contains some edge with an artifact. Easy to see that the statement is true: if there are such edge then we can pass over it in the tree on the path from A to B or we can pass over it in biconnected component. The converse also easy to check.

Here is one of the ways to find edge biconnected components:

1. Let's orient all edges to direction that depth first search passed it for the first time.

2. Let's find in new directed graph strongly connected components.

Statement: the strongly connected components in the new graph coincide with the biconnected components in old undirected graph.

Also you can notice that the edges in tree is the bridges of the graph (bridges in terms of graph theory). So you can simply find the edges in the graph.

forn(i, sz(g2[v])) {
    int to = g2[v][i];
    if (to == p) continue;
    if (dfs3(to, v, t, ans)) {
       ans |= good[v];
       ans |= w2[v][i];
       return true;
    }
}
return false;

u++, c = 0;
forn(i, sz) if (used[perm[i]] != u) dfs2(perm[i]), c++;

forn(i, c) good[i] = false;

forn(i, c) {
    g2[i].clear();
    w2[i].clear();
}
forn(i, n)
    forn(j, sz(g1[i])) {
       int x = comp[i], y = comp[g1[i][j]];
       if (x != y) {
         g2[x].pb(y);
         w2[x].pb(w[i][j]);
       } else if (w[i][j]) good[x] = true;
    }

n = c;
a = comp[a], b = comp[b];

bool ans = good[a];
assert(dfs3(a, -1, b, ans));
puts(ans ? "YES" : "NO");

Complexity: O(n + m).

652F - Ants on a Circle

The problem was suggested by Lewin Gan Lewin.

The first observation: if all the ants are indistinguishable we can consider that there are no collisions and all the ants are passing one through another. So we can easily determine the final positions of all the ants, but we can't say which ant will be in which position.

The second observation: the relative order of the ants will be the same all the time.

So to solve the problem we should only find the position of one ant after t seconds.

Let's solve that problem in the following way:

1. Consider the positions of all the ants after m time units. Easy to see that by the first observation all the positions of the ants will left the same, but the order will be different (we will have some cyclic shift of the ants). If we find that cyclic shift sh we can apply it times.

2. After that we will have only t ± od m time units.

So the problem now is to model the process for the one ant with m and r ± od m time units. Note that in that time interval the fixed ant will have no more than two collisions with each other ant. So if we model the process with ignoring all collisions except the ones that include the fixed ant, we will have no more than 2n collisions.

Let's model that process with two queues for the ants going to the left and to the right. Each time we should take the first ant in the queue with opposite direction, process the collision and add that ant to the end of the other queue.

Hint: you will have a problem when the fixed ant can be in two different positions at the end, but it's easy to fix with doing the same with the next ant.

fore(d, 1, n) {
    int i = (v - d + n) % n;
    if (a[i].x.y == 'R') tor.push(mp(i > v ? a[i].x.x - m : a[i].x.x, 0));
}
fore(d, 1, n) {
    int i = (v + d) % n;
    if (a[i].x.y == 'L') tol.push(mp(i < v ? a[i].x.x + m : a[i].x.x, 0));
}

li cx = a[v].x.x;
char cd = a[v].x.y;
li curt = 0;
while (t > 0) {
    if (cd == 'R') {
       if (tol.empty()) return getPos(cx, cd, t);
       assert(curt >= tol.front().y);
       li nx = tol.front().x - (curt - tol.front().y);
       tol.pop();
       li d = min((nx - cx + 1) >> 1, t);
       assert(cx <= nx);
       cx += d, nx -= d;
       t -= d;
       if (cx > nx) {
         assert((nx - cx) & 1);
         cx--, nx++;
       }
       assert(cx <= nx);
       cd = 'L';
       curt += d;
       assert(nx - m < cx);
       tor.push(mp(nx - m, curt));
    } else {
       if (tor.empty()) return getPos(cx, cd, t);
       assert(curt >= tor.front().y);
       li nx = tor.front().x + (curt - tor.front().y);
       tor.pop();
       li d = min((cx - nx + 1) >> 1, t);
       assert(cx >= nx);
       cx -= d, nx += d;
       t -= d;
       if (cx < nx) {
         assert((cx - nx) & 1);
         cx++, nx--;
       }
       assert(cx >= nx);
       cd = 'R';
       curt += d;
       assert(nx + m > cx);
       tol.push(mp(nx + m, curt));
    }
}
return getPos(cx, cd, 0);

vector<int> poss;
forn(i, n)
    poss.pb(getPos(a[i].x.x, a[i].x.y, t));
sort(all(poss));

vector<vector<int>> xs;
forn(s, 2) {
    int x = calc(s, m);
    int pos = -1;
    forn(i, n)
       if (a[i].x.x == x) {
         assert(pos == -1);
         pos = i;
       }
    assert(pos != -1);
    pos = (pos - s + n) % n;
    li k = (t / m) % n;
    pos = int((s + pos * k) % n);

    x = calc(pos, t % m);
    xs.pb(vector<int>());
    forn(i, sz(poss))
       if (poss[i] == x)
         xs.back().pb(i);
    assert(!xs.back().empty());
    if (sz(xs.back()) == 2) assert(xs.back()[0] + 1 == xs.back()[1]);
}

int pos = xs[0][0];
if (sz(xs[0]) > 1) {
    assert(sz(xs[0]) == 2);
    assert(pos + 1 == xs[0][1]);
    if (xs[0] != xs[1])
       pos = xs[0][1];
}

forn(ii, n) {
    int i = (ii + pos) % sz(poss);
    ans[a[ii].y] = poss[i];
}

forn(i, n) {
    if (i) putchar(' ');
    assert(0 <= ans[i] && ans[i] < m);
    printf("%d", ans[i] + 1);
}
puts("");

Complexity: O(nlogn).

Hello, Codeforces!

[Note the unusual (for the educational round) start time!]

Educational Codeforces Round 10 will take place after a long delay on 25 march 2016 at 16:00 MSK for the first and the second divisions. The long delay is caused by the high frequency of contests and championships on Codeforces. You can read about educational rounds here and here.

<The same as before>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks.

</The same as before>

From now traditionally the problemset was totally suggested by Codeforces users. The problem А for the third time was suggested by user unprost (no hope for the short problem statement :-)). The problem B was suggested by user Smaug. The problem C is another problem from the set sent by Bayram Berdiyev bayram, Allanur Shiriyev Allanur and Bekmyrat Atayev Bekmyrat.A. Alexey Dergunov dalex suggested the problems D and E. The problem F was suggested by Lewin Gan Lewin.

Thanks a lot to them and all others who are sending the problems or just ideas of the problems!

The problems D and E was prepared by Alexey Dergunov dalex. Other problems was prepared by me (Edvard Davtyan). I want to note the generator for the problem E its difficulty comparable with the solution to the problem F. Thanks to Maria Belova Delinur for checking the English statements. The problems was tested by users: unprost, Smaug, Aleksa Plavsic allllekssssa, Alexey Dergunov dalex and Lewin Gan Lewin. Thanks a lot to all of them!

I hope you will enjoy the problems!

P.S.: I really like the problem F and hope to see Accepted-s for it.

Good luck and have fun!

UPD: The contest is finished. The editorial is ready.

632A - Grandma Laura and Apples

The problem was suggested by unprost.

Consider the process from the end. The last buyer will always buy a half of an apple and get a half for free (so the last string always is halfplus). After that each buyer increases the number of apples twice and also maybe by one. So we simply have the binary presentation of the number of apples from the end. To calculate the answer we should simply restore that value from the end and also calculate the total money grandma should have.

С++ solution by me.

С++ solution by unprost.

Complexity: O(p).

632B - Alice, Bob, Two Teams

The problem was suggested by Lewin Gan Lewin.

Let's calculate the prefix sums for all numbers (and store it in array s1) and for numbers with letter B (and store it in array s2). Now we can find the sum of all numbers in any segment in O(1) time and the sum of numbers with letter B.

Let's iterate over prefix or suffix to flip and calculate the sum in that case by formulas: sum(s1, 0, n - 1) + sum(s2, 0, i) - 2·sum(s1, 0, i) for prefixes and sum(s1, 0, n - 1) + sum(s2, i, n - 1) - 2·sum(s1, i, n - 1) for suffixes.

C++ solution by me.

Python solution by Lewin.

Complexity: O(n).

632C - The Smallest String Concatenation

The problem was suggested by Lewin Gan Lewin. The proof of the transitivity also belongs to him.

Let's sort all the strings by comparator a + b < b + a and concatenate them. Let's prove that it's the optimal answer. Let that operator be transitive (so if ). Consider an optimal answer with two strings in reverse order by that operator. Because of the transitivity of operator we can assume that pair of strings are neighbouring. But then we can swap them and get the better answer.

Let's prove the transitivity of operator. Consider the strings as the 26-base numbers. Then the relation a + b < b + a equivalent to . The last is simply the relation between real numbers. So we proved the transitivity of the relation a + b < b + a.

C++ solution by me.

Python solution by Lewin.

Complexity: O(nLlogn), where L is the maximal string length.

632D - Longest Subsequence

The problem was suggested by Denis Bezrukov pitfall.

Let cnt_x be the number of occurences of the number x in the given array (easy to see that we can ignore the numbers greater than m). Let's iterate over and 1 ≤ k, x·k ≤ m and increase the value in the position k·x in some array z by the value cnt_x. So the value z_l equals the number of numbers in the given array which divide l. Let's find the minimal l with the maximum value z_l (1 ≤ l ≤ m). Easy to see that the answer to the problem is the numbers which divide l.

Let's calculate the complexity of the solution. The number of the pairs (k, x) we can bound with the value .

C++ solution by me.

Java solution by pitfall.

Complexity: O(n + mlogm).

632E - Thief in a Shop

The problem was suggested by Alexey Chesnokov CleRIC.

Let k = 2, then it is the standard problem which can be solved by FFT (Fast Fourier Transform). The solution is the following: consider the polynomial which the i-th coefficient equals to one if and only if there is the number i in the given array. Let's multiply that polynomial by itself and find i for which the coefficient in square not equals to 0. Those values i will be in the answer. Easy to modificate the solution for the arbitrary k. We should simply calculate the k-th degree of the polynomial. The complexity will be WlogWlogk, where W is the maximal sum.

We can improve that solution. Instead of calculating the k-th degree of the polynomial we can calculate the k-th degree of the DFT of the polynomial. The only problem is the large values of the k-th degrees. We can't use FFT with complex numbers, because of the precision problems. But we can do that with NTT (Number-theoretic transform). But that solution also has a problem. It can happen that some coefficients became equals to zero modulo p, but actually they are not equal to zero. To get round that problem we can choose two-three random modules and get the complexity O(W(logW + logk)).

The main author solution has the complexity O(WlogWlogk) (FFT with complex numbers), the second solution has the same complexity, but uses NTT and the third solution has the improved complexity (but it was already hacked by halyavin).

С++ solution, complex FFT by me.

С++ solution, NTT by me.

С++ solution, improved NTT by me.

С++ solution by CleRIC.

P.S.: To get faster solution you should each time multiply the polynomials of the required degree, but not of the degree 2²⁰.

Complexity: O(WlogWlogk) or O(W(logW + logk)), depending the bravery of the coder :-)

UPD: It turns out that the first approach also has complexity O(W(logW + logk)). See below the comment of halyavin.

632F - Magic Matrix

The problem was suggested by Lewin Gan Lewin. The solution and proof also belongs to him.

Consider the undirected complete graph with n nodes, with an edge between nodes i, j with cost a_ij. Let B_ij denote the minimum possible value of the max edge of a path from i to j. We know that a_ij ≥ B_ij by definition.

If the matrix is magic, we can choose arbitrary k₁, k₂, ..., k_m such that a_ij ≤ max(a_i, k1, a_k1, k2, ..., a_km, j) by repeating invocations of the inequality given. Also, you can show that if this inequality is satisfied, then the matrix is magic (by choosing an m = 1 and k₁ arbitrary).

So, this shows that the matrix is magic if and only if a_ij ≤ B_ij. Thus, combining with a_ij ≥ B_ij, we have a_ij = B_ij.

We need a fast way to compute B_ij for all pairs i, j. This can be computed as the MST, as the path in the MST minimizes the max edge between all pairs of nodes. So, the algorithm works as follows. First, find the MST on the complete graph. Then, the matrix is magic if and only if the max edge on the path between i, j in the MST is exactly equal to a_i, j. Also you shouldn't forget to check symmetry of the matrix and diagonal for zeros.

P.S.: Unfortunately we couldn't increase the value n in this problem: the tests already had the size about 67MB and they couldn't be given with generator. So most of the users who solved this problem uses bitset-s. The complexity of their solution is , where b = 32 or b = 64.

C++ solution, binary lifts by me.

Java solution by Lewin.

Complexity: O(n²logn) or O(n²).

Hello, Codeforces!

Today is the first day of the spring and it's great!

Educational Codeforces Round 9 will take place on 01 march 2016 at 18:00 MSK for the first and the second divisions. You can read about educational rounds here and here. I should again notice the high density of contests and championships.

<This time it wasn't changed>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks.

</This time it wasn't changed>

The problemset again was totally suggested by Codeforces users. The problem А again was suggested by user unprost (be ready to see a long problem statement). The problem D suggested by Denis Bezrukov pitfall. Alexey Chesnokov CleRIC sent the problem E a long ago. The problems B, C and F was suggested by Lewin Gan Lewin.

Thanks a lot to them and all others who are sending the problems or just ideas of the problems!

The problems was prepared by me (Edvard Davtyan). Thanks to Maria Belova Delinur for checking the English statements. The problems was tested by the same users who suggested them: unprost, Alexey Chesnokov CleRIC and Lewin Gan Lewin. Thanks a lot to all of them!

I hope you will enjoy the problems!

Good luck and have fun!

UPD1: The first part of the contest is finished. You can hack solutions.

UPD2: There are some technical problems. The phase of open hacks will be opened later (several hours).

UPD3: Editorial is ready.

UPD4: The contest is finished. We will start system testing in a few minutes.

UPD5: TOP3 of hackers:

P_Nyagolov — 31 hacks

khadaev — 27 hacks

halyavin — 23 hacks

628A - Tennis Tournament

The problem was suggested by unprost.

Here you can simply model the process. Or you can note that after each match some player drops out. In total n - 1 players will drop out. So the first answer is (n - 1) * (2b + 1). Obviously the second answer is np.

С++ solution 1

С++ solution 2

Complexity: O(log²n), O(logn) or O(1) depends on the realization.

628B - New Skateboard

This is one of the problems suggested by Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A.

The key observation is that the number is divisible by 4 if and only if its last two digits forms a number divisible by 4. So to calculate the answer at first we should count the substrings of length one. Now let's consider pairs of consecutive digits. If they forms a two digit number that is divisible by 4 we should increase the answer by the index of the right one.

C++ solution

Complexity: O(n).

628C - Bear and String Distance

The problem was suggested and prepared by Kamil Debowski Errichto. He also wrote the editorial.

There is no solution if the given required distance is too big. Let's think what is the maximum possible distance for the given string s. Or the more useful thing — how to construct a string s' to maximize the distance? We can treat each letter separately and replace it with the most distant letter. For example, we should replace 'c' with 'z', and we should replace 'y' with 'a'. To be more precise, for first 13 letters of the alphabet the most distant letter is 'z', and for other letters it is 'a'.

Let's solve a problem now. We can iterate over letters and greedily change them. A word "greedily" means when changing a letter we don't care about the next letters. We generally want to choose distant letters, because we may not find a solution otherwise. For each letter s_i we change it into the most distant letter, unless the total distance would be too big. As we change letters, we should decrease the remaining required distance. So, for each letter s_i consider only letters not exceeding the remaining distance, and among them choose the most distant one. If you don't see how to implement it, refer to my C++ solution with comments.

Other C++ solution

Complexity: O(n).

628D - Magic Numbers

Kareem Mohamed Kareem_Mohamed suggested the simpler version of the problem.

Denote the answer to the problem f(a, b). Note that f(a, b) = f(0, b) - f(0, a - 1) or what is the same f(a, b) = f(0, b) - f(0, a) + g(a), where g(a) equals to one if a is a magic number, otherwise g(a) equals to zero. Let's solve the problem for the segment [0, n].

Here is described the standard technique for this kind of problems, sometimes it is called 'dynamic programming by digits'. It can be realized in a two ways. The first way is to iterate over the length of the common prefix with number n. Next digit should be less than corresponding digit in n and other digits can be arbitrary. Below is the description of the second approach.

Let z_ijk be the number of magic prefixes of length i with remainder j modulo m. If k = 0 than the prefix should be less than the corresponding prefix in n and if k = 1 than the prefix should be equal to the prefix of n (it can not be greater). Let's do 'forward dynamic programming'. Let's iterate over digit in position i. We should check that if the position is even than p should be equal to d, otherwise it cannot be equal to d. Also we should check for k = 1 p should be not greater than corresponding digit in n. Now let's see what will be the next state. Of course i' = i + 1. By Horner scheme j' = (10j + p) mod m. Easy to see that . To update the next state we should increase it: z_i'j'k' +  = z_ijk. Of course all calculations should be done modulo 10⁹ + 7.

C++ solution

Complexity: O(nm).

628E - Zbazi in Zeydabad

The problem was suggested by Ali Ahmadi Kuzey.

Let's precalculate the values zl_ij, zr_ij, zld_ij — the maximal number of letters 'z' to the left, to the right and to the left-down from the position (i, j). It's easy to do in O(nm) time. Let's fix some cell (i, j). Consider the value c = min(zl_ij, zld_ij). It's the maximum size of the square with upper right ceil in (i, j). But the number of z-patterns can be less than c. Consider some cell (x, y) diagonally down-left from (i, j) on the distance no more than c. The cells (i, j) and (x, y) forms z-pattern if y + zr_xy > j.

Let's maintain some data structure for each antidiagonal (it can be described by formula x + y) that can increment in a point and take the sum on a segment (Fenwick tree will be the best choice for that). Let's iterate over columns j from the right to the left and process the events: we have some cell (x, y) for which y + zr_xy - 1 = j. In that case we should increment the position y in the tree number x + y by one. Now we should iterate over the cells (x, y) in the current column and add to the answer the value of the sum on the segment from j - c + 1 to j in the tree number i + j .

С++ solution

Complexity: O(nmlogm).

628F - Bear and Fair Set

The problem was suggested and prepared by Kamil Debowski Errichto. He also wrote the editorial.

At the beginning, to make things simpler, we should add a query (hint) with upTo = b, quantity = n, and then sort queries by upTo. Sorted queries (hints) divide interval [1, b] into q disjoint intervals. For each interval we know how many elements should be there.

Let's build a graph and find a max flow there. The answer is "YES" only if the flow is n.

• The first group A contains 5 vertices, representing possible remainders.
• The second group B contains q vertices, representing intervals.

Each vertex from A should be connected with the source by an edge with capacity n / 5. Each vertex from B should be connected with the sink by an edge with capacity equal to the size of the interval. Between each vertex x from A and y from B should be an edge with capacity equal to the number of numbers in the interval y, giving remainder x when divided by 5.

You can also use see that it's similar to finding matching. In fact, we can use the Hall's marriage theorem. For each of 2⁵ sets of vertices from A (sets of remainders) iterate over intervals and count how many numbers we can take from [1, b] with remainders from the fixed set of remainders.

The implementation with the Hall's theorem: C++ solution.

Complexity: O(2^Cn). In our problem C = 5.

Hello, Codeforces!

Educational Codeforces Round 8 will take place on 19 February 2016 at 18:00 MSK for the first and the second divisions. You can read about educational rounds here and here. I hope that the high density of contests on Codeforces will not startle you and you will participate in ER8.

<The phrase about simple problems is added in the end>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks.

</The phrase about simple problems is added in the end>

This time (for the first time) the problemset was totally suggested by Codeforces users. The problem А suggested by user unprost. The problem B was taken form the problems sent by Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A. The problem D suggested by Kareem Mohamed Kareem_Mohamed (but I made it more difficult to make it more interesting for you :-)). The problem E sent Ali Ahmadi Kuzey. The problems C and F are suggested by Kamil Debowski Errichto.

Thanks a lot to them and all others who are sending the problems or just ideas of the problems!

This time the problems wasn't prepared only by me (Edvard Davtyan). Thanks a lot to Kamil Debowski Errichto who not only suggested the problems C and F, but also prepared them. Thanks to Maria Belova Delinur for checking the English statements. Also thanks a lot to Ali Ahmadi Kuzey who helped me with testing of some problems.

A few words about the problems: A) Easy problem with the long statement; B) I hope you will not write hard solution; C) It's interesting; D) It's a little technical, but contains very useful technique; E) I like this problem; F) Very cool problem if you will not solve during the contest I recommend to solve it in practice.

Good luck and have fun!

UPD1: The first phase of the contest finished. Hacks started. The editorial is ready.

By the reason that all the problems of Errichto are about a bears, below you can see the illustration for the problem C (it seems Limak is the leftmost):

622A - Infinite Sequence

Let's decrease n by one. Now let's determine the block with the n-th number. To do that let's at first subtract 1 from n, then subtract 2, then subtract 3 and so on until we got negative n. The number of subtractions will be the number of the block and the position in the block will be the last nonnegative number we will get.

С++ solution

Complexity: .

622B - The Time

In this problem we can simply increase a times the current time by one minute (after each increasing we should check the hours and the minutes for overflow).

Another solution is to use the next formulas as the answer: .

C++ solution 1

C++ solution 2

Complexity: O(a) or O(1).

622C - Not Equal on a Segment

This problem is a simplified version of the problem suggested by Mohammad Nematollahi Deemo.

This problem can be solved differently. For example you can use some data structures or sqrt-decomposition technique. But it is not required. We expected the following simple solution from the participants. Let's preprocess the following values p_i — the position of the first element to the left from the i-th element such that a_i ≠ a_pi. Now to answer to the query we should check if a_r ≠ x then we have the answer. Otherwise we should check the position p_r.

C++ solution

Complexity: O(n).

622D - Optimal Number Permutation

This problem was suggested by Aleksa Plavsic allllekssssa.

Let's build the answer with the sum equal to zero. Let n be even. Let's place odd numbers in the first half of the array: the number 1 in the positions 1 and n, the number 3 in the positions 2 and n - 1 and so on. Similarly let's place even numbers in the second half: the number 2 in the position n + 1 and 2n - 1, the number 4 in the positions n + 2 and 2n - 2 and so on. We can place the number n in the leftover positions. We can build the answer for odd n in a similar way.

Easy to see that our construction will give zero sum.

C++ solution

Complexity: O(n).

622E - Ants in Leaves

This problem was suggested by Aleksa Plavsic allllekssssa.

Easy to see that the answer is equal to the answer over all sons of the root plus one. Now let's solve the problem independently for each son v of the root. Let z be the array of the depths of all leaves in the subtree of the vertex v. Let's sort z. Statement 1: it's profitable to lift the leaves in order of their appearing in z. Statement 2: denote a_x — the time of appearing the x-th leaf in the vertex v, let's consider the leaves z_i and z_i + 1 then a_zi + 1 ≥ a_zi + 1. Statement 3: a_zi + 1 = max(d_zi + 1, a_zi + 1), where d_x is the depth of the x-th leaf in the subtree of the vertex v. The last statement gives us the solution for the problem: we should simply iterate over z from left to right and recalculate the array a by formula from the third statement. All statements can be easily proved and it's recommended to do by yourself to understand better the idea of the solution.

С++ solution

Complexity: O(nlogn).

622F - The Sum of the k-th Powers

This problem was suggested by Ivan Popovich NVAL.

Statement: the function of the sum is a polynomial of degree k + 1 over variable n. This statement can be proved by induction (to make step you should take the derivative).

Denote P_x the value of the sum for n = x. We can easily calculate the values of P_x for x from 0 to k + 1 in O(klogk) time. If n < k + 2 then we already have the answer. Otherwise let's use Lagrange polynomial to get the value of the sum for the given value n.

The Largange polynomial have the following form: . In our case x_i = i - 1 and y_i = P_xi.

To calculate P(n) in a linear time we should use that x_i + 1 - x_i = x_j + 1 - x_j for all i, j < n. It's help us because with that property we can recalculate the inner product for i + 1 from the inner product for i simply by multiplying by two values and dividing by two values. So we can calculate the sum in linear time over k.

С++ solution

Complexity: O(klog MOD) (logk appeared because we should find the inverse element in the field modulo MOD = 10⁹ + 7).

Hello, Codeforces!

Educational Codeforces Round 7 will take place on 10 February 2016 at 18:00 MSK for the first and second divisions. You can read about educational rounds here and here.

<This paragraph was modified last time>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

</This paragraph was modified last time>

Thanks a lot to Aleksa Plavsic allllekssssa who suggested the problems D, E and Ivan Popovich NVAL for the problem F. Also thanks to Mohammad Nematollahi Deemo who suggested the problem that was highly simplified and will be under the letter C.

The round was prepared by me, Edvard Davtyan. Thanks a lot to MikeMirzayanov we invented the problems A, B and C together. Also thanks to Maria Belova Delinur for checking the English statements, Aleksa Plavsic allllekssssa and Ivan Popovich for testing the problems.

We tried to make the problems easy but interesting. I think that the problems is mathematized a little. I hope you will enjoy the problems!

Good luck and have fun!

P.S.: The Codeforces Educational Rounds was recognized by Snarknews as the best project in competitive programming in 2015 (the picture below is the prize).

UPD1: The first phase of the contest is ended. You can hack any other solution.

UPD2: The editorial is ready.

UPD3: The round is over, the results is final.

620A - Professor GukiZ's Robot

Easy to see that the answer is max(|x₁ - x₂|, |y₁ - y₂|).

С++ solution

Complexity: O(1).

620B - Grandfather Dovlet’s calculator

Let's simply iterate over all the values from a to b and add to the answer the number of segments of the current value x. To count the number of segments we should iterate over all the digits of the number x and add to the answer the number of segments of the current digit d. These values can be calculated by the image from the problem statement and stored in some array in code.

C++ solution

Complexity: O((b - a)logb).

620C - Pearls in a Row

Let's solve the problem greedily. Let's make the first segment by adding elements until the segment will be good. After that let's make the second segment in the same way and so on. If we couldn't make any good segment then the answer is  - 1. Otherwise let's add all uncovered elements at the end to the last segment. Easy to prove that our construction is optimal: consider the first two segments of the optimal answer, obviously we can extend the second segment until the first segment will be equal to the first segment in our construction.

C++ solution

Complexity: O(nlogn).

620D - Professor GukiZ and Two Arrays

We can process the cases of zero or one swap in O(nm) time. Consider the case with two swaps. Note we can assume that two swaps will lead to move two elements from a to b and vice versa (in other case it is similar to the case with one swap). Let's iterate over all the pairs of the values in a and store them in some data structure (in C++ we can user map). Now let's iterate over all the pairs b_i, b_j and find in out data structure the value v closest to the value x = s_a - s_b + 2·(b_i + b_j) and update the answer by the value |x - v|. Required sum we can find using binary search by data structure (*map* in C++ has lower_bound function).

C++ solution

Сложность: O((n² + m²)log(n + m)).

620E - New Year Tree

Let's run dfs on the tree and write out the vertices in order of their visisiting by dfs (that permutation is called Euler walk). Easy to see that subtree of any vertex is a subsegment of that permutation. Note that the number of different colours is 60, so we can store the set of colours just as mask of binary bits in 64-bit type (*long long* in C++, long in Java). Let's build the segment tree over the permutation which supports two operations: paint subsegment by some colour and find the mask of colours of some segment.

С++ solution

Complexity: O(nlogn).

620F - Xors on Segments

We gave bad constraints to this problem so some participants solved it in O(n² + m) time.

Note that . The values f(0, x) can be simply precomputed. Also you can notice that the value f(0, x) is equal to x, 1, x + 1, 0 depending on the value x modulo 4.

Let's use Mo's algorithm: we should group all the queries to blocks by the left end and sort all the queries in each block by the right end. Let r be the maximal left end inside the current group then all left ends will be in distance not greater than from r and right ends will be in nondecreasing order, so we can move the right end by one (total we will made no more than n movements in each block). During moving of the right end inside some group from the value r + 1 to the value of the current right end we will maintain two tries: the first for the values f(0, x - 1) and the second for the values f(0, x), in the first we will maintain the minimal value of x, in the second — the maximal. After adding some values to the trie we should find the maximal value that can be formed by the current value x. To do that we should go down in the first trie maintaining the invariant that in the current subtree the minimal value is not greater than x. Each time we should go by the bit that is not equal to the corresponding bit in x (if we can do that, otherwise we should go by the other bit). In the second trie we should do the same thing with the difference that we should maintain the invariant that the maximal value in the current subtree is not less than the value x. After moving the right end we should iterate from the left end of the query to r and update the answer (without adding the current value to the tries). Also after that all we should iterate over all the queries and with new empty tries iterate from the left end to r, add the current values to the tries and update the answer.

С++ solution: in this code the trie number 0 corresponds to the second trie and the trie number 1 corresponds to the first trie.

Complexity: .

Hello, Codeforces!

Educational Codeforces Round 6 will take place on 21 January 2016 at 18:00 MSK for the first and second divisions. You can read about educational rounds here and here.

<Your Ad Could Be Here>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

</Your Ad Could Be Here>

Thanks a lot to Aleksa Plavsic allllekssssa who suggested several problems, two of them you will see on the round (the problems D and F). Also thanks to Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A. They are together suggested five problems, two of them you will see on the round (the problems B and E).

As usual the round was prepared by me, Edvard Davtyan. Thanks a lot to MikeMirzayanov we invented the problems A and C together. Also thanks to Maria Belova Delinur who will check English statements and Aleksa Plavsic allllekssssa who help me with problem testing and have constantly been in touch.

The first problem is pretty simple, so I'm waiting fast accepteds from you. The last problem is pretty difficult, so respect to all particiants who will solve it. I hope you will enjoy the problems!

Good luck and have fun!

UPD 1: I forgot to thank all other users who already sent me the ideas for the problems. I'll try to give that problems to the next rounds.

UPD 2: The main part of the contest is finished. The phase of hacks is started.

UPD 3: The editorial is ready.

UPD 4: The round is over, the results is final.

616A - Comparing Two Long Integers

Note that solutions in Java with BigInteger class or input() function in Python2 will fail in this problem. The reason is the next: standard objects stores numbers not in decimal system and need a lot of time to convert numbers from decimal system. Actually they are working in O(n²), where n is the legth of the number.

To solve this problem you should simply read the numbers to strings and add leading zeroes to the shorter one until the numbers will be of the same length. After that you should simply compare them alphabetically.

С++ solution

Python solution

Complexity: O(n).

616B - Dinner with Emma

Firstly you should find the minimum value in each row and after that you should find the maximum value over that minimums. It's corresponding to the strategy of Jack and Emma.

C++ solution

Complexity: O(nm).

616C - The Labyrinth

Let's enumerate all the connected components, store their sizes and for each empty cell store the number of it's component. It can be done with a single dfs. Now the answer for some impassable cell is equal to one plus the sizes of all different adjacent connected components. Adjacent means the components of cells adjacent to the current impassable cell (in general case each unpassable cell has four adjacent cells).

C++ solution

Complexity: O(nm).

616D - Longest k-Good Segment

This problem is given because on the Codeforces pages we often see questions like "What is the method of the two pointers?". This problem is a typical problem that can be solved using two pointers technique.

Let's find for each left end l the maximal right end r that (l, r) is a k-good segment. Note if (l, r) is a k-good segment then (l + 1, r) is also a k-good segment. So the search of the maximal right end for l + 1 we can start from the maximal right end for l. The only thing that we should do is to maintain in the array cnt_x for each number x the number of it's occurrences in the current segment (l, r) and the number of different numbers in (l, r). We should move the right end until the segment became bad and then move the left end. Each of the ends l, r will be moved exactly n times.

C++ solution

Complexity: O(n).

616E - Sum of Remainders

Unfortunately my solution for this problem had overflow bug. It was fixed on contest. Even so I hope you enjoyed the problem because I think it's very interesting.

Let's transform the sum . Note that the last sum can be accumulated to only value min(n, m), because for i > n all the values will be equal to 0.

Note in the last sum either or . Let's carefully accumulate both cases. The first sum can be simply calculated by iterating over all . We will accumulate the second sum independently for all different values . Firstly we should determine for which values i we will have the value . Easy to see that for the values i from the interval . Also we can note that the sum of the second factors in with fixed first factor can be calculaed in constant time — it's simply a sum of arithmetic progression . So we have solution with complexity .

С++ solution

Complexity: .

616F - Expensive Strings

This problem was prepared by Grigory Reznikow vintage_Vlad_Makeev. His solution uses suffix array.

This problem is a typical problem for some suffix data structure. Four competitors who solved this problem during the contest used suffix automaton and one competitor used suffix tree. My own solution used suffix tree so I'll describe solution with tree (I think it's simple except of the building of the tree).

Let's build the new string by concatenation of all strings from input separating them by different separators. The number of separators is O(n) so the alphabet is also O(n). So we should use map<int, int> to store the tree and the complexity is increased by O(logn). Let's build the suffix tree for the new string. Let's match all the separators to the strings from the left of the separator. Let's run dfs on the suffix tree that doesn't move over separators and returns the sum of the costs of the strings matched to the separators from the subtree of the current vertex. Easy to see that we should simply update the answer by the product of the depth of the current vertex and the sum in the subtree of the current vertex.

С++ solution

Complexity: O(nlogn).

Hi, Codeforces!

Happy New Year! Holidays and 2015 year have passed and year 2016 is ahead. I wish you good luck in programming competitions and achieving all of your goals this year.

Educational Codeforces Round 5 will take place on 11 January 2016 at 18:00 MSK for the first and second divisions. You can read about educational rounds here and here.

<A year has passed, but paragraph remains unchanged.>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

</A year has passed, but paragraph remains unchanged.>

Thanks a lot to Grigory Reznikow vintage_Vlad_Makeev who prepared a good problem (the problem F in ER 5). You can send to me some ideas of problems or maybe already prepared problems that you can't use in rounds or official competitions.

As usual the round was prepared by me, Edvard Davtyan. Thanks a lot to MikeMirzayanov for helping to invent the problems. Also thanks in advance to Maria Belova Delinur who will check English statements.

I think the problems is not difficult (except maybe for problem F). I hope you will enjoy the problems and solve all of them!

Good luck and have fun!

UPD 1: Coding phase is finished. You can hack other solutions for 24 hours.

UPD 2: The editorial is ready.

UPD 3: During the phase of hacks we found the following: the same solutions on Python2 and Python3 works differently on different large tests. For example, some of Python3 solutions works very slow on tests with only zeros, but Python2 works very slow on tests with nines. Some of solutions works in around one second so we decided to increase the time limit for the problem A to 2 seconds. All the solutions will be rejudged soon on the complete testset.

UPD 4: The round is over. All solutions will be rejudged soon on the complete testset (includes the hacks).

612A - The Text Splitting

Let's fix the number a of strings of length p and the number b of strings of length q. If a·p + b·q = n, we can build the answer by splitting the string s to a parts of the length p and b parts of the length q, in order from left to right. If we can't find any good pair a, b then the answer doesn't exist. Of course this problem can be solved in linear time, but the constraints are small, so you don't need linear solution.

Complexity: O(n²).

612B - HDD is Outdated Technology

You are given the permutation f. Let's build another permutation p in the following way: p_fi = i. So the permutation p defines the number of sector by the number of fragment. The permutation p is called inverse permutation to f and denoted f^- 1. Now the answer to problem is .

Complexity: O(n).

612C - Replace To Make Regular Bracket Sequence

If we forget about bracket kinds the string s should be RBS, otherwise the answer doesn't exist. If the answer exists each opening bracket matches to exactly one closing bracket and vice verse. Easy to see that if two matching brackets have the same kind we don't need to replace them. In other case we can change the kind of the closing bracket to the kind of the opening. So we can build some answer. Obviously the answer is minimal, because the problems for some pair of matching pairs are independent and can be solved separately.

The only technical problem is to find the matching pairs. To do that we should store the stack of opening brackets. Let's iterate from left to right in s and if the bracket is opening, we would simply add it to the stack. Now if the bracket is closing there are three cases: 1) the stack is empty; 2) at the top of the stack is the opening bracket with the same kind as the current closing; 3) the kind of the opening bracket differs from the kind of the closing bracket. In the first case answer doesn't exist, in the second case we should simply remove the opening bracket from the stack and in the third case we should remove the opening bracket from the stack and increase the answer by one.

Complexity: O(n).

612D - The Union of k-Segments

Let's create two events for each segment l_i is the time of the segment opening and r_i is the time of the segment closing. Let's sort all events by time, if the times are equal let's sort them with priority to opening events. In C++ it can be done with sorting by standard comparator of vector<pair<int, int>> events, where each element of events is the pair with event time and event type ( - 1 for opening and  + 1 for closing).

Let's iterate over events and maintain the balance. To do that we should simply decrease the balance by the value of the event type. Now if the balance value equals to k and before updating it was k - 1 then we are in the left end of some segment from the answer. If the balance equals to k - 1 and before updating it was k then we are in the right end of the segment from the answer. Let's simply add segment [left, right] to the answer. So now we have disjoint set of segments contains all satisfied points in order from left to right. Obviously it's the answer to the problem.

Complexity: O(nlogn).

612E - Square Root of Permutation

Consider some permutation q. Let's build by it the oriented graph with edges (i, q_i). Easy to see (and easy to prove) that this graph is the set of disjoint cycles. Now let's see what would be with that graph when the permutation will be multiplied by itself: all the cycles of odd length would remain so (only the order of vertices will change, they will be alternated), but the cycles of even length will be split to the two cycles of the same length. So to get the square root from the permutation we should simply alternate (in reverse order) all cycles of the odd length, and group all the cycles of the same even length to pairs and merge cycles in each pair. If it's impossible to group all even cycles to pairs then the answer doesn't exist.

Complexity: O(n).

612F - Simba on the Circle

The author solution for this problem uses dynamic programming. I think that this problem can't be solved by greedy ideas. Let's calculate two dp's: z1_i is the answer to the problem if all numbers less than a_i are already printed, but the others are not; and z2_i is the answer to the problem if all numbers less than or equal to a_i are already printed, but the others are not. Let's denote d_ij — the least distance between i and j on the circular array and od_ij is the distance from i to j in clockwise order. Easy to see that z2_i = min_j(z_j + d_ij) for all j such that the value a_j is the least value greater than a_i. Now let's calculate the value z1_i. Consider all elements equals to a_i (in one of them we are). If there is only one such element then z1_i = z2_i. Otherwise we have two alternatives: to move in clockwise or counterclockwise direction. Let we are moving in clockwise direction, the last element from which we will write out the number would be the nearest to the i element in counterclockwise direction, let's denote it u. Otherwise at last we will write out the number from the nearest to the i element in clockwise direction, let's denote it v. Now z1_i = min(z2_u + od_iu, z2_v + od_vi). Easy to see that the answer to the problem is min_i(z1_i + d_si), over all i such that a_i is the smallest value in array and s is the start position.

Additionally you should restore the answer. To do that, on my mind, the simplest way is to write the recursive realization of dp, test it carefully and then copy it to restore answer (see my code below). Of course, it's possible to restore the answer without copy-paste. For example, you can add to your dp parameter b which means it's need to restore answer or not.

Complexity: O(n²).

Code