Предлагаю обсудить задачи с SEERC 2015. Задачи есть в тренировках. [contest:100818]
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Интересует задача C.
Можно для делителя числа N подсчитать prob[i], где i = 0,1,..35.
prob[i] — вероятность того, что всё закончится за i шагов.
Только это даёт TLE. Так как я для каждого такого числа перебираю его делители за sqrt(N).
Как ускорить? Или есть другое решение?
Простых чисел до sqrt(N) меньше 10000, поэтому найти разложение заданных чисел в простые можно за менее 100 миллионов операций.
Заметим, что нам не важно, какие именно простые входят в данное число, важно лишь количество каждого отдельно взятого простого. Возьмём все такие количества и сложим их в вектор, который отсортируем по неубыванию. Будем использовать динамику с запоминанием ответов для таких векторов. Тогда для каждого вектора мы посчитаем описанную Вами prob[i] всего один раз. Уникальных векторов, в отличие от чисел, не очень много, поэтому все 10000 тестов проходятся очень быстро, потому что для одних тестов используются запомненные значения из других.
Код: http://ideone.com/gJXUtq
Хотелось бы узнать, как решать A и C?
Задачу A все решают рандомом. Пока есть время, то всем переменным присваиваем значения случайным образом, затем находим значения выражений. Если они не равны, то выводим нолик. Если время подходит к концу, то выводи единичку.
Мне кажется, что тесты очень-очень слабые, так как на таком тесте
a ^ b ^ c ^ d ^ e ^ f ^ g ^ h ^ i ^ j ^ k ^ l ^ m ^ n ^ o ^ p ^ q ^ r ^ s ^ t ^ u ^ v ^ w ^ x ^ y ^ z ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^ L ^ M ^ N ^ O ^ P ^ Q ^ R ^ S ^ T ^ U ^ W ^ X ^ Y ^ Z
a ^ b ^ c ^ d ^ e ^ f ^ g ^ h ^ i ^ j ^ k ^ l ^ m ^ n ^ o ^ p ^ q ^ r ^ s ^ t ^ u ^ v ^ w ^ x ^ y ^ z ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^ L ^ M ^ N ^ O ^ P ^ Q ^ R ^ S ^ T ^ U ^ W ^ X ^ Y ^ ~ Z
любой рандом выведет 1, хотя есть набор пременных (1111..111 или 1111..110) при которых уравнения не равны. Всего 2^51 вариантов, угадать 2 из 2^51 — без шансов. =)
Хотел передать авторам задач "привет"! Автор задач А и В — найдись!
SEERC в тренировки на codeforces добавил Temirulan, так что спроси у него, кто авторы задач =)
А куда делась задача G?
Не сразу понял о чём вы. Даже не заметил этого.) Видимо авторы забыли добавить задачу в треньку =)
Официальные тесты этой задачи видимо некорректны. На все тесты у них один ответ:
eroare deschidere fisier 0Интересно, какое количество команд приглашается с этого регионального этапа на финал? На baylor искал, не нашёл такой инфы.
а куда делась тренировка? Это из-за контеста так или кто-то ее спрятал?
Интересная ситуация :) только собирались написать ее, а уже нечего...
Подскажите, как решать F?
Корни нашего полинома могут быть целыми, рациональными (дробь) или иррациональными.
Рациональных корней не будет, так как самый первый коэффициент равен 1.
Док-во тут
Итак, перебираем 21 возможных целых корней (от -10 до 10). Учитываем сколько раз он встретился. Для этого делим наш полином на (x-v) до тех пор, пока делится "без остатка", где v — это корень. (Или же юзаем схему Горнера) Ответ на задачу: N — количество_целых_корней.
Задача А подозрительно напоминает NP-трудную. И ограничение 0.2 секунды. Это шутка такая?
Да, у румынских авторов интересное чувство юмора. Они часто пытаются развеселить участников подобным образом, это уже не первый год) Со временем к таким вещам начинаешь привыкать...
Вики говорит, что задача нехорошая, да.
Да, разумеется, co-NP, тавтология же, а не выполнимость.
А на разборе что-нибудь разумное по этому поводу было? Хотя бы идея авторского решения...
.>>>SEERC
.>>>разбор
))))))
Не понял прикола. Нужен кэп.
В Виннице разбор обычно проводится силами участников. Об авторских решениях румынских задач ничего не было известно.
Получается, что после контеста те ребята, которые что-то решили, выходят на сцену и рассказывают как они решали??? =)
omg! Отбор на финал, который хуже Воронежа. Остановите планету, я сойду!
А также ещё шутки: в задаче говорится, что в строке не более 51 переменной (это логично 26 строчных + 25 заглавных), но нигде не написано про длину выражения. Может там такой есть тест: (((...(A ^ B)...))), где количество скобок ~1e6 штук. =) Например в 3 тесте длина выражения без пробелов ~600 символов, суммарное количество переменных (с повторами) ~160.