Привет, Codeforces!

30 апреля в 17:35 по Москве начнётся Educational Codeforces Round 43.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для Div. 2. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной готовили Михаил awoo Пикляев, Роман Roms Глазов и Адилбек adedalic Далабаев.

Также мы хотим поблагодарить Ивана BledDest Андросова и Максима Neon Мещерякова за помощь в подготовке раунда.

Удачи в раунде! Успешных решений!

UPD: Раунд будет содержать 6 задач вместо 7.

UPD2: Опбликован разбор

Поздравляем победителей:

Поздравляем лучших взломщиков:

Было сделано 777 успешных взломов и 656 неудачных взломов!

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

961A - Тетрис

#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 - Сон на лекции

#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 - Шахматная доска

#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 - Пара прямых

#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 - Туфурама

#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-подстроки

#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 - Разбиения

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

Привет, Codeforces!

4 апреля в 17:05 по Москве начнётся Educational Codeforces Round 41.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для Div. 2. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной готовили Роман Roms Глазов и Адилбек adedalic Далабаев.

Также мы хотим поблагодарить Михаила awoo Пикляева и Ивана BledDest Андросова за помощь в подготовке раунда.

Удачи в раунде! Успешных решений!

UPD Разбор

UPD2

Поздравляем победителей:

Поздравляем лучших взломщиков:

Было сделано 518 успешных взломов и 491 неудачный взлом!

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Привет, Codeforces!

13 января в 16:05 по Москве начнётся Educational Codeforces Round 36.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд (уже по традиции) будет рейтинговым для Div. 2. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной готовили Михаил awoo Пикляев, Иван BledDest Андросов и Сергей sslotin Слотин.

Удачи в раунде! Успешных решений!

У меня также есть сообщение от наших партнёров, 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.

Поздравляем победителей:

Поздравляем лучших взломщиков:

Было сделано 2023 успешных и 1300 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

UPD Разбор

Привет, Codeforces!

12 декабря в 18:05 по Москве начнётся Educational Codeforces Round 34.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд снова будет рейтинговым для Div. 2. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной готовили Михаил awoo Пикляев и Иван BledDest Андросов.

Удачи в раунде! Успешных решений!

У меня также есть сообщение от наших партнёров, Harbour.Space University:

Информация об обучении

Мы предлагаем записаться на курсы по одной из трёх наших программ, связанных с IT: Data Science, Computer Science и Cyber Security — заполните форму для того, чтобы принять участие в программе, начинающейся в январе или в сентябре 2018 года. Мы свяжемся с вами вскоре после заполнения формы. Надеемся увидеть вас среди участников наших курсов!

Перейти к форме

Поздравляем победителей:

Поздравляем лучших взломщиков:

Было сделано 1528 успешных и 786 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

UPD Разбор

Привет, Codeforces!

30 сентября 2016 года в 17:05 Мск состоится Codeforces Round #374 (Div. 2) для участников из второго дивизиона. Участники первого дивизиона традиционно могут участвовать вне конкурса. Обратите внимание на необычное время проведения.

Это мой второй раунд на Codeforces, я старался сделать задачи интересными для всех, поэтому рекомендую прочитать условия всех задач! Желаю всем участникам раунда найти что-то новое и интересное для себя, и, естественно, быстрых решений и высокого рейтинга!

Хочу поблагодарить Михаила MikeMirzayanov Мирзаянова за замечательные платформы Codeforces и Polygon, за помощь в придумывании задач и их подготовке, своих очень хороших друзей Данила danilka.pro Сагунова также за помощь в подготовке соревнования и Ивана BledDest Андросова за прорешивание раунда.

Участникам будет предложено 5 задач и 2 часа на их решение. Разбалловка будет традиционно объявлена ближе к началу раунда. :)

Разбалловка почти стандартная: 500-1000-1500-2000-2750

UPD: Разбор

567A - Почта в Лайнландии

Можно сделать очевидный вывод — наибольшей стоимостью отправки письма из i-го города будет являться максимум из расстояний от i-го города до первого и от i-го города до последнего (max(abs(x_i - x₀), abs(x_i - x_n - 1)). А минимальной стоимостью отправки будет являться минимум из расстояний до соседних городов (для i-го города соседними являются города с номерами i - 1 и i + 1), то есть (min(abs(x_i - x_i - 1), abs(x_i - x_i + 1)). Для всех городов, кроме самого левого и самого правого, это считается нормально. Так как у самого левого нет соседей левее, значит минимальная стоимость определяются однозначно (abs(x_i - x_i + 1)). Аналогично для самого правого города (abs(x_i - x_i - 1)).

Авторское решение

567B - Берляндская национальная библиотека

Чтобы корректно обрабатывать события, нам необходимо знать, находится ли в библиотеке на данный момент человек. Для этого будем использовать массив in типа bool. Также заведём две переменные для хранения ответа и "текущего состояния" (в которой будет храниться количество человек, присутствующих в библиотеке на данный момент). Их обозначим ans и state соответственнно.

Итак, если к нам поступает запрос вида " + a_i", то мы увеличиваем state на единицу, отмечаем, что этот человек зашёл в читальный зал (in[a_i] = true) и пытаемся обновить ответ (ans = max(ans, state)).

Иначе же к нам поступает запрос вида " - a_i". В данном случае если человек, который выходит из библиотеки, находился в ней, то нам просто нужно уменьшить state. Иначе мы понимаем, что если этого человека "не было" в библиотеке (in[a_i] == false) и он выходит, значит он был в читальном зале ещё до начала рассматриваемого нами промежутка времени. Тогда мы в любом случае должны увеличить ответ на единицу. Также не стоит забывать, что необходимо отметить, что человек вышел из библиотеки (in[a_i] = false).

Авторское решение

567C - Геометрическая прогрессия

Давайте будем решать эту задачу относительно фиксированного среднего элемента. Это значит, что если мы фиксируем элемент a_i, то наша прогрессия должна состоять из элементов вида a_i / k, a_i, a_i·k. Заметим, что прогрессии со средним элементом a_i не будет существовать, когда a_i не делится нацело на k ().

При фиксированном среднем члене мы сможем отвечать на запрос вида "сколько существует подпоследовательностей — геометрических прогрессий, средний элемент которых стоит строго в позиции i". Очевидно, что это будет количество элементов слева от i-го, равных a_i / k, умноженное на количество элементов, находящихся справа от i-го, равных a_i·k. То есть мы можем отвечать на этот вопрос для каждого элемента, если будем знать количества элементов слева и справа от i-го. Для этого можно использовать ассоциативный массив (map). Будем хранить 2 map-a l и r, в l будем поддерживать все элементы строго левее i-го, а в r — строго правее i-го. Если идти по массиву слева направо, то l должен быть пустым, а в r должны быть все элементы. Пройдём циклом по всему изначальному массиву, постепенно обновляя map-ы (очевидно, что перед рассмотрением i-го элемента мы должны удалить его из r, а после рассмотрения — добавить его в l). Если a_i будет делиться нацело на k, то добавляем к ответу l[a_i / k] * r[a_i * k] (стоит заметить, что как при перемножении, так и при обновлении ответа могут случаться переполнения типа int, поэтому проще всего все переменные хранить в long long).

Авторское решение

567D - Одномерный морской бой

Сначала нам необходимо понять, в каком случае мы можем утверждать, что Алиса соврала. Это случится, когда на поле размера n невозможно будет уместить k кораблей размера a. Для отрезка фиксированной длины len мы можем посчитать максимальное количество кораблей размера a, которые могут уместиться на таком поле. Каждый корабль занимает ровно a + 1 клетку, кроме одного крайнего. Поэтому для отрезка длины len формула для подсчёта будет выглядеть так: (чтобы не учитывать корабль, который занимает a клеток, а не a + 1, мы просто добавим одну <<фиктивную>> клетку в наш отрезок). Значит, для отрезка [l..r] наша формула должна выглядеть так: .

Для решения задачи нам надо хранить все отрезки [l..r], внутри которых все клетки "свободны" (то есть ни в одну из клеток отрезка не было произведено выстрела). Для удобства их можно хранить в множестве (std: : set), чтобы можно было легко найти нужный отрезок. Итак, будем обрабатывать выстрелы по очереди. Изначально количесво помещающихся кораблей будет равняться (это значит, что у нас есть один отрезок [1..n]). После каждого выстрела один из отрезков будет либо делиться на два отрезка меньшего размера, либо он будет просто уменьшаться в размере на единицу (если выстрел будет произведён в его край). Таким образом, если выстрел произведён в точку x, относящуюся к отрезку [l..r], то мы должны вычесть из нашего общего количества кораблей их количество на отрезке [l..r], удалить этот отрезок из множества и разделить его на два новых: [l..x - 1] и [x + 1..r] (если выстрел был произведён в край отрезка, тогда добавляется только один новый отрезок) и прибавить к количеству и (соответственно, если появляется только один новый отрезок, то необходимо прибавить только одну величину).

Если после обработки какого-то из выстрелов количество кораблей стало меньше, чем k, то это означает, что Алиса соврала нам, выводим номер этого хода. Если же после обработки всех выстрелов количество кораблей так и осталось не меньше, чем k, выводим  - 1.

Авторское решение

567E - Президент и дороги

Сначала давайте разберёмся, какие рёбра не будут лежать ни на одном кратчайшем пути из s в t. Если запустить два алгоритма поиска кратчайших путей (из вершины s и из вершины t) и сохранить расстояния в массивах d1 и d2 соответственно, можно сделать следующий вывод: если у нас есть ребро (u, v), то оно будет лежать хотя бы на одном кратчайшем пути из s в t тогда и только тогда, когда d1[u] + w(u, v) + d2[v] == d1[t] (где w(u, v) — вес ребра (u, v)).

После того, как мы построили граф кратчайших путей из s в t, мы можем определить, какие из рёбер лежат на всех кратчайших путях. Если представить путь из s в t в виде отрезка [0..D], а расстояния между парами вершин, соединённых рёбрами в этом графе, в виде подотрезков данного отрезка (например, если у нас есть ребро (u, v), тогда данный подотрезок будет иметь вид [d1[u]..d1[v]]), то можно заметить, что все подотрезки каким-то образом касаются других подотрезков (некоторые также могут пересекаться с другими подотрезками). Ребро (u, v) будет лежать на всех кратчайших путях из s в t, если подотрезок [d1[u]..d1[v]] будет только касаться других подотрезков (внутренние пересечения с другими подотрезками недопустимы). Теперь мы можем однозначно отвечать "YES" для этих рёбер.

Остальная часть задачи более простая. Если ребро (u, v) с весом w не лежит на всех кратчайших путях, можно попробовать уменьшить его. Данное ребро будет лежать на всех кратчайших путях только в том случае, если его вес станет равен d1[t] - d1[u] - d2[v] - 1. Итак, если величина d1[t] - d1[u] - d2[v] - 1 (предполагаемый новый вес нашего ребра)строго положительна, тогда мы сможем уменьшить наше ребро так, чтобы оно лежало на всех кратчайших путях, выведем "CAN" и через пробел разность между старым и новым весами ребра. Иначе же выведем "NO".

Авторское решение

567F - Мавзолей

Представим, что мы выставляем блоки по парам в порядке возрастания их высоты, начиная с левого и правого края. Так, например, два блока высоты 1 мы можем поставить в позиции 1 и 2, либо в позиции 1 и 2n, либо в позиции 2n - 1 и 2n. Отрезок незанятых мест таким образом изменится, и следующая по высоте пара блоков будет выставляться уже в образовавшиеся крайние позиции. В конце концов останутся две свободные позиции, куда необходимо поставить пару блоков высоты n.

Очевидно, вышеописанным способом строится любая корректная последовательность. Попробуем посмотреть на требования к высотам блоков со стороны такого способа построения последовательности. Поскольку блоки мы выставляем в порядке возрастания высот, то неравенства теперь ставят ограничения только на порядок расстановки блоков. Например, требование ''3 >= 5'' теперь означает, что ставить блок в позицию 3 мы можем только лишь если блок в позиции 5 уже поставлен (а значит он имеет меньшую высоту), или же в позициях 3 и 5 блоки нужно ставить одновременно (пара блоков одной высоты).

Для дальнейшего подсчета количества способов воспользуемся идеей динамического программирования. Будем считать dp[l][r] — количество способов поставить блоки, если свободные от блоков места образуют отрезок [l, r]. Высота пары блоков, которая будет ставится в крайние места отрезка однозначно определяется границами этого отрезка. Переберем один из трех вариантов расстановки очередной пары блоков (исключение составляет случай l =  = r + 1). Теперь проверим, что такая расстановка не нарушает требования условия задачи. Будем рассматривать только ограничения, касающиеся позиций, на которые ставятся блоки в фиксированном варианте. Для любой "текущей" позиции должно выполняться "<" для любого еще не занятого места (которое находится внутри отрезка [l, r], но не совпадает с одним из двух "текущих" мест), ">" для любого занятого места (вне [l, r]), а ''='' выполняться только в случае сравнения двух "текущих" мест.

Такое динамическое программирование проще всего считать рекурсивно, "ленивой" динамикой.

Авторское решение

Здравствуй, Codeforces!

5 августа 2015 года в 19:00 Мск состоится Codeforces Round #Pi для участников второго дивизиона. Участники первого дивизиона традиционно могут поучаствовать вне конкурса.

Это мой первый раунд на Codeforces. Надеюсь, что задачи вам понравятся и это даст мне стимул для подготовки новых раундов! Желаю всем быстрых Accepted и успешных взломов!

Хочу поблагодарить Михаила Мирзаянова (MikeMirzayanov) за замечательные платформы Polygon и Codeforces и за помощь в придумывании задач, Максима Ахмедова (Zlobober) за помощь в подготовке соревнования, Марию Белову (Delinur) за перевод условий на английский, а также моих друзей Данила Сагунова (danilka.pro) и Виталия Кудасова (kuviman) за прорешивание задач.

Участникам будет предложено 6 задач и два с половиной часа на их решение. Разбалловка будет объявлена ближе к началу раунда.

UPD: Разбалловка: 500-1000-1500-2000-2500-2500.

UPD: Разбор