| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
В воскресенье 2 сентября состоится тестовый 5-часовой раунд. Этот раунд является зеркалом очного финала открытого кубка. Финал проходит на сборах в Петрозаводске, а все желающие смогут написать его на contest.yandex.ru.
Время начала тестового раунда в 10-00 по московскому времени. На контест Mirror of XI Open Cup Onsite можно зарегистрироваться уже сейчас.
контест командный или личный? Или все таки надо учесть влияние ПТЗ на сложность задач =D
Контест командный, но писать естественно можно и лично.
довольно интересное влияние ПТЗ на сложность задач =)
И все же как решались B, F, I, J. В F какие-то суффиксные мудрости? В J — максимальный поток О_о или обычная жадина? Кто как решал?
B: заметим, что d(a, b) = d(a, gcd(a, b)) + d(b, gcd(a, b)). Значит, можно сделать meet-in-the-middle: для каждого числа переберем все его делители, и пометим, что от такого-то делителя можно дойти до такого-то числа за такое-то количество ходов. Потом нужно как бы перебрать этот gcd и построить сами ответы.
I: понятно, что зная массу минимальной частицы, можно однозначно восстановить все остальное. Я просто перебирал эту массу и тупо восстанавливал с каким-то количеством отсечений.
J: жадность, какой там может быть поток?
I: и как же однозначно можно восстановить все остальные? Вы имеете ввиду если отсортировать по неубыванию заданные суммы?
Да, надо отсортировать заданные суммы. Понятно, что первая сумма — это сумма двух наименьших, вторая сумма — это сумма первого и третьего. А дальше можно завести multiset — какие суммы мы еще обязаны найти в массиве всех сумм. Будем перебирать все данные суммы в порядке неубывания: если данная сумма лежит в multiset'е — то ее просто надо оттуда выкинуть, а иначе — мы встретили сумму "минимальная частица + новая, еще не встречавшаяся до этого, частица". Ну и при этом надо добавить в multiset новые значения. На все это нужно еще навесить сколько-то отсечений, чтобы не приходилось каждый раз перебирать все n2 сумм.
еще вопрос — а разве нельзя как-то ограничить перебор минимальной частицы, например, бинпоиском (всмысле найти минимальное возможоне значение и максимальное)? Если нет, то как доказать что функция "плохая"? =)
Думаю нет. Если добавить проверку, что сумма любых двух уже посчитанных частиц действительно встречается в данном массиве, то все будет быстро отсекаться.