Всем здрасьте =)
Как многие знают, недавно прошел заключительный этап Всесибирской олимпиады школьников по программированию(http://vsesib.nsesc.ru/about.html).
Хотелось бы узнать свежие идеи решения по задачам 2 и 3, кто и как собирается/собирался их решать ^_^ (http://vsesib.nsesc.ru/archive/2012/2012_3_inf_t.pdf). У меня были мысли на счет задачи 2, но решение было за квадрат и конечно же TL :( Ну а на 3 я как — то не представляю внятного решения ...
На разбор я, увы, не успел...
Надеюсь на большое количество откликов :)
Заранее спасибо!
Во второй можно точки в map складывать. Тогда O(NlogN) и должно пройти.
Хмм, а если решать на Паскале(Ну в моем случае на делфях)? К сожалению тут нету такого нужного компонента, как MAP >_<
Написать АВЛ-дерево или декартово
Руками проще и быстрее писать хешмап
а каким образом пересечения искать, используя map?
про вторую задачу на разборе сказали, что она решается либо через еденичный прямоугольник (правда так вроде и не ответили на вопрос как содержать массив в памяти), либо через дерево Фенвика. асимптотика в таком случае будет O(Nlog^2N)
На разборе было предложено дерево Фенвика, но из-за ограничений его не возможно поддерживать. Потом, было предложено извращение с деревом отрезков, которое я, честно говоря, не понял.