Привет, CF!
Я думаю многие из вас, в частности участники IOI, затрудняются найти хорошие, понятные разборы задач IOI, поэтому я решил создать блог где мы будем публиковать задачу, решать её и переходить к следующей (как на AOPS).
Позвольте мне начать — IOI 2006 Б. Пирамида.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | pajenegod | 145 |
| 9 | SecondThread | 145 |
This page may be useful.
I know that I can I find solutions on this site but I think people have a lot of creative solutions for these problems.
Hello sir,thanks for the link :) But how to find questions of previous IOI's and their solution in this site
List of previous IOIs, click on a year to see the problems
Literally follow his link and click on the olympiad you want to check out, then follow the links (usually "The Competition")
Задачу Пирамида можно написать на 59 баллов. Перебираем все пирамиды и внутри них будем перебирать все возможные комнаты , а сумму в пирамиде и в комнате будем считать ДПшкой. Вот код.
Да, именно так я и делал. У меня тоже 59. А как на 100?
Наверное двумерное дерево отрезков.
Ну да, в чистом виде.
Нам надо считать сумму на подпрямоугольнике(это можно сделать префиксными суммами) и минимальный подпрямоугольник размера c*d(а вот для этого уже используется дерево отрезков.
Теперь просто перебираем левый верхний угол пирамиды, выбираем лучшее положение для комнаты запросом к прямоугольнику размера (a-2)*(b-2) (то есть пирамиде без границ) к дереву отрезков и обновляем ответ.
Итого O (n*m*log(n)*log(m))
Минимумы на всех подпрямоугольниках одинаковых размеров можно и за O(n * m) с помощью очереди для минимума. Это делается аналогично одномерной задаче.
Пусть надо предпосчитать для всех прямоугольников размера e * f. Cначала предпосчитаем минимумы на прямоугольниках 1 * f c помощью одномерной задачи. Потом аналогично предпосчитаем на прямоугольниках e * 1, но уже для результата предыдущего предподсчёта.
вот решение исходной задачи на 100.
Огромное спасибо! Весь сижу над этой задачей и наконец-то понял!
Коммент старенький, но всё же. Эту задачу я всё таки сдал, но с помощью очереди. Написал 2D не рекурсивное деревое отрезков — TL.
O(n ^ 2 * log(n))
рандомные тесты проходит.
Попробуй сдать, что ли. Например, сюда.
а что там за 1 число в выходных данных? и еще там надо читать из файла? у меня везде вердикт ошибка исполнения.
В семпле видимо бага в ответе, там надо 4 числа выводить. Файл или стандартный поток вроде неважно, если файлы, то input.txt/output.txt.
кажется ошибка исполнения — это на самом деле МЛ.
да это был МЛ. но не работает решение. плохо тестировал значит. 12 тестов пройдено.
решение было изначально верное, но не укладывалось в МЛ(там всего 32 мб он). я поменял массив интов на массив чаров и стал ловить ВА(переполнение). Потом поменял на массив шортов и прошло.
n ^ 2 * log(n) Accepted
Очередь (два стека). За O(N * M). Код
Вот он, редиска!
Следующая задача — IOI 2008 Б. Острова.
Next task — IOI 2008 B. Islands.
Where can we test IOI problems , I mean is there any online link ?
Most of them are available on wcipeg
Also you can ask yeputons for an account on http://acm.math.spbu.ru/ . You can find there all IOI problems from 2003 up to 2014.