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

1. 

   toxicmt

   06.11.2015 17:31

   #8645649

   +3

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

1. 

   Source

   06.11.2015 19:32

   #8645781

   +4

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

   
   

   1. 

      grey_wolfs

      09.11.2015 10:59

      #8647735

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

1. 

   hellman

   06.11.2015 20:51

   #8645875

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

   
   

   1. 

      halyavin

      06.11.2015 21:22

      #8645911

      Есть еще простой (но возможно более медленный) метод. Рассматриваем блоки палиндромов в двух системах счисления (я использовал блоки размера 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

   
   

   1. 

      grey_wolfs

      09.11.2015 10:27

      #8647697

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

      
      

      1. 

         ilyanik

         12.11.2015 19:10

         #8652491

         Еле разобрался в их решении.
         
         Вкратце идея такая:
         
         

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

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

1. 

   ilyanik

   09.11.2015 07:58

   #8647571

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

   
   

   1. 

      grey_wolfs

      09.11.2015 10:52

      #8647727

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

      
      

      1. 

         ilyanik

         11.11.2015 15:24

         #8651017

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

         Сделал сам

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

         
         

1. 

   ilyanik

   11.11.2015 13:35

   #8650861

   Не дождался вашей имплементации:
   
   Действительно несравнимо быстрее, но все равно недостаточно: просто пройтись по 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
   };