Timus 1382

Есть N человек и столько же карточек, пронумерованных от 1 до N. (N < 1000) Каждому человеку вручается карточка. Каждый человек делает два высказывания: у меня карточка a_i и у человека b_i карточка c_i. Одно из высказываний верно, другое — нет. Двух одинаковых высказываний среди всех людей нет. Найти какое высказывание каждого человека было верным.

Идей несколько:

i) Построим двудольный граф с 2*N ребрами. Нужно построить паросочетания с дополнительными запретами на некоторые пары ребер. Можно перейти к вершинному графу, где вершины смежны, если они не могут быть в одном паросочетании и попытаться найти наибольшее вершинное покрытие.

ii) Попробуем свести к 2-SAT. Рассмотрим 2*N переменных вида: у человека i карточка j. Тогда условие на выполнение ровно одного высказывания будет эквивалентно выполнению формулы: (x || y) && (not x || not y). Как учесть, что будет выбрана только одна карточка? Допустим, относительно этой карточки сделано несколько предположений: x, y, u, z. Тогда условие станет таким: (x && not y && not u && not z) || (not x && y && not u && not z) || (not x && not y && u && not z) || (not x && not y && not u && z).

Есть ли еще какие-нибудь идеи?

Timus 1940

Необходимо найти количество чисел из диапазона (A, A+B] (A, B < 10^9), не содержащих простых делителей, меньших k (k < 300). Пробую перебирать произведения простых чисел, меньших k, и использовать формулу включения-исключения, примерно вот так:

int go(int count, int product, int prime_index)
{
	if (product > B || prime_index == primes.size())
		return 0;

	int product_new = primes[prime_index] * product;
	int count_new = count+1;

	int result = 0;
	if (count_new & 1)
	{
		result += (B / product_new - A / product_new);
	}
	else
	{
		result -= (B / product_new - A / product_new);
	}

	result += go(count+1, product_new, prime_index + 1);
	result += go(count, product, prime_index + 1);

	return result;
}

TL. Возможно ли как-нибудь ускорить данное решение или необходим другой подход? Спасибо.

Timus 1696

Посчитать число последовательностей длины N (N <= 1000) элементы которой из [1..K] (K <= 200) таких, что не существует i < j < k и A[i] > A[j] > A[k].

Очевидно, существует простое решение за N*K^3, если в состоянии запоминать два максимальных элемента, что, естественно, не проходит по времени.

Спасибо!

SRM 581 Div-1 Medium

Скажите, пожалуйста, не будет ли являться публикация ссылки на библиотеку prewritten алгоритмов нарушением правил Codeforces? Может быть, подобная информация будет полезна неопытным участникам?