См. https://docs.google.com/document/d/1g4ntoEf9MdLbgrP2iFyC3XF1ytCuhEq2EAzcVH7CryQ/edit
Замечания, предложения и вопросы приветствуются.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.11.2024 08:03:23 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Надеюсь, я правильно понял условие. Найти X: 1 ≤ X ≤ N, кол-во делителей X максимально. X не кратно P. Всего 42 * 42 таких тестов. N ≤ 4242.
Решим сперва без ограничения "не кратно P".
Теперь переделываем это решения для нашего ограничения... Т.е. вставляем в перебор нужный if.
Разве это не зайдет?
P.S. С точки зрения длинки нужны умножение на короткое, деление на короткое, двоичный логарифм.
UPD: Sorry, что по-русски. Надеюсь, google translate справится.
случайно отправилось, см. следующее
Я подобный алгоритм исследовал. И ещё тогда думал " [user:Burudnuk1] возможно сумеет его дооптимизировать до прохождения". Не помню где, кажется в одной из газет харьковской зимней школы, была примета: "если у тебя на любую задачу проходят решения через ветви и границы — значит, ты [user:Burudnuk1] ".
А если серьёзно — для задачи без запрещённых P отсекать эти ветви и границы от предложенного мной двольно трудно. А с запрещённым P , оптимизации ветвей и границ становятся менее оптимизирующими (не всегда правда, что a1 ≥ a2 ≥ a3 ≥ ...). И у меня получалось, что не всегда выгодно "степени a[i] от 1 до a[i-1] (**по возрастанию**)", а как лучше — тоже не очень понятно. Да и многие N для одного P тоже делались осознанно для того, чтоб люди придумывали что-то отличное от изложенных ветвей и границ.
Так что мне очень интересно увидеть эклюзивное решение от Burunduk1 — оно таки будет проходить или таки нет, и если будет, то его таки можно будет свалить, расширив набор тестов, или таки нет.
Кстати, именно цель непрохождения таких ветвей и границ была главной причиной почему я давал задачу именнно с длинной арифметикой, а не в пределах long long (за что меня сегодня критиковал KADR).
Согласен, про "добавим один if, чтобы запретить P" я погорячился. Там несколько случаев, но вроде силу всех отсечений можно сохранить.
А какой номер у этой задачи? H? На официальном сайт SEERC вроде результаты уже есть, а условий пока нет.
Тестов я тоже не нашел. Судя по всему у Вас есть доступ к ним :-) Если Вы скините мне архив с тестами и авторское решение на [email protected], в течение пары дней готов реализовать вышеприведенную идею.
P.S. Забыл еще одну оптимизацию. Можно использовать то, что суффиксы совпадают... Начиная с некоторого места, все a[i] = 1. Если выделить общий суффикс, и на него можно поделить, числа уменьшатся, длинка будет работать быстрее.
F
"(не всегда правда, что a1 ≥ a2 ≥ a3 ≥ ...)" Если есть pi^ai и pj^aj (pi<pj) и по-вашему ai<aj, то можно поменять ai и aj местами, при этом кол-во делителей не изменится, а число уменьшится. Это ведь чертовски очевидно :о
При наличии запрещённого числа — не всегда. Хотя бы пример из условия, там 40 = 2^3 * 3^0 * 5^1, и 3>=0>=1 == false.
Это как бы на реализацию сильно не влияет. Просто смотрим чтобы хотя бы по одному простому множителю числа Р искомое число имело меньшую степень.
Что не влияет? Условие собирались использовать для отсечений в ветвях и границах, потом оказывается, что оно не всегда правильное и поэтому его использовать можно только частично и очень осторожно — и это всё не влияет на скорость работы?
Предъявите, пожалуйста, эффективное переборное решение этой задачи. У меня что-то похожее есть (и было до тура), но оно на полном тесте работает где-то 5 часов (против 1,2 сек у предложенного в разборе). Ещё мне казалось, будто я сумел дооптимайзить переборное, чтоб оно работало где-то за 20 минут, но чисто случайный stress test таки нашёл контрпример (тест, на котором та оптимизация даёт WA).
И главное: если я напрасно думал, что такой подход будет не проходить (то есть на самом деле он работает) — ну то где же бОльшее, чем планировалось, количество OK-ов за задачу? Где хотя бы решения, написанные потОм?
Я всего лишь высказался по поводу последовательности степеней, а не по поводу решения.
Хорошо, с утверждением "в последовательности степеней a1, a2, ..., ak, ... будет не более одного места, где aj < aj + 1, причём такое возможно только если запрещённое число P делится на простое pj" я согласен. Только вот оно даёт ветвям и границам гораздо более слабые отсечения, чем сформулированное изначально a1 ≥ a2 ≥ ... ≥ ak ≥ ...