Первая личная интернет-олимпиада, отбор на ИОИП

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всем привет!

В это воскресенье, 21 января, мы начинаем сезон личных интернет-олимпиад — в 16:00 по московскому времени состоится первая личная интернет-олимпиада для школьников, которая также будет являться первым отборочным туром ИОИП. Вам предстоит помочь подросткам, попавшим в игру Джуманджи, со всеми возникшими у них трудностями.

Продолжительность олимпиады — 5 часов. Не забудьте зарегистрироваться на цикл личных интернет-олимпиад в этом сезоне перед началом олимпиады, если вы не сделали этого раньше.

Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client.

Олимпиаду для вас подготовили подготовили Илья Збань (izban), Николай Будин (budalnik), Александра Дроздова (demon1999), Михаил Анопренко (manoprenko), Дмитрий Филиппов (DimaPhil) и Григорий Шовкопляс (GShark).

Также спасибо Ильдару Гайнуллину (300iq) за помощь в тестировании задач.

Удачи!

h[i + 1] = h[i] * P + s[i]; if(h[i + 1] >= MOD) h[i + 1] %= MOD; ll get_hash ( int l, int r ) { return (h[r + 1] - h[l] * deg[r - l + 1] + MOD * MOD) % MOD; }; ll get_revhash (int l, int r) { return (revh[l + 1] - revh[r + 2] * deg[r - l + 1] + MOD * MOD) % MOD; }

int res; ll h[2000005], rh[2000005], deg[2000005]; int getHash(int l, int r) { if (l == 0) return h[r]; res = (h[r] - h[l - 1] * deg[r - l + 1]) % mod; if (res < 0) res += mod; return res; } int getRHash(int l, int r) { if (r + 1 == str.size()) return rh[l]; res = (rh[l] - rh[r + 1] * deg[r - l + 1]) % mod; if (res < 0) res += mod; return res; }

Комментарии (29)

Показать архивные | Написать комментарий?

_Dreamer_

7 лет назад, # |

It smells like long adventrure

→ Ответить

Victor_Morozov

Извините, а это нормально что я зарегестрировался, но не могу зайти на PCMS@ Web Client?

gamezovladislav

7 лет назад, # ^ |

Мало просто заполнить форму, еще необходимо дождаться подтверждения регистрации.
тут можно посмотреть статус...

12iq

+55

Проблемы с доступом к PCMS? Просто добавь 2 и получи PCMS2...

Qumeric

Можно ли писать не школьникам вне конкурса?

madmax

У вас тоже не грузиться?

almosh

Да

bktl1love

← Rev. 2 →

Я зарегистрировался после начала контеста, и я не могу войти в PCMS. У всех так? UPD: Зашел

Shudi

Подскажите, где найти условия задач? Возможно, у меня проблемы с отображением некоторых ссылок.

JotaroKujo

Пожалуйста

Спасибо!

markysha

+12

Как решать д?

gepardo

← Rev. 4 →

+10

Воспользуемся динамическим программированием.

У нас ДП такая: dp[v, k, flag], где v -- вершина, k -- количество ~~гепардов~~ ягуаров, которых мы хотим поставить в поддереве с вершиной v, flag -- флаг, он обозначает следующее:

0 -- через v не проходит путь никакого ~~гепарда~~ ягуара
1 -- через v проходит путь, и не опускается назад в поддерево
2 -- через v проходит путь, и опускается назад в поддерево

Начальные значения: dp[v, 0, 0] = dp[v, 1, 1] = 0.

В самом конце подсчета динамики для заданного v мы увличиваем все значения dp[v, k, 1] и dp[v, k, 2] на значение энергии в вершине v.

Как делать пересчеты? Мы добавляем функцию merge, которая добавляет сына к ответу. Она работает за O(k1·k2), где k1 -- размер дерева, которое у нас уже есть, а k2 -- размер поддерева сына. Таким образом мы добавляем к нашей вершине v сыновей по одному.

Можно доказать, что такая динамика работает за O(n²).

Как она пересчитывается, смотрите код для лучшего понимания.

Код

struct DPState {
	int k;
	vector<int64_t> d0, d1, d2;
	
	inline int64_t max012(int i) const {
		return max(d0[i], max(d1[i], d2[i]));
	}
	
	DPState() {
	}
	
	DPState(int k)
		: k(k),
		  d0(k+1, LLONG_MIN),
		  d1(k+1, LLONG_MIN),
		  d2(k+1, LLONG_MIN) {
	}
};

inline int64_t sum(int64_t a, int64_t b) {
	return (a == LLONG_MIN || b == LLONG_MIN) ? LLONG_MIN : (a+b);
}

inline void umax(int64_t &a, int64_t b) {
	a = max(a, b);
}

inline string itos(int64_t val) {
	if (val == LLONG_MIN) {
		return ":(";
	} else {
		ostringstream os; os << val;
		return os.str();
	}
}

signed main() {
	#ifndef USE_FILE_IO
		ios_base::sync_with_stdio(false);
	#endif
	int n, k; cin >> n >> k;
	vector<int64_t> e(n);
	for (int i = 0; i < n; i++) {
		cin >> e[i];
	}
	vector< vector<int> > g(n);
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b; a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	auto mergeStates = [&](const DPState &a, const DPState &b) -> DPState {
		DPState c(a.k + b.k);
		for (int i = 0; i <= a.k; i++) {
			for (int j = 0; j <= b.k; j++) {
				umax(c.d0[i + j], sum(a.d0[i], b.max012(j)));
				umax(c.d1[i + j], sum(a.d1[i], b.max012(j)));
				umax(c.d2[i + j], sum(a.d2[i], b.max012(j)));
				umax(c.d1[i + j], sum(a.d0[i], b.d1[j]));
				umax(c.d2[i + j - 1], sum(a.d1[i], b.d1[j]));
			}
		}
		return c;
	};
	
	vector<DPState> dp(n);
	function<void(int, int)> dfs = [&](int v, int p) {
		DPState kur(1);
		kur.d0[0] = kur.d1[1] = 0;
		for (int to: g[v]) {
			if (to == p) {
				continue;
			}
			dfs(to, v);
			kur = mergeStates(kur, dp[to]);
		}
		for (int i = 0; i <= kur.k; i++) {
			kur.d1[i] = sum(kur.d1[i], e[v]);
			kur.d2[i] = sum(kur.d2[i], e[v]);
		}
		dp[v] = kur;
	};
	dfs(0, -1);
	
	cout << dp[0].max012(k) << endl;
	
	return 0;
}

+16

Может быть тогда кто-нибудь поделится идеями решения на полный балл C и B? Хеши в третей задаче у меня зашли только на длины строк до 10^5.Что дальше? Из предположений только алгоритм Манакера, но может быть можно какое-нибудь ДП насчитать?

← Rev. 3 →

В третьей да, Манакер. Конкатенируешь строку два раза, далее нужно найти наибольший палиндром, не превосходящий длины строки. Это делается так: находим наибольшие палиндромы четной и нечетной длин, затем их уменьшаем, пока они не станут не больше длины строки. Потом ищем максимум из них.

Во второй надо все IP-адреса перевести в uint64-числа. Затем ответ магическим образом оказывается равен b - a - 1 - k, где k — количество IP-адресов i таких, что a ≤ i ≤ b. Осталось проверить случай, когда это невозможно (между a и b нет подряд идущих).

Спасибо. В плане третьей всё понятно. Вопрос по второй: я так понимаю, что под uint64 подразумевается не unsigned long long. Если так, то можно чуть подробнее об этом / ссылку на какой-либо материал по данному типу?

uint64 это, по сути, unsigned long long (64-х битный беззнаковый). Я написал uint64, чтобы было без привязки конкретно к языку C++.

А вообще, я не любитель long long и всегда использую int64_t и uint64_t вместо long long и unsigned long long соответственно (если это возможно).

Видимо, что-то всё-таки понял неверно. Во-первых, при вычитании у нас могут появиться маски, по типу 999, которые больше 255. Во-вторых, x <= 8, т.е. длина числа будет 8 * 3 = 24, что, в свою очередь, больше ограничений типа.

x ≤ 8, каждое число по 8 бит, значит, все поместится в 8 * 8 = 64-х битный тип.

Мы преобразуем IP-адреса в uint64-числа таким образом. Самую правую часть адреса мы помещаем в младшие 8 бит, следующую слева от нее -- в следующие в 8 бит и так далее. При таком преобразовании каждое число меньше 2^8x будет соответствовать валидному адресу и наоборот.

LoDThe

Если попробовать убрать лишние взятия остатка от деления, то на 100 заходят хеши.

Можно подробнее по этому поводу? Старался делать как можно оптимальнее и лишний раз не брать по модулю. Или может быть дело в том, что я считаю всё в long long?

При сумме/разности по модулю можно использовать следующий трюк: вместо a = (b + c) % MOD писать как-то так:

a = b + c;
while (a >= MOD) {
    a -= MOD;
}

Утверждается, что, если a < MOD и b < MOD, то такая конструкция отработает быстрее.

С разностью нечто похожее.

Да, это понятно. Но не совсем понимаю, как этот метод применим к коду выше. Во всех случаях используется умножение, где в любом случае нужно брать остаток от деления. Мне кажется, что будет быстрее загнать сумму/разность под это же взятие остатка, т.к. один раз нам всё равно придётся это сделать. Разве не так?