Наконец, открылась регистрация на SRM 523. Напоминаю, он начнется в 21.00 по московскому времени
Для вашего часового пояса смотрите сюда.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 27.04.2024 05:27:39 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Самый эпичный даблпост за всю историю CodeForces :) Double-blog-post.
Скрывай другую версию)
А там двумерная динамика h*w работает?
UPD: Да, она работает :)
Я решал динамикой по w, h: когда h=0, ответ 1, иначе ответ равен
где R(n,k) - количество разбиений n на слагаемые, не превышающие k.
Я кодил динамику по профилю. Там вроде профилей всего пара-тройка тысяч максимум.
Не сдал, правда, очень эпично: пока фиксил последний баг в инициализации, вылезло сообщение об окончании.
UPD: Ох, я почему-то ошибочно подумал, что в див1 500-я будет 1000-й из div2.
Для w=10 различных масок 9003 штуки.
Я на контесте забыл, что синюю можно ставить только на ее края, а в центре пусто, и так и не сдал эту задачу.
Да, в первом моем раунде (SRM 522) я случайно попал в div-2.
Посчитаем динамику
А что происходит в див2? Почему на третьем месте какой-то парень, который сдал только первую задачу с 151,19. При этом сумма балов у него 1222,75 ? Как такое может быть если челенджы только целую часть меняют?
Пруф:
У него в хистори сабмит почти на 1000 по харду
Я один не могу найти его в списке?
тьфу, не актуально
Мимо :(
У него сначала идёт проверка, что m до 1012, потом он его ещё домножает на d. А потом он на эту величину домножает c - вот тут и должно переполниться.
Но вот сейчас я посмотрел внимательно и вижу, что там в любом случае это не повлияет на алгоритм. А на челлендж-фазе подбирал такое d, что 1012*d*d будет иметь выставленный 64-й бит. Хорошо, что не подобрал :)
typedef long long Long;
Таки троль.
В div1 250 надо было еще ограничения дать все до 10^18.
Чтоб веселее было. А что ж я, зря заменял умножение делением (чтоб geom[i]*d , вместе в выходом за аппербаунд, и за лонг лонг не вышло)?
Просто такое впечатление возникло, что автор специально подбирал удобные для челленджа задачи (сейчас уже прочел в блоге, что за примеры в 250 он извиняется).
В 500 забыл поставить модуль в одном месте, в итоге ресабмит и всего 210 очков.
Но задачи были хорошие. Как кстати 900 Div 1 решать?
"Их 120000 для каждой середины."
Расскажите пожалуйста, как получить такую оценку?
Очень просто. Оченим количество путей так. У нас не более 4 вторых клеток и не более 3 следующих. Получаем
аргх... опередили)
забавно, что чувак, который всех челленжил направо и налево, получил море баллов, в итоге плохо выступил
Имхо - то, что они для взломов - следствие того, что они простые: все (и я тоже :) ) кинулись их писать, не подумав про частные случаи.
Зато первый раз смог написать вторую задачу :)
Не могу решить вторую. А именно: написал решение, проходящее все тесты, которые я могу проверить руками на листочке, и не проходящее большие. По коду багу найти не могу.
Вдруг найдется кто-то, кому ошибка будет очевидна.
Как решаю.
f(w,h) - сколькими способами можно получить фигню высотой ровно h, если ширина основания w. Разделяю это на подзадачи, перебирая позицию самой левой пустой клетки на нижнем уровне.
Код: http://pastebin.com/NdLCKDqL
Советую посмотреть мой короткий код;)
Как только написал это, подумал, а почему бы не сделать f(w,h) - сколькими способами можно получить фигню высотой <= h. Написал это, оказалось короче, меньше асимптотика и работает правильно.
upd: не, нифига не правильно, всего лишь последний семпл-тест почему-то прошло.
ll testLeft = prec[lp]*f(lp,h-1);
Почему одна часть домножается на дополнительную константу а другая нет?)
И вообще, мне кажется, неверно сначала собирать сумму и потом домножать на количество способов, ведь сами слагаемые можно составить разными количествами способов.
Почему левое домножается, а правое нет:
lp - позиция самой левой пустой клетки первого уровня. Значит слева от нее все клетки заполнены. Способов заполнить их prec[lp] штук. А на эти заполненные можно еще понаставить чего-нибудь высоты не более h-1.
Справа же от этой позиции другие пустые клетки могут быть, поэтому там просто f от той же высоты.
> И вообще, мне кажется, неверно сначала собирать сумму и потом домножать на количество способов, ведь сами слагаемые можно составить разными количествами способов.
Не очень понял.
Клетки слева от lp заполняются независимо от того что находится на них, почему бы не поперемножать.
Похоже, что как раз в этом месте и ошибка.
Когда ты собираешь сумму, с длиной lp, полоска может разбиться на несколько несвязных частей, каждую из которых нужно умножать на свой f(x,h-1), сразу все нельзя.
Несвязные части - части, разделенные пустыми клетками?
Если да, она не может разбиться, так как там нет пустых клеток.
Ещё одна попытка:
dp[w][h] = (dp[w][h]+f(w-1,h))%mod;
Как я понял это случай с пустым левым концом, правый у тебя рассматривается в цикле.
Для случая w=3, h=1 расстановка с одним кубиком посередине учтётся 2 раза. То есть порядок "обрезания" пустых клеток имеет значение в решении.
================================
Расстановка пусто-заполнено-пусто?
Самая левая клетка пуста, значит рассмотрится только в строчке
dp[w][h] = (dp[w][h]+f(w-1,h))%mod;
В цикле она уже не рассмотрится, в цикле самая левая пустая клетка перебирается начиная со второй.
Double.
Triple.
Надеюсь сейчас будет правильно, потому что все мои идеи неверные, и больше сомнений вроде нет.
Да, это именно оно, спасибо.
Adamka, спасибо и тебе за попытку помочь и потраченное время)