Hello Codeforces!

On April 30, 17:35 MSK Educational Codeforces Round 43 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for Div. 2. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 problems and 2 hours to solve them.

The problems were prepared by Mikhail awoo Piklyaev, Roman Roms Glazov, Adilbek adedalic Dalabaev and me.

We'd like to thank Ivan BledDest Androsov and Maksim Neon Mescheryakov for the help in preparing the round.

Good luck to all participants!

UPD: The round will contain 6 problems instead of 7.

UPD2: Editorial

Congratulations to the winners:

Congratulations to the best hackers:

777 successful hacks and 656 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

961A - Tetris

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	int n, m;
	cin >> n >> m;
	vector<int> cnt(n);

	for (int i = 0; i < m; ++i) {
		int col;
		cin >> col;
		++cnt[col - 1];
	}
	
	cout << *min_element(cnt.begin(), cnt.end()) << endl;
	
	return 0;
}

961B - Lecture Sleep

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	int n, k;
	scanf("%d %d", &n, &k);
	
	vector<int> a(n);
	vector<int> t(n);
	
	int overall = 0;
	
	for (int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	for (int i = 0; i < n; ++i)
		scanf("%d", &t[i]);
		
	vector<int> pr(n);
	for (int i = 0; i < n; ++i) {
		if (i) pr[i] += pr[i - 1];
		if (t[i] == 0) pr[i] += a[i];
		else overall += a[i];
	}
	
	int add = 0;
	for (int i = k - 1; i < n; ++i)
		add = max(add, pr[i] - (i >= k ? pr[i - k] : 0));
	
	printf("%d\n", overall + add);
	
	return 0;
}

961C - Chessboard

#include <bits/stdc++.h>

using namespace std;

const int N = 109;

int n;
string a[4][N];

int main() {
	cin >> n;
	for(int k = 0; k < 4; ++k)
		for(int i = 0; i < n; ++i){
			cin >> a[k][i];
				for(int j = 0; j < n; ++j)
			    a[k][i][j] -= '0';
		}
	
	vector <int> v;
	for(int k = 0; k < 4; ++k){
		int sum = 0;
		for(int i = 0; i < n; ++i)
			for(int j = 0; j < n; ++j)
				if((i + j) % 2 != a[k][i][j])
					++sum;
		v.push_back(sum);
	}
	
	int res = int(1e9);
	vector <int> perm;
	for(int k = 0; k < 4; ++k) perm.push_back(k);
	do{
		int sum = 0;
		for(int k = 0; k < 4; ++k){
			int id = perm[k];
			if(k & 1)
				sum += v[id];
			else
				sum += n * n - v[id];
		}
		
		res = min(res, sum);
	}while(next_permutation(perm.begin(), perm.end()));

	cout << res << endl;
}

961D - Pair Of Lines

#include <bits/stdc++.h>

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

#define all(a) (a).begin(), (a).end()
#define sz(a) int(a.size())
#define mp make_pair

#define x first
#define y second

using namespace std;

typedef long long li;
typedef pair<int, int> pt;

inline pt operator -(const pt &a, const pt &b) {
	return {a.x - b.x, a.y - b.y};
}

inline li cross(const pt &a, const pt &b) {
	return a.x * 1ll * b.y - a.y * 1ll * b.x;
}

const int N = 200 * 1000 + 555;

int n;
pt p[N];

inline bool read() {
	if(!(cin >> n))
		return false;
	
	fore(i, 0, n)
		scanf("%d%d", &p[i].x, &p[i].y);
	return true;
}

bool used[N];

bool check() {
	int i1 = -1, i2 = -1;
	fore(i, 0, n) {
		if(used[i])
			continue;
		if(i1 == -1)
			i1 = i;
		else if(i2 == -1)
			i2 = i;
	}
	if(i2 == -1)
		return true;
		
	fore(i, 0, n) {
		if(used[i])
			continue;
		if(cross(p[i2] - p[i1], p[i] - p[i1]) != 0)
			return false;
	}
	return true;
}

bool check2(pt a, pt b) {
	memset(used, 0, sizeof used);
	fore(i, 0, n)
		if(cross(b - a, p[i] - a) == 0)
			used[i] = 1;
	return check();
}

inline void solve() {
	if(n <= 2) {
		puts("YES");
		return;
	}
	
	if(check2(p[0], p[1]) || check2(p[0], p[2]) || check2(p[1], p[2]))
		puts("YES");
	else
		puts("NO");
}

int main(){
	if(read()) {
		solve();
	}
	return 0;
}

961E - Tufurama

#include <bits/stdc++.h>

using namespace std;

const int N = 200 * 1000 + 9;

int n;
int a[N];
int f[N];
vector <int> v[N];

void upd(int pos, int d){
	for(; pos < N; pos |= pos + 1)
		f[pos] += d;
}

int get(int pos){
	int res = 0;
	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
		res += f[pos];
	return res;
}

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i){
		scanf("%d", a + i);
		--a[i];
	}
		
	for(int i = 0; i < n; ++i){
		if(a[i] < N)
			v[a[i]].push_back(i);
		upd(i, 1);
	}
	
	long long res = 0;
	for(int i = 0; i < n; ++i){
		int to = min(N - 1, a[i]);
		res += get(to);
		for(auto x : v[i])
			upd(x, -1);
	}
	
	for(int i = 0; i < n; ++i)
	    if(i <= a[i])
	        --res;
    assert(res % 2 == 0);
    
	cout << res / 2 << endl;
}

961F - k-substrings

#include <bits/stdc++.h>

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

#define all(a) (a).begin(), (a).end()
#define sz(a) int(a.size())
#define mp make_pair

#define x first
#define y second

using namespace std;

typedef pair<int, int> pt;

const int LOGN = 21;
const int N = 1000 * 1000 + 555;

int n;
string s;

inline bool read() {
	if(!(cin >> n))
		return false;
	
	char buf[N];
	assert(scanf("%s", buf) == 1);
	s = buf;
	return true;
}

pair<pt, int> d[N], curP[N];
int szd = 0;

int cnt[N], szcnt;
int rdp[N];

inline void radix_sort() {
	fore(k, 0, 2) {
		szcnt = 0;
		fore(i, 0, szd) {
			int val = k == 0 ? d[i].x.y : d[i].x.x;
			while(szcnt <= val)
				cnt[szcnt++] = 0;
			cnt[val]++;
		}
		int sum = 0;
		fore(i, 0, szcnt) {
			rdp[i] = sum;
			sum += cnt[i];
		}
		
		fore(i, 0, szd) {
			int val = k == 0 ? d[i].x.y : d[i].x.x;
			curP[rdp[val]++] = d[i];
		}
		fore(i, 0, szd)
			d[i] = curP[i];
	}
}

int c[N], id[N];
int lcp[N];

int lg[N];
int st[LOGN][N];

void precalc() {
	s += '$';
	for(int len = 1; len < 2 * sz(s); len <<= 1) {
		szd = 0;
		fore(i, 0, sz(s)) {
			int sh = len >> 1;
			d[szd++] = {len == 1 ? mp((int)s[i], 0) : mp(c[i], c[(i + sh) % sz(s)]), i};
		}
		radix_sort();
		
		c[d[0].y] = 0;
		fore(i, 1, szd)
			c[d[i].y] = c[d[i - 1].y] + (d[i - 1].x != d[i].x);
		
		if(c[d[szd - 1].y] == sz(s) - 1)
			break;
	}
	
	fore(i, 0, sz(s)) {
		c[i]--;
		if(c[i] >= 0) id[c[i]] = i;
	}
	s.pop_back();
	
	int l = 0;
	fore(i1, 0, n) {
		l = max(l - 1, 0);
		if(c[i1] == n - 1)
			continue;
		
		int i2 = id[c[i1] + 1];
		while(i1 + l < n && i2 + l < n && s[i1 + l] == s[i2 + l])
			l++;
		lcp[c[i1]] = l;
	}
	
	lg[0] = 0;
	fore(i, 1, N) {
		lg[i] = lg[i - 1];
		if((1 << (lg[i] + 1)) <= i)
			lg[i]++;
	}
	
	fore(pw, 0, LOGN) {
		if(pw == 0) {
			fore(i, 0, n)
				st[pw][i] = lcp[i];
			continue;
		}
		fore(i, 0, n) {
			st[pw][i] = st[pw - 1][i];
			if(i + (1 << (pw - 1)) < n)
				st[pw][i] = min(st[pw][i], st[pw - 1][i + (1 << (pw - 1))]);
		}
	}
}

inline int getMin(int l, int r) {
	if(l >= r) swap(l, r);
	
	int len = lg[r - l];
	return min(st[len][l], st[len][r - (1 << len)]);
}

inline bool eq(int i1, int i2, int l) {
	if(i1 == i2) return true;
	return getMin(c[i1], c[i2]) >= l;
}

int l[N], mx[N];

inline void solve() {
	precalc();
	
	fore(i, 0, n / 2) {
		int c1 = i, c2 = n - 1 - i;
		if(s[c1] != s[c2]) {
			l[i] = -1;
			continue;
		}
		int lf = 0, rg = min(c1, n - 1 - c2) + 1;
		while(rg - lf > 1) {
			int mid = (lf + rg) >> 1;
			
			if(eq(c1 - mid, c2 - mid, 2 * mid + 1))
				lf = mid;
			else
				rg = mid;
		}
		l[i] = lf;
	}
	
	fore(i, 0, n / 2) {
		if(l[i] < 0)
			continue;
		mx[i - l[i]] = max(mx[i - l[i]], 2 * l[i] + 1);
	}
	fore(i, 1, n / 2)
		mx[i] = max(mx[i], mx[i - 1] - 2);

	fore(i, 0, (n + 1) / 2) {
		if(i) printf(" ");
		printf("%d", mx[i] == 0 ? -1 : mx[i]);
	}
	puts("");
}

int main(){
	if(read()) {
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

#define all(a) (a).begin(), (a).end()
#define sz(a) int(a.size())
#define mp make_pair

#define x first
#define y second

using namespace std;

typedef long long li;

const li MOD = li(1e18) + 3;
const li BASE = 1009;

inline li norm(li a) {
	while(a >= MOD)
		a -= MOD;
	while(a < 0)
		a += MOD;
	return a;
}

inline li mul(li a, li b) {
	li m = ((long double)(a) * b) / MOD;
	return norm(a * b - m * MOD);
}

const int N = 1000 * 1000 + 555;

int n;
string s;

inline bool read() {
	if(!(cin >> n))
		return false;
	
	char buf[N];
	assert(scanf("%s", buf) == 1);
	s = buf;
	return true;
}

li h[N], pw[N];

inline void precalc() {
	h[0] = 0;
	fore(i, 0, n)
		h[i + 1] = norm(mul(h[i], BASE) + s[i] - 'a' + 1);
		
	pw[0] = 1;
	fore(i, 1, N)
		pw[i] = mul(pw[i - 1], BASE);
}

inline li getHash(int l, int r) {
	return norm(h[r] - mul(h[l], pw[r - l]));
}

inline bool eq(int i1, int i2, int l) {
	if(i1 == i2) return true;
	return getHash(i1, i1 + l) == getHash(i2, i2 + l);
}

int l[N], mx[N];

inline void solve() {
	precalc();
	
	fore(i, 0, n / 2) {
		int c1 = i, c2 = n - 1 - i;
		if(s[c1] != s[c2]) {
			l[i] = -1;
			continue;
		}
		int lf = 0, rg = min(c1, n - 1 - c2) + 1;
		while(rg - lf > 1) {
			int mid = (lf + rg) >> 1;
			
			if(eq(c1 - mid, c2 - mid, 2 * mid + 1))
				lf = mid;
			else
				rg = mid;
		}
		l[i] = lf;
	}
	
	fore(i, 0, n / 2) {
		if(l[i] < 0)
			continue;
		mx[i - l[i]] = max(mx[i - l[i]], 2 * l[i] + 1);
	}
	fore(i, 1, n / 2)
		mx[i] = max(mx[i], mx[i - 1] - 2);

	fore(i, 0, (n + 1) / 2) {
		if(i) printf(" ");
		if(mx[i] == 0) mx[i] = -1;
		printf("%d", mx[i]);
	}
	puts("");
}

int main(){
	if(read()) {
		solve();
	}
	return 0;
}

961G - Partitions

#include <bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) fore(i, 0, n)

const int MOD = int(1e9) + 7;

inline int norm(int a) {
	while(a >= MOD)
		a -= MOD;
	while(a < 0)
		a += MOD;
	return a;
}

inline int mul(int a, int b) {
	return int((a * 1ll * b) % MOD);
}

inline int binPow(int a, int k) {
	int ans = 1;
	while(k > 0) {
		if(k & 1) ans = mul(ans, a);
		a = mul(a, a);
		k >>= 1;
	}
	return ans;
}

const int N = 200 * 1000 + 555;

int f[N], inf[N];

void precalc() {
	f[0] = inf[0] = 1;
	fore(i, 1, N) {
		f[i] = mul(f[i - 1], i);
		inf[i] = mul(inf[i - 1], binPow(i, MOD - 2));
	}
}

int n, k, w[N];

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

inline int c(int n, int k) {
	if(k > n || n < 0) return 0;
	if(k == 0 || n == k) return 1;
	
	return mul(f[n], mul(inf[n - k], inf[k]));
}

inline int s(int n, int k) {
	if(n == 0) return k == 0;
	if(k == 0) return n == 0;
	
	int ans = 0, sg[2] = {1, MOD - 1};
	forn(cnt, k)
		ans = norm(ans + mul(sg[cnt & 1], mul(c(k, cnt), binPow(k - cnt, n))));
	return mul(ans, inf[k]);
}

inline void solve() {
	int sum = 0;
	forn(i, n)
		sum = norm(sum + w[i]);
		
	int s0 = s(n, k);
	int s1 = mul(n - 1, s(n - 1, k));
	
	cout << mul(sum, norm(s0 + s1)) << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	precalc();
	
	assert(read());
	solve();

#ifdef _DEBUG
	cerr << "TIME = " << clock() << endl;
#endif
	return 0;
}

Hello Codeforces!

On April 04, 17:05 MSK Educational Codeforces Round 41 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for Div. 2. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev and me.

We'd like to thank Mikhail awoo Piklayev and Ivan BledDest Androsov for the help in preparing the round.

Good luck to all participants!

UPD Editorial

UPD2

Congratulations to the winners:

Congratulations to the best hackers:

518 successful hacks and 491 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Hello Codeforces!

On January 13, 16:05 MSK Educational Codeforces Round 36 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be (traditionally now) rated for Div. 2. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Mikhail awoo Piklyaev, Ivan BledDest Androsov, Sergey sslotin Slotin and me.

Good luck to all participants!

I also have a message from our partners, Harbour.Space University:

As we get ready to dive into the second week of the year, we want to update you all on the upcoming Hello India x Russia Programming Bootcamp! So far 25 teams have registered, with more signing up daily.

As a reminder, the boot camp will take place from March 22nd to March 30th, 2018, at the Amrita School of Engineering campus, India. The Coordinator of the Programming Committee, and head coach will be two time ACM-ICPC world vice-champion Gleb GlebsHP Evstropov.

You can find more information and registration, click here

For those of you who need financial support for the boot camp, please fill up the register form, then we will contact you and prepare an official sponsorship request letter for you to present to your University, University’s IT partners or your potential employer.

Congratulations to the winners:

Congratulations to the best hackers:

2023 successful hacks and 1300 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

UPD Editorial

Hello Codeforces!

On December 12, 18:05 MSK Educational Codeforces Round 34 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for Div. 2 again. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Mikhail awoo Piklyaev, Ivan BledDest Androsov and me.

Good luck to all participants!

I also have a message from our partners, Harbour.Space University:

Scholarship Information

We are offering a Scholarship for each of our three tech programmes: Data Science, Computer Science and Cyber Security — fill out the Form for the January 2018 programme start period or the September 2018 programme start period. We will contact you soon. Can't wait to see you here!

Go to form

Congratulations to the winners:

Congratulations to the best hackers:

1528 successful hacks and 786 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

UPD Editorial

Hello, Codeforces!

30th September 2016 at 17:05 MSK Codeforces Round #374 (Div. 2) will take place for second division participants. Traditionally, participants from the first division will be able to join out of competition. Please, notice that the start time is unusual.

This is my second Codeforces round, I tried to make problems interesting for everyone, so I recommend to read all problems statements! I hope that everyone will find something new and interesting. I wish lots of accepted runs and higher rating to all participants.

I want to thank Michael MikeMirzayanov Mirzayanov for wonderful platforms Polygon and Codeforces, and for help in preparing the problems, my best friends Danil danilka.pro Sagunov also for help in preparing the round and Ivan BledDest Androsov for testing the problems.

Participants will be given five tasks and two hours for solve them. Scoring system will be announced traditionally closer to round start. :)

The scoring is almost the standard: 500-1000-1500-2000-2750

UPD: Editorial

567A - Lineland Mail

One can notice that the maximum cost of sending a letter from i'th city is equal to maximum of distances from i'th city to first city and from i'th city to last (max(abs(x_i - x₀), abs(x_i - x_n - 1)). On the other hand, the minimum cost of sending a letter will be the minimum of distances between neighboring cities (i - 1'th and i + 1'th cities), more formally, min(abs(x_i - x_i - 1), abs(x_i - x_i + 1). For each city, except the first and the last this formula is correct, but for them formulas are (abs(x_i - x_i + 1)) and (abs(x_i - x_i - 1)) respectively.

Author solution

567B - Berland National Library

To answer the queries correct, we need to know if the person is still in the library. For that purpose we will use in array of type bool. Also we will store two variables for the answer and ''current state'' (it will store the current number of people in the library). Let's call them ans and state respectively.

Thus, if we are given query  + a_i then we should increase state by one, mark that this person entered the library (in[a_i] = true) and try to update the answer (ans = max(ans, state)).

Otherwise we are given  - a_i query. If the person who leaves the library, was in there, we should just decrease state by one. Otherwise, if this person was not in the library (in[a_i] == false) and leaves now, he entered the library before we started counting. It means we should increase the answer by one anyway. Also one should not forget that it is needed to mark that the person has left the library (in[a_i] = false).

Author solution

567C - Geometric Progression

Let's solve this problem for fixed middle element of progression. This means that if we fix element a_i then the progression must consist of a_i / k and a_i·k elements. It could not be possible, for example, if a_i is not divisible by k ().

For fixed middle element one could find the number of sequences by counting how many a_i / k elements are placed left from fixed element and how many a_i·k are placed right from it, and then multiplying this numbers. To do this, one could use two associative arrays A_l and A_r, where for each key x will be stored count of occurences of x placed left (or right respectively) from current element. This could be done with map structure.

Sum of values calculated as described above will give the answer to the problem.

Author solution

567D - One-Dimensional Battle Ships

First, we should understand when the game ends. It will happen when on the n-sized board it will be impossible to place k ships of size a. For segment with length len we could count the maximum number of ships with size a that could be placed on it. Each ship occupies a + 1 cells, except the last ship. Thus, for segment with length len the formula will look like (we add "fictive" cell to len cells to consider the last ship cell). This way, for [l..r] segment the formula should be .

For solving the problem we should store all the [l..r] segments which has no ''free'' cells (none of them was shooted). One could use (std: : set) for that purpose. This way, before the shooting, there will be only one segment [1..n]. Also we will store current maximum number of ships we could place on a board. Before the shooting it is equal to .

With every shoot in cell x we should find the segment containing shooted cell (let it be [l..r]), we should update segment set. First, we should delete [l..r] segment. It means we should decrease current maximum number of ships by and delete it from the set. Next, we need to add segments [l..x - 1] and [x + 1..r] to the set (they may not be correct, so you may need to add only one segments or do not add segments at all) and update the maximum number of ships properly. We should process shoots one by one, and when the maximum number of ships will become lesser than k, we must output the answer. If that never happen, output  - 1.

Author solution

567E - President and Roads

At first, let's find edges that do not belong to any shortest paths from s to t. Let's find two shortest path arrays d1 and d2 with any shortest-path-finding algorithm. First array stores shortest path length from s, and the second — from t. Edge (u, v) then will be on at least one shortest path from s to t if and only if d1[u] + w(u, v) + d2[v] == d1[t].

Let's build shortest path graph, leaving only edges described above. If we consider shortest path from s to t as segment [0..D] and any edge (u, v) in shortest path graph as its subsegment [d1[u]..d1[v]], then if such subsegment do not share any common point with any other edge subsegment, except its leftest and rightest point (d1[u] and d1[v]), this edge belongs to every shortest path from s to t.

Now we could surely answer "YES" to such edges. Next part of the solution are much simple. If edge (u, v) do not belong to every shortest path, we could try decrease its weight. This edge will belong to every shortest path if and only if its weight will become d1[t] - d1[u] - d2[v] - 1. So, if this value are strictly positive, we should answer "CAN" considering new edge weight. Otherwise we need to output "NO".

Author solution

567F - Mausoleum

Consider that we are placing blocks by pairs, one pair by one, starting from leftmost and rightmost places. Thus, for example, two blocks of height 1 we could place in positions 1 and 2, 1 and 2n, or 2n - 1 and 2n. The segment of unused positions will be changed that way and the next block pairs should be placed on new leftmost and rightmost free places. At last only two positions will be free and we should place two blocks of height n on them.

Any correct sequence of blocks could be builded that way. Let's try to review the requirements consider such way of placing blocks. As soon as we place blocks one by one, the requirements are now only describes the order of placing blocks. For example, requirement ''3 >= 5'' means that we should place block in position 3 only if block in position 5 is already placed (and thus it have lesser height), or we place pair of blocks of same height on them at one moment.

For counting required number of sequences we will use dynamic programming approach. Let's count dp[l][r] — the number of ways to place some blocks in the way that only positions at segment [l..r] are free. The height of current placed pair of blocks is counted from the segment borders itself (. Fix one way of placing current block pair (exclusion is l =  = r + 1). Now check if such placing meets the requirements. We will consider only requirements that meets one of the current-placing positions. For every "current" position "<" must be true only for free positions (positions in [l..r], which do not equal to current positions), ">" must be true for already-placed positions (out of [l..r]) and "=" must be true only for second current position.

This DP could be easily calculated using "lazy" approach.

Author solution

Hello, Codeforces!

5th august 2015 at 19:00 MSK Codeforces Round #Pi will take place for second division participants. Participants from the first division are able to participate out of the contest.

This is my first round on Codeforces. I hope you will enjoy the tasks and this will stimulate me to prepare new rounds! Wish you quick Accepted verdicts and successful hacks.

I want to thank Michael Mirzayanov (MikeMirzayanov) for wonderful platforms Polygon and Codeforces and for help in preparing the tasks, Maxim Akhmedov (Zlobober) for help in contest preparation, Maria Belova for translation statements to english, and also my friends Danil Sagunov (danilka.pro) and Vitaliy Kudasov (kuviman) for solving the tasks.

Participants will be given six tasks and two and the half hours for solving them. Scoring system will be announced closer to round start.

UPD: Scoring: 500-1000-1500-2000-2500-2500.

UPD Editorial