grey_wolfs6 ноя 2015 в 12:50

Вперед, на поиски палиндромов

7 мин

23K

PHP * Программирование * Спортивное программирование *

+18

Комментарии 15

toxicmt 6 ноя 2015 в 14:31

Круто! Не зря батл делали)

Source 6 ноя 2015 в 16:32

Есть ощущение, что если бы вы работали не со строками, а с цифрами напрямую, то было бы ещё быстрее.

grey_wolfs 9 ноя 2015 в 07:59

Я думаю вы правы. Ниже уже подсказали как это можно сделать. Сейчас буду пробовать реализовывать.

hellman 6 ноя 2015 в 17:51

Не так давно на одном из контестов codechef была такая же задачка. Только базы систем исчисления произвольные от 2 до 16, и нужно было первые 1000 палиндромов меньшие 2^60. Ограничение по времени — 8 сек (правда на входе может быть 5 тестов). Editorial там же есть.

halyavin 6 ноя 2015 в 18:22

Есть еще простой (но возможно более медленный) метод. Рассматриваем блоки палиндромов в двух системах счисления (я использовал блоки размера 1000 и 1024 соответственно). Рассчитываем множество разниц (a(i)-a(0)) — (b(j)-b(0)), где a(i), b(j) — числа в блоках. Множество этих разниц зависит только от количества цифр в двух системах счисления, поэтому его можно переиспользовать, пока число цифр в одной из систем счисления не изменится. Потом вычисляем разницу между началами блоков b(0)-a(0) и смотрим попадает ли она в это множество. Если попадает — проверяем ответ. Если не попадает — сдвигаем один из блоков вперед.

У меня получились следующие результаты (на java):
60 55952637073625955 3.100s
61 161206152251602161 3.981s
62 313558153351855313 4.406s
63 7036267126217626307 11.122s

grey_wolfs 9 ноя 2015 в 07:27

Спасибо! Это великолепно! Сейчас попробую в этом разобраться.

ilyanik 12 ноя 2015 в 16:10

Еле разобрался в их решении.

Вкратце идея такая:

Для каждой возможной длины большего из оснований (BASE) генерируем 2 набора частичных палиндромов.
1. 1-й, вида a..b0..00..0b..a, где (a != 0)
2. 2-й, вида 0..0c..dd..c0..0, без ограничений.
* множеством всех палиндромов данной длины, очевидно, будет множество всех попарных сумм.
Переводим все палиндромы из обоих наборов во второе основание (base).
Смотрим на N верних цифр палиндромов из первого набора и на N нижних из обоих. N прямо пропорционально ширине a..b
Используем факт, что если пара элементов образует палиндром в основании (base), то и (N верних цифр 1-го набора).(сумма N нижних цифр обоих) ПРИМЕРНО образуют палиндром в основании (base). Это возможно потому, что прибавление даже максимально возможного палиндрома из 2-го набора ПОЧТИ не влияет на N верних цифр 1-го набора. При правильно выбранной структуре хранения элементов 2-го набора, это позволяет для каждого элемента из 1-го набора проверять относительно небольшое количество элементов из 2-го.

Нахождение всех двойных палиндромов по основаниям 2 и 10, до 2^60, занимает ~0.1 секунды, при этом проверку на палиндром в основании (base) проходят 174984 (из более милларда!) пар.

ilyanik 12 ноя 2015 в 17:25

Ещё немного оптимизации, и время уменьшено до ~0.03 секунды.

grey_wolfs 13 ноя 2015 в 06:07

ilyanik Отличная работа! Я по этому решению хотел отдельную статью написать. Это довольно сложное и очень интересное решение. Но, если хотите, я вам уступлю. У меня сейчас немного тяжеловато со временем, а вы уже, я смотрю, во всем разобрались.

ilyanik 13 ноя 2015 в 13:48

Нет, спасибо, «чукча не писатель» :)

Но если нужно, причешу и прокомментирую свой код (C++) и выложу.

ilyanik 15 ноя 2015 в 10:50

0.016 секунды.

А если ещё в двух местах операцию модуля заменить на итеративное вычитание, то можно сделать ещё на 10-20% быстрее.

ilyanik 9 ноя 2015 в 04:58

Извините за теоретический пост в практическом топике. :)

По-моему, куда более эффективной будет «генерация» палиндромов прямо в переменной типа int64. Например, для десятичных палиндромов длиной 4 надо начать с 1001 и дойти до 9999, каждый раз прибавляя либо по 110 (1111, 1221, ...), либо 11 (1991->2002, 2992->3003, ...). Аналогично и постоянно сравнивая, продвигаемся по двоичным палиндромам.

grey_wolfs 9 ноя 2015 в 07:52

Да. Скорее всего вы правы. Надо только придумать корректные условия для больших чисел. Например, в 6-тизначных палиндромах надо прибавлять 1100, 110 или 11. Для каждого своё условие (ну или свой цикл). А в палиндромах с нечетным кол-вом знаков надо прибавлять 10^n или 11*10^n-1. В общем сейчас попробую это реализовать и отпишусь как это сработало.

ilyanik 11 ноя 2015 в 12:24

Не дождался вашей имплементации:

Сделал сам

template<typename IntT, size_t BASE>
class palindrome_iterator
{
	static const size_t MAX_WIDTH = sizeof(IntT) * CHAR_BIT;

	struct IncrementData
	{
		IncrementData()
			: m_counter(BASE - 1)
			, m_counterLimit(BASE - 1)
			, m_increment(IntT(1))
		{}

		size_t  m_counter;         //	current counter value
		size_t  m_counterLimit;    //	number of iterations, usually B, but B - 1 for last increment
		IntT    m_increment;       //	increment value
	};

public:
	palindrome_iterator()
		: m_value(1)
		, m_countersSize(1)
		, m_basicIncrement(1)
		, m_width(1)
	{
		m_powers[0] = IntT(1);
		for (size_t i = 1; i < MAX_WIDTH / 2 + 1; ++i)
			m_powers[i] = m_powers[i - 1] * IntT(BASE);
	}

	inline void operator ++()
	{
		//	always increment basic
		m_value += m_basicIncrement;

		size_t i = 0;
		do {
			if (--m_counters[i].m_counter)
				return;

			//	fix value on digit overflow
			m_counters[i].m_counter = m_counters[i].m_counterLimit;
			m_value += m_counters[i].m_increment;
		} while (++i < m_countersSize);

		//	reset increments when new digit is added
		IncWidth();
	}

	inline const IntT & operator *() const
	{
		return m_value;
	}

private:
	void IncWidth()
	{
		++m_width;
		if (m_width & 1) {
			m_counters[m_countersSize - 1].m_counter = m_counters[m_countersSize - 1].m_counterLimit = BASE;
			++m_countersSize;
		}

		if (m_width & 1) { 
			m_basicIncrement = m_powers[m_countersSize - 1];                                   //	100...

			m_counters[0].m_increment = m_powers[m_countersSize - 2];
		}
		else {
			m_basicIncrement = m_powers[m_countersSize - 1] + m_powers[m_countersSize];        //	110...

			m_counters[0].m_increment = m_powers[m_countersSize - 2] - m_powers[m_countersSize];
		}

		for (size_t i = 1; i < m_countersSize - 1; ++i)
			m_counters[i].m_increment = m_powers[m_countersSize - i - 2] - m_powers[m_countersSize - i];

		m_counters[m_countersSize - 1].m_increment = m_powers[0] - m_powers[1];
	}

	IntT           m_value;                        //	current value
	IntT           m_basicIncrement;               //	basic increment (100... for odd width, 1100... for even width
	size_t         m_countersSize;                 //	just greater half of width: (width + 1) / 2
	IncrementData  m_counters[MAX_WIDTH];
	IntT           m_powers[MAX_WIDTH / 2 + 1];    //	1, B, B^2, B^3, ... sequence
	size_t         m_width;                        //	current width = number of digits
};

Действительно несравнимо быстрее, но все равно недостаточно: просто пройтись по палиндромам до 2^60 у меня занимает 5 секунд. А значит, что найти все палиндромы по 2 основаниям займёт минимум 10 секунд. А по условиям codechef можно за 1.5

ilyanik 11 ноя 2015 в 10:35

Не дождался вашей имплементации:

Действительно несравнимо быстрее, но все равно недостаточно: просто пройтись по 2^60 палиндромов у меня занимает 5 секунд. А значит, что найти все палиндромы по 2 основаниям займёт минимум 10 секунд. А по условиям codechef можно за 1.5

template<typename IntT, size_t B>
class palindrome_iterator
{
	static const size_t MAX_W = sizeof(IntT) * 8;

	struct IncrementData
	{
		size_t  m_counter;         //	current counter value
		size_t  m_counterLimit;    //	number of iterations, usually B, but B - 1 for last increment
		IntT    m_increment;       //	increment value
	};

public:
	palindrome_iterator()
		: m_value(1)
		, m_countersSize(1)
		, m_basicIncrement(1)
		, m_width(1)
	{
		m_powers[0] = 1;
		for (size_t i = 1; i < MAX_W; ++i)
			m_powers[i] = m_powers[i - 1] * (IntT)B;

		for (size_t i = 0; i < MAX_W; ++i) {
			m_counters[i].m_counter = m_counters[i].m_counterLimit = B - 1;
		}

		m_counters[0].m_increment = 1;
	}

	inline void operator ++()
	{
		//	always increment basic
		m_value += m_basicIncrement;

		size_t i = 0;
		do {
			if (--m_counters[i].m_counter)
				return;

			//	fix value on digit overflow
			m_counters[i].m_counter = m_counters[i].m_counterLimit;
			m_value += m_counters[i].m_increment;
		} while (++i < m_countersSize);

		//	reset increments when new digit is added
		IncWidth();
	}

	inline const IntT & operator *() const
	{
		return m_value;
	}

private:
	void IncWidth()
	{
		++m_width;
		if (m_width & 1) {
			m_counters[m_countersSize - 1].m_counter = m_counters[m_countersSize - 1].m_counterLimit = B;
			++m_countersSize;
		}

		if (m_width & 1) { 
			m_basicIncrement = m_powers[m_countersSize - 1];                                                //	100...

			m_counters[0].m_increment = m_powers[m_countersSize - 2];
		}
		else {
			m_basicIncrement = m_powers[m_countersSize - 1] + m_powers[m_countersSize];

			m_counters[0].m_increment = m_powers[m_countersSize - 2] - m_powers[m_countersSize];
		}

		for (size_t i = 1; i < m_countersSize - 1; ++i) {
			m_counters[i].m_increment = m_powers[m_countersSize - i - 2] - m_powers[m_countersSize - i];    //	110...
		}

		m_counters[m_countersSize - 1].m_increment = m_powers[0] - m_powers[1];
	}

	IntT           m_value;                    //	current value
	IntT           m_basicIncrement;           //	basic increment (100... for odd width, 1100... for even width
	size_t         m_countersSize;             //	just greater half of width (width + 1 / 2)
	IncrementData  m_counters[MAX_W];
	IntT           m_powers[MAX_W];            //	1, B, B^2, B^3, ... sequence
	size_t         m_width;                    //	current width = number of digits
};

Зарегистрируйтесь на Хабре, чтобы оставить комментарий