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

Продвижение в рунете определяется двумя поисковыми системами — Google и Яндекс. Алгоритмы ранжирования обоих весьма схожи. Но есть некоторые отличия, которые просто невозможно игнорировать.

По наблюдениям вебмастеров формула ранжирования Google учитывает около 270 факторов , определяющих позиции сайта в выдаче, в то время как формула Яндекса — около 800 .

Действие алгоритма Google логично и последовательно. Сайт появляется в индексе, наращивает ссылочную массу, создает полезный, уникальный контент — выходит в ТОП. За попытки манипулировать рейтингом (к примеру, закупка ссылок) сайт попадет под фильтр.

Для выхода в ТОП Google достаточно планомерно работать с сайтом: регулярно обновлять контент, распространять его в социальных сетях, работать над наращиванием естественной ссылочной массы.

(блог GetGoodRank в ТОП Google на 4 позиции)

Поисковый алгоритм Яндекс

Ситуация в Яндексе обстоит несколько иначе. Во-первых, ТОП Яндекса корректируется вручную. Во-вторых, Яндекс учитывает в ранжировании коммерческие факторы . Это факт.

Летом 2015 года вебмастера отметили существенные колебания ТОПа поисковой выдачи по высокочастотным запросам. Екатерина Гладких, аналитик Яндекс, подтвердила, что в этот период поисковая система тестировала подход к определению релевантности сайтов. Суть метода заключается в том, что сайты, по которым Яндексу не хватает пользовательских данных, искусственно поднимаются в ТОП по запросам, которым сайт является предположительно релевантным. Если сайт в течение тестового периода получит переходы и его поведенческие будут на высоте, то алгоритм присвоит ему более высокие позиции, чем изначально определенные формулой. Екатерина признала, что качество поисковой выдачи из-за введения такого метода «кратковременно снижается».

Выйти в ТОП Яндекс из-за дополнительных факторов ранжирования должно быть сложнее, чем продвинуться в Google, однако практика показывает, что нет:

(блог GetGoodRank в ТОП Яндекса на 4 позиции, а в Google — на 18 позиции)

Хотя качество ранжирования с учетом более 800 факторов оставляет желать лучшего:

(Блог для вебмастеров в ТОП 3 ответов Яндекс на вопрос об использовании цементировочных агрегатов)

Факторы ранжирования в 2016 году

Мы предлагаем говорить о 3 важных группах факторов ранжирования:

факторы контента — видео, графика, текст, их качество, количество

пользовательские факторы — факторы, определяющие доверие посетителя сайта.

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

Почему выделяем именно эти три группы? Это те факторы, которые действительно имеют значение для позиций сайта, а также доступны для оптимизации вебмастерам.

Если проанализировать эволюцию поисковых систем, то мы приходим к выводу, что борьба поисковых систем направлена вовсе не на само SEO как таковое, а на его автоматизацию.

Ссылки продолжают работать как в Google, так и в Яндекс. Если бы ссылки не имели значения для поисковых систем, то алгоритмы просто перестали бы их учитывать в определенный момент, без шумных заявлений об отключении, без введения фильтров и санкций за закупку. И пусть бы вебмастера игрались и тешились дальше, сливая SEO-бюджеты сайтов в бестолковую закупку.

Что делать с ссылочным

Закупать ссылки опасно, хотя вебмастеров санкции Минусинска не остановили. Ссылки продолжают закупать, хоть и не в таких количествах, как ранее. Вебмастера рекомендуют тщательно изучать ресурсы, прежде чем получить обратную ссылку:

качественные, регулярно обновляемые сайты

сайты, сделанные для людей

активно посещаемые, используемые сайты

сайты, точно соответствующие тематике продвигаемого ресурса

Исследование компании Backlinko подтверждает значимость ссылок, указывая их главным фактором для продвижения в Google. Сегодня для высоких позиций сайта выгоднее получить 10 ссылок с разных доменов, чем 10 ссылок с одного домена.

(зависимость позиций сайта от количества ссылающихся доменов в Google, результаты исследования Backlinko)

Факторы контента

Контент — основной информирующий элемент сайта, работающий в двух направлениях. Поисковым системам контент указывает на релевантность сайта интересам пользователей. Для посетителей контент является основным элементом коммуникации.

Сегодня поисковые системы выдвигают особые требования к наполнению сайта. Техническая уникальность текста отходит на второй план, в то время как польза, ценность, актуальность информации становятся главными факторами для ранжирования.

Поисковые системы уже «умеют» определять настроение и удовлетворенность пользователя, отслеживая его поведение на сайте. Иными словами, поисковики понимают, понравился пользователю контент или нет.

Google говорит о достаточности контента, исследования доказывают, что страницы с более объемным контентом ранжируются выше. Этому есть несколько объяснений:

Полезный, объемный, достаточный текст по теме вызывает больше доверия пользователей — такие страницы получают больше социальных сигналов, что учитывается при ранжировании

Объемный текст позволяет поисковым системам точнее определить релевантность страницы/сайта

В инструкциях асессорам (Google Search Quality Rating Guide) Google говорит о достаточности основного контента на странице, не указывая точных пределов минимума и максимума.

Для высокого ранжирования важны:

разнообразие контента — видео-контент увеличивает время на сайте, большое количество качественной, релевантной графики (к примеру, качественные изображения товаров в интернет-магазине) увеличивает время на сайте, количество кликов, глубину просмотра, объемные, полезные статьи и обзоры повышают вероятность добавление сайта в избранное/закладки для быстрого доступа, растет уровень повторных посещений.

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

Технически уникальный текст ничего не значит для пользователя. Когда человек приходит на сайт, он хочет получить ответы на главные вопросы: кто, что, где, когда, зачем, почему?

Отвечает ли контент вашего сайта на эти вопросы? Вот отрывок текста сайта из ТОП Google по запросу акриловые ванны:

(пример текста для поисковых машин, не несущий никакой пользы для посетителя)

Такой текст поможет сайту указать релевантность запросу для поисковой системы. Но ценность такого текста для пользователя стремится к нулю.

Релевантность — это параметр контента, который оценивается и поисковыми системами, и пользователями, ведет к более высоким позициям и улучшению поведенческих факторов сайта.

Пользовательские факторы

Пользовательские факторы — это совокупность действий пользователя на сайте и в отношении сайта: переходы из поиска и прямые заходы, действия на сайте, возвраты в выдачу, клики по кнопкам социальных сетей. К пользовательским факторам также относим юзабилити, напрямую определяющую желание пользователя взаимодействовать с сайтом.

Пользовательские факторы — это те параметры, которые по минимуму подлежат автоматизации. Поисковые системы чувствительны к буму посещений, резким изменениям паттернов поведения пользователей на сайте, географии пользователей. Использование сервисов автоматической накрутки поведенческих факторов понижает сайты в поисковой выдаче до того уровня, когда их практически невозможно найти в поисковой выдаче.

Накрутка поведенческих факторов только для выхода в поисковый ТОП — дело абсолютно неблагодарное. Прибыли сайту такие «посетители» не принесут, а без комплексного анализа и оптимизации сайта под реальных пользователей выход в ТОП для сайта опасен:

Посетители заходят на сайт, обнаруживают некачественный дизайн, неуникальный/неакутальный контент, подозрительные функции и возвращаются в выдачу. Уровень отказов растет, и эффект от «накрутки» поведенческих минимизируется.

Сейчас набирают популярность сервисы, привлекающие к анализу сайта реальных пользователей. Отчет такого анализа показывает, что мешает реальным пользователям совершить целевое действие на сайте, а также укажет, какие именно параметры сайта исправить и улучшить, чтобы пользователь остался доволен, что в результате приведет к росту поведенческих факторов.

Какие факторы ранжирования Google и Яндекс стоит оптимизировать?

Сегодня мы наблюдаем переход SEO из технической плоскости в плоскость психологическую. Работа исключительно с техническими параметрами сайта больше не дает желаемых результатов. Бесспорно, техническое исполнение сайта должно быть на высоте, потому как любые ошибки сайта (кривая верстка, ошибки в тексте, битые ссылки) критично снижают доверие пользователя. Поисковые системы внедрили искусственный интеллект в алгоритмы ранжирования (Яндекс — Матрикснет, Google — RankBrain), которые понимают, что ищет пользователь, и выдают наиболее подходящие результаты. Вебмастера давно отметили, что один и тот же запрос, введенный с двух разных компьютеров двумя разными пользователями получат разный ответ поисковой системы и разный список сайтов в выдаче. Из этого следует, что сегодня резоннее работать с факторами качества сайта, которые вызываю доверие как пользователей, так и поисковых систем, и других сайтов.

Ссылки

Автоматизировать наращивание ссылочной массы больше нельзя. Для получения качественных обратных ссылок нужны:

новые деловые контакты и связи

вход в новые целевые сообщества

работа с брендом (укрепление доверия целевой аудитории, надежность, авторитет)

Контент

Уникальность отходит на второй план, а так, автоматизировать создание контента не представляется возможным. Единственная ситуация, в которой резонно обратиться к автогенерации контента — заполнение карточек товаров интернет-магазина, ассортимент которого насчитывает десятки тысяч позиций. Однако уже сейчас есть отличные рекомендации, как работать с карточками товаров . Сегодня важно уйти от лирики, и давать пользователю действительно качественный контент, четко отвечающий на его вопрос:

Важно, чтобы в пределах одной страницы пользователь нашел ответы на все вопросы, и ему не понадобилось возвращаться в поиск, чтобы полностью собрать «пазл» решения вопроса. Джейсон Демерс (Jason DeMers), SEO-аналитик Forbes, говорит о важности наличия разных типов контента на сайте, акцентируя внимание на видео и изображениях. Именно этот контент обладает наибольшим вирусным потенциалом, мгновенно получая тысячи лайков и репостов в социальные сети, что также способствует наращиванию ссылочной массы.

Пользовательские факторы

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

(Активность в Facebook — улучшение пользовательских факторов блога)

Для оптимизации пользовательских факторов необходимо:

четко понимать потребности и цели пользователей

качественный контент, точно отвечающий целям пользователя

удобный, простой в использовании, понятный сайт, способствующий достижению цели пользователя

техническая исправность сайта

социальная представленность

мобильная доступность

Факторов ранжирования много, учесть все в процессе работы над сайтом просто невозможно. Указанные группы факторов имеют наибольший вес в формулах поисковых алгоритмов.

EO 2016 — это интеллектуальное SEO, не подлежащее автоматизации. Сегодня для высокого ранжирования следует работать над качеством сайта, а не акцентировать технические аспекты (ссылки, ключевые слова), как это было ранее.

Интернет состоит из миллионов сайтов и содержит экзабайты информации. Чтобы люди могли узнать о существовании этой информации и воспользоваться ей, существуют поисковые системы. Они реализуют право человека на доступ к информации - любой информации, которая нужна в данный момент. Поисковая система - это техническое средство, с помощью которого пользователь интернета может найти данные, уже размещенные в сети.

Пользователи ищут в интернете самые разные вещи - от научных работ до эротического контента. Мы считаем, что поисковая система в каждом случае должна показывать подходящие страницы - от статей по определенной теме до сайтов для взрослых. При этом она просто находит ту информацию, которая уже есть в интернете и открыта для всех.

Яндекс не является цензором и не отвечает за содержание других сайтов, которые попадают в поисковый индекс. Об этом было написано в одном из первых документов компании «Лицензия на использование поисковой системы Яндекса», созданном еще в 1997 году, в момент старта : «Яндекс индексирует сайты, созданные независимыми людьми и организациями. Мы не отвечаем за качество и содержание страниц, которые вы можете найти при помощи нашей поисковой машины. Нам тоже многое не нравится, однако Яндекс - зеркало Рунета, а не цензор».

Информация, которая удаляется из интернета, удаляется и из поискового индекса. Поисковые роботы регулярно обходят уже проиндексированные сайты. Когда они обнаруживают, что какая-то страница больше не существует или закрыта для индексирования, она удаляется и из поиска. Для ускорения этого процесса можно воспользоваться формой « ».

В ответ на запрос, который пользователь ввел в поисковой строке, поисковая система показывает ссылки на известные ей страницы, в тексте которых (а также в метатегах или в ссылках на эти сайты) содержатся слова из запроса. В большинстве случаев таких страниц очень много - настолько, что пользователь не сможет просмотреть их все. Поэтому важно не просто найти их, но и упорядочить таким образом, чтобы сверху оказались те, которые лучше всего подходят для ответа на заданный запрос - то есть, наиболее релевантные запросу. Релевантность - это наилучшее соответствие интересам пользователей, ищущих информацию. Релевантность найденных страниц заданному запросу Яндекс определяет полностью автоматически - с помощью сложных формул, учитывающих тысячи свойств запроса и документа. Процесс упорядочивания найденных результатов по их релевантности называется ранжированием. Именно от ранжирования зависит качество поиска - то, насколько поисковая система умеет показать пользователю нужный и ожидаемый результат. Формулы ранжирования строятся также автоматически - с помощью машинного обучения - и постоянно совершенствуются.

Качество поиска - это самый важный аспект для любой поисковой системы. Если она будет плохо искать, люди просто перестанут ей пользоваться.

Поэтому нам важно постоянно совершенствовать алгоритмы ранжирования и делать их устойчивыми к внешнему влиянию (например, к попыткам некоторых вебмастеров обмануть поисковую систему).

Поэтому мы не продаем места в результатах поиска.

Поэтому на результаты поиска никак не влияют политические, религиозные и любые другие взгляды сотрудников компании.

Пользователи просматривают страницу результатов поиска сверху вниз. Поэтому Яндекс показывает сверху, среди первых результатов, те документы, которые содержат наиболее подходящие пользователю ответы - то есть наиболее релевантные заданному запросу. Из всех возможных релевантных документов Яндекс всегда старается выбрать наилучший вариант.

С этим принципом связано несколько правил, которые Яндекс применяет к некоторым типам сайтов. Все эти правила работают полностью автоматически, их выполняют алгоритмы, а не люди.

1. Существуют страницы, которые явно ухудшают качество поиска. Они специально созданы с целью обмануть поисковую систему. Для этого, например, на странице размещают невидимый или бессмысленный текст. Или создают дорвеи - промежуточные страницы, которые перенаправляют посетителей на сторонние сайты. Некоторые сайты умеют замещать страницу, с которой перешел пользователь, на какую-нибудь другую. То есть когда пользователь переходит на такой сайт по ссылке из результатов поиска, а потом хочет снова вернуться к ним и посмотреть другие результаты, он видит какой-то другой ресурс.

Такие ресурсы не представляют интереса для пользователей и вводят их в заблуждение - и, соответственно, ухудшают качество поиска. Яндекс автоматически исключает их из поиска или понижает в ранжировании.

3. По запросам, которые не подразумевают явно потребность в эротическом контенте, Яндекс ранжирует сайты для взрослых ниже или вообще не показывает их в результатах поиска. Дело в том, что ресурсы с эротическим контентом часто используют достаточно агрессивные методы продвижения - в частности, они могут появляться в результатах поиска по самым разнообразным запросам. С точки зрения пользователя, который не искал эротики и порнографии, «взрослые» результаты поиска нерелевантны, и, к тому же, могут шокировать. Более подробно об этом принципе можно почитать .

4. Яндекс проверяет индексируемые веб-страницы на наличие вирусов. Если обнаружилось, что сайт заражен, в результатах поиска рядом с ним появляется предупреждающая пометка. При этом зараженные сайты не исключаются из поиска и не понижаются в результатах поиска - может быть, на таком ресурсе находится нужный пользователю ответ, и он все равно захочет туда перейти. Однако Яндекс считает важным предупредить его о возможном риске.

8 июня вебмастера заметили, что у сайтов изменился один из самых известных показателей – тематический Индекс Цитируемости (тИЦ) . Яндекс в блоге для вебмастеров подтвердил обоснованность наблюдений, опубликовав сообщение об изменениях в алгоритме расчета тИЦ.

Что касается непосредственно изменений, то тут Яндекс был как всегда краток и лаконичен. Понятно одно: что-то изменилось в алгоритме, но что именно – осталось загадкой.

Обновление показателя тИЦ отметили многие сервисы, анализирующие выдачу. Вот такое сообщение появилось на Tools.promosite.ru :

Интересные наблюдения с форумов о том, что тИЦ подрос на сайтах, где ничего не делалось уже достаточно длительный срок:

Также сообщается, что замечены существенные увеличения тИЦ для некоторых ресурсов СМИ и для Яндекс.Каталога:

Мы отметили изменение тИЦ для наших клиентов, проанализировав показатель для сайтов, работы с которыми были закончены в мае 2016 по услуге «Поисковое продвижение », тариф «Продвинутый».

Общее настроение после июньского апа в целом хорошее. Большинство сообщений на форумах о том, что тИЦ вырос. Это же подтверждают и наши наблюдения. По сравнению с апом в апреле, этот был более удачным. При нашей проверке тИЦ изменился у 77% сайтов. И в положительную сторону у 58%.

Скачок выше 10 пунктов был отмечен у 33% сайтов из всех ресурсов с положительной динамикой. Максимальный рост составил 390 пунктов.

Отрицательная динамика наблюдалась в 19% случаев, из них потеряли свыше 10 пунктов только 28% ресурсов. Максимальное падение составило 70 пунктов.

В среднем график изменения тИЦ после апрельского апдейта для сайтов выглядит следующим образом: сначала падение позиций в апреле, потом подъем после обновления в июне. Это же неоднократно отмечалось и в Сети.

Для большинства ресурсов с положительной динамикой мы получили подобные графики изменений в позициях по тИЦ:

Если у вас коммерческий сайт, и вы не занимаетесь продажей ссылок, то, скорее всего, рост или падение тИЦ не играет для вас никакого значения.

Конечно, приятно, что показатель, о котором пишет чуть ли не весь Интернет, у вашего сайта вырос. Но если вы не понимаете, какая от этого польза, и при его изменении с сайтом решительно ничего не происходит, скажем, не меняется количество людей на сайте, позиции в поиске, процент конверсии, размер выручки и т.д., то можно особо и не заострять внимание на колебаниях этого индекса. Вот Google вообще недавно отменил обновление своей пузомерки (PR). Теперь никто не знает, сколько она составляет, насколько упала или выросла, а занимаются продвижением ресурсов.

Собственно, и вам советуем работать над комплексным продвижением сайта , а не над тИЦ. Следить не за пузмерками, а за изменением в большую сторону реальных KPI , по которым вы определяете эффективность своего бизнеса в Сети.

В течение последних двух лет Google и «Яндекс» неустанно меняли свои алгоритмы. Это нередко приводило к панике среди SEO-специалистов, но подыгрывало последователям органического SEO . Ведь все изменения, вводимые поисковыми системами, были направлены на уменьшение видимости страниц низкого качества и без добавленной ценности.

Так остались ли ещё методики продвижения сайтов, не приводящие к «фильтрации»? Какие стратегии оптимизации следует выбирать SEO-специалистам в 2015–2016 годах?

Что делать для успешного продвижения в Google?

1. Расширять семантическое ядро с учётом алгоритма «Колибри».

Алгоритм Hummingbird («Колибри») был запущен 20 августа 2013 года, но до сих пор многие SEO-специалисты не принимают его во внимание. «Колибри» кардинально изменил способ поисковой системы Google анализировать запросы: вместо сопоставления запросу отдельных ключевых слов на странице поисковик ищет соответствие общего смысла.

Ключевые слова по-прежнему важны, однако следует применять бóльшее их разнообразие, включая синонимы, поисковые подсказки и близкие по смыслу слова и словосочетания. Например, вместе с «ключом» «цветы» использовать фразы «букет ко дню святого Валентина» , «доставка цветов в день заказа» или «цветочная композиция» . Если возможно, т.е. если действительно есть что сказать по этому поводу, то вставлять и диалоговые фразы типа «где купить цветы дёшево?»

Все подобранные «ключи» необходимо разделить на три группы: информационные, навигационные и транзакционные.

• Информационные запросы (например, «как составить букет?» ) задают, когда ищут образовательный контент. Поэтому на сайте их следует использовать при создании информационных статей с ненавязчивыми ссылками на продукты или услуги.
• Навигационные запросы (например, «магазин ромашка» ) используют для поиска бренда, конкретного продукта или веб-ресурса, их рациональнее применять на страницах «Главная» и «О компании», например.
• Транзакционные же явно указывают на намерение совершить некое действие: заказать, купить, скачать. В этом случае используют слова «цена», «купить», «доставка», «аренда», «купон», «скидка» и пр. Подходящие места для них – странички товаров/услуг, акций и т.п.

В любом случае «ключи» не должны напоминать «коровью лепёшку» - несклоняемую и бессмысленную вставку в ткань повествования. Текст должен читаться плавно и естественно, ведь его воспринимает и оценивает Человек, поисковик же работает с «широким» семантическим ядром, а не повторённой 5 раз в «магических» формах и положениях фразой.

2. Совершенствовать структуру URL сайта.

Сайты с упорядоченной структурой адресов обычно ранжируются лучше, чем ресурсы с «грязной» структурой и запутанной организацией контента. URL-адреса и ссылки являются строительными блоками веб-сайта, а потому им следует уделять должное внимание.

• Динамические адреса типа site.ru/page?id=13579&color=4&size=2&session=754839 слишком длинные и не несут никакого смысла. Показатель кликабельности (CTR, click-through rate) таких ссылок в результатах поиска обычно ниже, поэтому стоит использовать статические человекупонятные урлы (ЧПУ).
• Множество «битых» ссылок , ведущих на страницу 404 ошибки, также может повредить позициям сайта при ранжировании. Необходимо время от времени проверять сайт на предмет возникновения неработающих ссылок, используя специальные программы, например, Screaming Frog .
• Ранее считалось, что большое количество исходящих ссылок со страницы негативно сказывается на её ранжировании в поиске, хотя это утверждение некоторые оспаривали. Сейчас Google уже отказался от регламентированного (не более 100 штук) количества ссылок с одной страницы, но настаивает на том, чтобы соответствовали тематике страницы и тем запросам, по которым люди на неё приходят.

3. Фокусироваться только на качественных, потом-кровью заработанных обратных ссылках, пусть их будет и немного.

За определение качества ссылочной массы и естественности анкор-листа в Google отвечает алгоритм «Пингвин» , последнее крупное обновление которого произошло 21 октября 2014 года (Google Penguin 3.0). 15 октября 2015 года началась новая итерация апдейта «Пингвина» - многие сайты, торгующие ссылками через биржу Sape, были понижены в выдаче.

Разработчики Google недвусмысленно нам говорят, что гораздо лучше иметь многочисленные ссылки с нескольких авторитетных нишевых ресурсов, чем сотни единичных ссылок со второсортных сайтов.

Как адаптировать сайт под мобильные устройства? Используйте, например, фреймворк Twitter Bootstrap. Это распространённая и очень удобная система вёрстки сайтов со стандартизированными шаблонами. А главное, что для дальнейшего улучшения сайта вам не придётся долго искать программиста, который смог бы разобраться в HTML-коде: с «Бутстрапом» знакомо большинство верстальщиков, которым не составит труда внести нужные изменения.

Как не потерять благосклонного отношения «Яндекса»?

1. Относиться к текстам как к основному инструменту продвижения.

Наряду с фильтром «Переоптимизация» «Яндекс» в середине 2014 года ввёл новый «Антиспам-фильтр» . Он похож на своего «старшего брата», но более жёсткий (приводит к потере позиций в выдаче вплоть до 1000) и учитывающий больше нюансов.

Что делать, чтобы не подвести свой сайт под «Антиспам-фильтр»?

• Уделять особое внимание длине и заспамленности ключевыми словами заголовков (title) и описаний (description) страниц.
• Не зацикливаться на прямых вхождениях «ключей» и ограничить общий процент использования ключевых слов и выражений. Это касается таких «экзотов», как «Где купить ххх дёшево?» , «Недорогие услуги... в городе N» и т.п., но не базовых словосочетаний типа названий товаров или отраслевых терминов, без которых невозможно донести информацию. В отношении последних действует обычный литературный «ограничитель» - критерий тавтологичности.
• Тщательно редактировать тексты: «Антиспам-фильтр» настроен на определение орфографических и пунктуационных ошибок.
• Не выделять «ключи» жирным, курсивом и другими способами. Делать это можно лишь в отношении фраз или слов, на которых стоят логические акценты для привлечения внимания читателя. Ничего нового, всё логично - выделяется главная мысль или термин, а не любой «ключ».
• По возможности заменять избыточные «ключи» словами из подсказок и «Спектра ».

2. Сосредоточиться на естественном линкбилдинге, приносящем трафик.

12 марта 2014 года «Яндекс» произвёл отмену ссылочного ранжирования по Москве и области для коммерческих запросов в ряде сфер. Не за горами отмена избыточного влияния ссылок и по всей России.

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

Это касается и ставших в последнее время модными всплывающих виджетов типа «Мы Вам перезвоним через 26 секунд», «Вы были на сайте уже 10 секунд! Нашли что-то полезное?» и пр.

а) Более 10 лет поиск в Google персонализируется в зависимости от многих факторов:

• Истории поиска . Если Вы ищете что-то в Google под своим аккаунтом, при формировании результатов поиска учитывается история минимум за год. И даже если Вы работаете с поисковиком анонимно, Google всё равно будет выдавать персонализированные результаты, поскольку при помощи файлов cookie хранит историю поиска в конкретном браузере за 180 дней. Не будешь же чистку каждый день устраивать...
• Предыдущего запроса. Google работает по механизму уточнения предыдущего запроса, предполагая, что Вы по нему нашли не всё, что искали, а потому предлагает страницы, связанные одновременно с текущим и предыдущим запросами.
• Географического положения пользователя. Результаты поиска, которые выдаются пользователю в одном городе, могут разительно отличаться от результатов по тому же поисковому запросу в другом городе. 24 июля 2014 года в США был запущен новый алгоритм Pigeon 1.0 («Голубь») , который резко изменил результаты локальной выдачи в связи с введением новых механизмов обработки и интерпретации сигналов местоположения. В итоге близость расположения бизнеса для пользователя Google стала чуть ли не главным фактором в поисковой выдаче. Даты внедрения нового алгоритма в других странах пока не озвучиваются.

б) «Яндекс» не отстаёт от западного конкурента в деле персонализации поиска: 12 декабря 2012 года российская компания запустила алгоритм «Калининград» , учитывающий историю поиска. В то же время «Яндекс» обращает внимание и на географическое положение пользователя, а также разделяет запросы на геозависимые (по которым выдача привязана к региону) и геонезависимые (результаты поиска не зависят от региона пользователя).

Таким образом, вокруг каждого пользователя формируется поисковый пузырь , из которого не так-то легко выбраться. Это порождает массу иллюзий, например, у владельцев сайтов. Нужно просто принять, что практически невозможно узнать, на каких позициях в SERP Ваш сайт видят другие люди. Чтобы получить действительно точные данные по неперсонализированным позициям, следует использовать специальные программы или онлайн-сервисы, например, AllPositions (платный), «Энергослон» (платный), SEOGadget (бесплатный, но с ограничением количества проверок в день).

Но не надо заблуждаться и в отношении этого инструмента - он тоже не отражает реальную видимость ресурса (как мы поняли, она вообще индивидуальна). Увидеть сайт на позициях, определённых программами, может только ОН, Уникум анонимикус , постоянно уничтожающий cookies, генерирующий новые IP и т.п., или же впервые воспользовавшийся браузером где-то на орбите (а может, и там пеленгуют?). Но несмотря на то, что этот инструмент обитает в вакууме, он полезен, просто цель у него другая - оценка в динамике эффективности прикладываемых усилий по развитию ресурса . Иными словами, неперсонализированные позиции помогают понять, одобряет или нет поисковик вашу деятельность. А уж где в SERP сайт увидят Маша или Вася, сильно зависит от их сетевого поведения.

29 июля в Минске прошёл финальный раунд чемпионата по программированию Яндекс.Алгоритм . Победителем стал Егор Куликов - выпускник мехмата МГУ и бывший сотрудник Яндекса. Второе место - у Николы Йокича из Швейцарской высшей технической школы Цюриха. В составе команды школы он был финалистом ACM ICPC. Третье место занял Макото Соэдзима , выпускник Университета Токио. Геннадий Короткевич , победитель двух предыдущих Алгоритмов, занял шестое место.

Как и в прошлые годы, мы публикуем подробный разбор финальных задач. 31 июля мы впервые провели зеркало Алгоритма. Поэтому, чтобы не испортить его участникам удовольствие, не стали публиковать ответы сразу же после финала, как мы это обычно делаем.

В этом году мы получили на четверть больше заявок на участие в Алгоритме, чем год назад, - 4578. Среди участников пока немного девушек - 372. В списке зарегистрировавшихся есть представители 70 стран; больше всего соревнующихся - из России, Индии, Украины, Беларуси, Казахстана, США и Китая. В финале приняли участие 25 человек.

Задачи для Яндекс.Алгоритма составляют сотрудники Яндекса и приглашённые эксперты, среди которых - финалисты и призёры ACM ICPC. По условиям состязания, участники могут использовать разные языки программирования. Статистика Яндекс.Алгоритма показывает, что самый популярный язык - С++; его выбрали более двух тысяч человек. Второе место поделили Python и Java.

Задача A. Место проведения финала

В этом году финал Яндекс.Алгоритма проходит в Национальной библиотеке Беларуси. Хочется отметить, что здание библиотеки имеет весьма необычную форму - ромбокубоктаэдр.

Ромбокубооктаэдр это полуправильный многогранник, гранями которого являются 18 квадратов и 8 треугольников. Всего у ромбокубооктаэдра 24 вершины и 48 ребер. Изображение ромбокубооктаэдра представлено ниже:

В этой задаче вам требуется определить количество способов покрасить грани ромбокубоктаэдра таким образом, чтобы никакие две грани, имеющие общее ребро, не были покрашены в один цвет. Всего в вашем распоряжении имеется k цветов.

Так как ответ может достаточно большим, вычислите его по модулю 10 9 + 7.

Формат входных данных

В единственной строке входных данных записано одно целое число k (1 ⩽ k ⩽ 50), количество цветов в вашем распоряжении.

Формат выходных данных

В единственной строке выведите ответ на задачу.

Примеры

стандартный ввод	стандартный вывод
1	0
3	356928

Замечание

Одним из вариантов корректной раскраски для k = 3 будет покрасить все треугольные грани в первый цвет (8 граней), все квадратные грани, смежные по ребру с одной из треугольных граней, во второй цвет (12 граней), и все оставшиеся квадратные грани в третий цвет (6 граней).

Разбор задачи A

Рассмотрим новый граф, вершинами которого являются грани ромбокубооктаэдра, а рёбрами соединены те вершины, которые соответствуют граням, смежным по стороне (так называемый двойственный граф многогранника). Наша задача принимает следующий вид: нужно посчитать количество правильных раскрасок получившегося графа в k цветов, где правильная раскраска - это такая раскраска, что соседние вершины окрашены в разные цвета.

Заметим, что наш граф является двудольным: его вершины можно разбить на две группы, состоящие из 12 вершин и из 14 вершин, таким образом, что рёбра соединяют только вершины разных групп. На самом деле, в условии даже указано, как именно устроено это разбиение: первую долю разбиения образуют вершины, которые в пояснении предлагается покрасить во второй цвет, а вторую долю - все остальные.

Будем сначала красить первую долю, а только потом вторую. Заметим, что при фиксированной раскраске первой доли посчитать количество способов, которыми можно докрасить вторую долю, не составляет труда: каждую вершину второй доли мы красим в отдельности, а значит, общее число способов есть произведение по всем вершинам второй доли v величины k − adj(v), где adj(v) - количество различных цветов среди вершин, смежных v.

Теперь надо каким-то образом перебрать раскраску первой доли. Если явно перебирать цвет для каждой вершины, это потребует порядка 50 12 ≈ 2,4 · 10 20 операций, что не уложится ни в какие разумные временные рамки. Будем перебирать не сами цвета вершин, а только их разбиение на одинаковые/разные цветовые группы. А именно - для каждой очередной вершины в ходе перебора будем принимать решение, отнести ли её к одному из уже имеющихся цветов вершин, либо завести ли для неё новый. Таких «сжатых» раскрасок уже не так много, всего 4 213 597 штук. Очевидно, информации, содержащейся в сжатой раскраске первой доли, достаточно для того, чтобы понять, сколькими способами можно докрасить вторую долю, надо только не забыть умножить это число на количество способов превратить данную сжатую раскраску в полноценную раскраску (оно равняется A(k, c) = k(k − 1)(k − 2)...(k − c + 1), где c - количество использованных в сжатой раскраске цветов).

Если написанное решение не укладывается в ограничение по времени, но работает не сильно долго на одном тесте, то можно схитрить и воспользоваться тем, что ограничение на k не очень большое, посчитав на локальном компьютере все 50 ответов на тесты и просто вбив в программу.

Альтернативное решение может перебирать раскраску на поясе из 8 средних квадратов, а дальше считать количество способов докрасить одну из половин и возводить его в квадрат, так как верхняя и нижняя половина ромбокубооктаэдра красятся независимо друг от друга.

Задача B. Преобразование последовательности

Вам дана последовательность a 1 , a 2 ,..., a n , исходно состоящая из n нулей. За один ход вы можете выбрать любой её подотрезок a l , a l+1 ,...,a r , а также произвольное целое число x и преобразовать последовательность этот подотрезок, заменив a l+k на a l+k + (−1) k · x для всех целых 0 ⩽ k ⩽ r − l.

Требуется преобразовать исходную нулевую последовательность в данную последовательность b 1 , b 2 ,..., b n за минимальное число ходов. Имеется важное ограничение на последовательность b i: гарантируется, что все её элементы принадлежат множеству {−1, 0, 1}.

Формат входных данных

В первой строке входных данных находится единственное целое число n (1 ⩽ n ⩽ 10 5). Вторая строка содержит n целых чисел b 1 , b 2 ,..., b n (−1 ⩽ b i ⩽ 1).

Формат выходных данных

Выведите минимальное число ходов, необходимое для того, чтобы преобразовать исходную последовательность в требуемую.

Примеры

стандартный ввод	стандартный вывод
2 -1 1	1
5 1 -1 1 1 0	2

Замечание

В первом тесте из условия можно получить требуемую последовательность за один ход, в котором x = −1, l = 1 и r = 2.

Во втором тесте из условия можно действовать следующим образом:
0 0 0 0 0 → 2 -2 2 0 0 → 1 -1 1 1 0

Разбор задачи B

Будем постепенно разбираться в конструкции. Во-первых, инвертируем знаки у всех чисел, стоящих на чётных позициях. Теперь операция, указанная в условии, будет действовать проще: нам разрешается выбрать любой подотрезок и прибавить ко всем числам на нём одно и то же число t.

Раз мы имеем дело с операциями вида «прибавить на подотрезке одно и то же число», то полезно перейти к последовательности, состоящей из разностей соседних элементов: перейдём от a 1 , a 2 ,...,a n к последовательности b 0 = a 1 , b 1 = a 2 − a 1 ,..., b i = a i+1 − a i ,..., b n = −a n . В этой последовательности элементов на один больше, и она удовлетворяет специальному условию, что b 0 + b 1 +… + b n = 0.

Тогда прибавление константы x на отрезке исходной последовательности эквивалентно замене b l−1 → b l−1 + x и b r → b r − x.

В последовательности a i встречались целые числа от −1 до 1, поэтому в последовательности b i будут встречаться целые числа от −2 до 2. За один ход, как мы уже выяснили, мы можем к одному из чисел прибавить x, а из другого вычесть x, и мы хотим добиться, чтобы в последовательности были одни нули.

Назовём «весом» операции прибавления x и −x к двум элементам последовательности величину |x|.

Докажем вспомогательный факт: если число b i больше (меньше) нуля, то не выгодно применять операции, в которых число b i увеличивается. Формально говоря, если есть оптимальная (т. е. кратчайшая) последовательность операций, в которой какое-то b i в какой-то момент увеличивается, то можно предъявить последовательность операций, в которой ни одно b i никогда не увеличивается, и которая имеет ту же длину.

Действительно, пусть к b i применялись две операции, скажем, 1) b i → b i + x, b j → b j − x и 2) b i + x → b i + x − y, b k → b k +y, и, для определённости, где x,y > 0 и, для определённости, x ⩽ y.

Давайте заменим эти две операции на две других: 1) b i → b i − (y − x) = b i + x − y, b k → b k + y − x и b j → b j − x, b k + y − x → b k + y − x + x = b k + y. Это две эквивалентные операции, они приводят к тем же результатам, но можно увидеть, что суммарный вес двух новых операций уменьшился: |y − x| + |x| = y − x + x = y < x + y = |x| + |y|.

Повторяя такие замены, пока возможно, мы рано или поздно остановимся (потому что суммарный вес операций не может неограниченно убывать, так как он всегда целый и неотрицательный), а значит, можно найти последовательность операций той же длины, в которой любой положительный элемент всегда только уменьшается. Аналогично можно добиться того, что любой положительный элемент будет только увеличиваться.

Это позволяет описать все доступные нам операции. Мы можем либо избавиться от −2 и 2 за один ход, либо избавиться от −1 и 1 за один ход, либо избавиться от −2, 1, 1 за два хода, либо избавиться от 2, −1, −1 за два хода.

Понятно, что суммарный вес всех операций, которые мы произведём, есть сумма всех положительных чисел среди b i (которая противоположна по знаку сумме всех отрицательных чисел). У нас теперь бывают операции веса 1 и веса 2, и понятно, что чтобы минимизировать общее число операций, надо сделать как можно больше операций веса 2. Это приводит нас к жадному алгоритму, а именно - сокращать двойки с минус двойками, пока можем, а когда не больше не можем, сокращать единички и минус единички с чем получится.

Таким образом, ответ это сумма всех положительных b i минус минимум из количества двоек и количества минус двоек.

Задача C. Игра в шляпу

Шляпа это популярная в русскоговорящих странах игра, рассчитанная на большую дружную компанию. Участники разбиваются на команды по двое и садятся в круг таким образом, чтобы каждый сидел строго напротив своего партнёра. Играющие пишут множество слов на маленьких бумажках, кладут их в шляпу, после чего каждый из игроков по очереди пытается объяснить своему партнёру выпадавшее ему слово, не называя его при этом явно.

Рассмотрим следующую задачу. За круглым столом сидят 2n людей. Они хотят поиграть в шляпу, и они уже разбились некоторым образом на команды по двое. Теперь они хотят пересесть таким образом, чтобы каждый человек сидел напротив своего партнёра. Для этого они могут несколько раз произвести следующую операцию: они выбирают двух людей из сидящих за столом и просят их поменяться местами.

Вам дано начальное расположение людей за столом. Определите, какое минимальное количество операций описанного вида надо произвести, чтобы каждый человек сидел напротив своего партнёра.

Формат входных данных

В первой строке входных данных находится целое число n (1 ⩽ n ⩽ 10 5), означающее, что за столом сидят 2n человек.

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

Формат выходных данных

Выведите минимальное число операций, которые надо произвести, чтобы каждый человек оказался напротив своего партнёра.

Примеры

стандартный ввод	стандартный вывод
3 2 1 3 2 1 3	0
4 2 1 4 2 3 1 3 4	2

Замечание

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

Во втором тесте из условия один из оптимальных способов будет сначала поменять местами людей, сидящих на первой и седьмой позициях, а потом поменять местами людей, сидящих на седьмой и восьмой позициях, что приведёт нас к корректной рассадке: 3 1 4 2 3 1 4 2.

Разбор задачи C

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

Получившийся граф обладает тем свойством, что в нём из каждой вершины ведёт ровно два ребра (одно - диаметр, а второе - в вершину, в которой сидит человек из той же команды). Такой граф всегда представляет из себя объединение из какого-то количества циклов.

Мы стремимся достигнуть ситуации, когда каждый цикл состоит ровно из двух диаметрально противоположных вершин, то есть когда всего имеется ровно n циклов длины 2.

Поймём, как меняется наш граф под воздействием доступной нам операции. Пусть поменяли местами двух людей не из одной команды (иначе это бессмысленная операция), скажем, человека из вершины a с человеком из вершины b. Пусть партнёр человека a сидит в вершине a′, а партнёр человека b сидит в вершине b′. Тогда из графа пропадут два ребра aa′ и bb′ и образуются два новых ребра ba′ и ab′ (то есть новые рёбра будут идти крест-накрест между концами старых). Легко видеть, что такая операция может либо один цикл разъединить на два, либо не изменить количество циклов, либо склеить два цикла. Значит, ответ никак не меньше, чем n − c, где c - исходное количество циклов. С другой стороны, всегда можно добиться требуемого ровно за столько ходов: достаточно на каждом шаге брать пару сокомандников, которые сидят не друг напротив друга, и просто пересаживать одного из них так, чтобы он сел напротив своего партнёра. Эта операция строго увеличивает количество циклов на один.

Таким образом, ответ есть n − c, где c - количество циклов, или, что то же самое, компонент связности в указанном графе. Эту задачу можно решить и просто явно моделируя процесс рассаживания людей по парам, и это корректно по тем же причинам, которые описаны выше.

Задача D. Кучефицируй меня полностью

Вы - простой паренёк, который хочет лишь одного: чтобы ему на день рождения подарили двоичную максимальную кучу, потому что у всех ваших друзей уже такая есть! Наконец, вы пошли с родителями в магазин, но, к сожалению, там закончились все двоичные кучи, и всё, что осталось - это старое полное двоичное дерево. Оно состоит из n = 2 h − 1 вершин, в которых записаны некоторые значения, не обязательно удовлетворяющие главному свойству максимальной кучи. К счастью, Старый Джо согласился помочь вам превратить это дерево в двоичную кучу за определённую плату.

Полное двоичное дерево высоты h это корневое дерево, состоящее из n = 2 h − 1 вершин, пронумерованных от 1 до n, такое, что для любого 1 ⩽ v ⩽ 2 h-1 − 1 вершина v является предком для вершин 2v и 2v + 1.

Двоичная максимальная куча высоты h это полное бинарное дерево высоты h, у которого в вершинах находятся значения h 1 , h 2 ,..., h n , при этом значение в любой вершине не меньше, чем значение в её детях (если у неё есть дети).

Вам дано полное бинарное дерево высоты h, в вершинах которого находятся значения a 1 ,a 2 ,...,a n . Также, с каждой вершиной связана стоимость c v , означающая, что Старый Джо может как увеличить, так и уменьшить значение в вершине v на произвольную величину x > 0 за стоимость в c v x. Вы можете менять значения в произвольном количестве вершин.

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

Формат входных данных

В первой строке ввода находится единственное целое число n (1 ⩽ n ⩽ 2 18 −1), количество вершин в полном бинарном дереве, которое вам досталось. Гарантируется, что n = 2 h − 1 для некоторого целого h.

Во второй строке ввода находятся n целых чисел a 1 , a 2 ,..., a n (0 ⩽ a i ⩽ 10 6), текущие значения вершин дерева.

В третьей строке находятся n целых чисел c 1 , c 2 ,..., c n (0 ⩽ c i ⩽ 10 6), стоимости изменения значений в вершинах дерева.

Формат выходных данных

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

Пример

стандартный ввод	стандартный вывод
7 4 5 3 1 2 6 6 4 7 8 0 10 2 3	19

Замечание

В тесте из условия оптимальным способом будет увеличить значение в вершине 1 на 2 ценой в 4 · 2 = 8 и уменьшить значения в вершинах 6 и 7 на 3 ценой в 2 · 3 = 6 и 3 · 3 = 9 соответственно. Таким образом, общая стоимость будет равна 8 + 6 + 9 = 23.

Разбор задачи D

Введём обозначения. Пусть L v (x) - это минимальная цена, которую надо заплатить, чтобы поддерево вершины v стало корректной кучей, а в самой вершине v стояло число, не превосходящее x. Пусть S v (x) - это величина, которая определяется абсолютно аналогично, только в самой вершине v должно стоять строго число x. Тогда ответ на задачу равняется значению минимума функции S v (x).

Для листовых вершин v по условию имеем, что S v (x) = c v |x − a v |. Аналогично можно понять, что L v (x) = max{0, c v (a v − x)}.

Выразим S v (x) через L 2v (x) и L 2v+1 (x) (то есть функцию S вершины v через функции L её детей). Верно следующее соотношение:

S v (x) = c v |x − a v | + L 2v (x) + L 2v+1 (x).

Действительно, если в вершину v мы ставим значение x, то мы платим, во-первых, за изменение самой вершины v, и во-вторых, мы должны поменять поддеревья v каким-то образом, чтобы значение в v оказалось не меньше значений в её детях, а эту стоимость мы можем получить из функции L для детей.

L v (x) мы сейчас научимся считать по S v (x). Но давайте в этом месте остановимся и выскажем предположение, какой вид имеют функции L v и S v . Можно догадаться, что они будут кусочно-линейными функциями переменной x, но на самом деле верно даже более сильное условие: они будут выпуклыми кусочно-линейными функциями (другими словами, угол наклона каждого следующего звена возрастает). Давайте строго это докажем: пусть это верно для вершин 2v и 2v + 1. Тогда S v (x), как следует из формулы выше, тоже выпуклая кусочно-линейная функция (так как является суммой трёх выпуклых кусочно-линейных функций).

Теперь уже L v (x) легко получить по S v (x): рассмотрим точку глобального минимума S v (x). До этой точки S v (x) убывает, а после неё возрастает. Для того, чтобы получить L v (x), надо просто заменить участок возрастания S v (x) на константный горизонтальный участок со значением, равным глобальному минимуму функции S v (x).

Заметим, что для того, чтобы задать функции L v и S v , нужно O(size(v)) информации о точках излома этих функций, где size(v) - это размер поддерева вершины v. Действительно, точек излома в графике функции S v (x) не больше, чем суммарно точек излома в графиках функций S 2v и S 2v+1 плюс ещё одна точка излома из-за слагаемого c v |x − a v |. Получается рекуррента T(v) = T(2v) + T(2v + 1) + 1 на количество хранимой в худшем случае информации, решением которой является T(v) = size(v).

Непосредственно реализовать основную формулу, используемую в задаче, можно за линейную сложность от размеров сливаемых функций. Таким образом получается решение за size(v) = nk = n · log 2 n.

Задача E. Отделяй и властвуй

Последовательность чисел называется хорошей , если ее можно построить согласно следующим правилам:

• пустая последовательность является хорошей;
• если X и Y - хорошие последовательности, то XY (конкатенация X и Y) также является
  хорошей;
• если X - хорошая последовательность, а n - любое число, то nXn (число n, потом все элементы X, и, наконец, опять число n) также является хорошей последовательностью.

Например, последовательность (1, 2, 2, 1, 3, 3) является хорошей, а последовательность (1, 2, 1, 2) - нет.

Последовательность называется разделимой, если существует способ разбить ее на две хорошие подпоследовательности (любая из них может быть пустой). Например, последовательность (1, 2, 1, 2) является разделимой (поскольку ее можно разбить на хорошие подпоследовательности (1, 1) и (2, 2)), а последовательность (1, 2, 3, 1, 2, 3) - нет.

Рассмотрим все последовательности из 2n чисел, такие что каждое число от 1 до n встречается ровно дважды. Сколько из них являются разделимыми? Найдите ответ по модулю 10 9 + 7.

Формат входных данных

В единственной строке ввода записано одно целое число n (1 ⩽ n ⩽ 500).

Формат выходных данных

Выведите одно целое число - ответ на задачу по модулю 10 9 + 7.

Примеры

стандартный ввод	стандартный вывод
1	1
2	6
4	2016

Разбор задачи E

Как проверить, является ли последовательность отделимой? Для данной последовательности построим граф на n вершинах. Вершины i и j соединим ребром, если пары соответствующих чисел нельзя включить в одну ПСП (т. е., например, когда числа расположены как (i, j, i, j) либо (j, i, j, i), но не (i, i, j, j) или (i, j, j, i)). Последовательность отделима тогда и только тогда, когда получившийся граф двудолен.

Обозначим за f(n) количество отделимой последовательностей из n пар чисел, при этом последовательности, отличающиеся перенумеровкой чисел, мы будем считать одинаковыми. Введем вспомогательную функцию g(n) - количество примитивных последовательностей, т. е. отделимой последовательностей из n пар чисел, для которых существуют ровно один способ разделения на две ПСП (это в точности те же последовательности, для которых граф, описанный выше, связен).

Пусть мы знаем значения g(n), вычислим теперь f(n). Для произвольной отделимой последовательности рассмотрим компоненту связности, содержащую первое число. Пусть она содержит k пар чисел, тогда между ее элементами есть 2k промежутков, в каждый из которых можно поставить любую отделимой последовательность независимо друг от друга. Обозначим F (n, k) количество способов выбрать k отделимых последовательностей суммарной длины 2n. Тогда из рассуждений выше получаем f(n) = g(k) F(n − k, 2k). Величины F(n, k) тривиально пересчитываются друг через друга и очередные значения f(n).

Как найти g(n)? Назовем конфигурацией спобов разбить 2n элементов на два множества и построить ПСП на каждом из них независимо. Количество конфигураций на 2n элементах t(n) вычисляется тривиально. Вычтем из этого количества все конфигурации, не относящиеся к примитивным последовательностям, оставшееся количество будет равно 2g(n). Снова рассмотрим компоненту связности, содержащую первое число, пусть в ней k пар чисел. Количество таких конфигураций равно 2g(k) T(n − k, 2k), где T (n, k) - количество способов выбрать k конфигураций с суммарным количеством элементов 2n. Таким образом, g(n) = (T(n) − g(k) T(n − k, 2k). Величины T(n, k) вычисляются тривиально через t(n), которые находятся явно. Суммарная сложность этого решения O(n 3).

Задача F. Дроби

Задана последовательность a 1 , a 2 ,..., a n , элементы a i которой являются дробями, записанными в виде p/q, где p - целое, а q - целое положительное (при этом их взаимная простота не гарантируется).
Проверьте, что для каждой пары i,j (1 ⩽ i < j ⩽ n) существует как минимум одно 1 ⩽ k ⩽ n такое, что a i · a j =a k .

Формат входных данных

Первая строка входных данных содержит одно целое число n (1 ⩽ n ⩽ 3 · 10 5) - длину последовательности. В следующей строке записаны n дробей в формате p/q (p и q целые, |p| ⩽ 10 9 , 1 ⩽ q ⩽ 10 9).

Формат выходных данных

Выведите «Yes», если для каждой пары различных i и j найдётся требуемое k, и «No» в противном случае.

Примеры

стандартный ввод	стандартный вывод
1 7/42	Yes
3 3/3 0/1 -5/5	Yes
2 2/1 3/2	No

Разбор задачи F

Сократим все дроби. Произведём несколько наблюдений.

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

Во-вторых, заметим, что в каждом из множеств 0 < |x| < 1 и 1 < |x| есть не более одно го числа. Действительно, если, например, на 0 < |x| < 1 есть больше одного числа, то выберем из всех представленных там чисел два минимальных по абсолютному значению (скажем, a и b), возьмём их произведение ab, и оно будет иметь ещё меньшее ненулевое абсолютное значение: 0 < |ab| = |a||b| < min{|a|, |b|}, а значит, оно не совпадает ни с одним из чисел в нашем множестве. Аналогично с диапазоном 1 < |x|.

Таким образом, после сокращения и удаления дубликатов при условии, что ответ - Yes, в нашем множестве может быть не более восьми чисел: два нуля, две единицы, две минус единицы и по одному числу из указанных диапазонов. Значит, можно придерживаться следующей логики: сократим все числа, оставим от каждого числа не более двух его копий. Если получилось больше восьми чисел, то ответ однозначно No, иначе можно рассмотреть все пары чисел, благо их совсем немного, и честно проверить требуемое условие.