GNYRC 2009 Questions .pdf
File information
Original filename: GNYRC 2009 Questions.pdf
Author: user
This PDF 1.5 document has been generated by Microsoft® Word 2010, and has been sent on pdf-archive.com on 01/10/2013 at 22:09, from IP address 95.104.x.x.
The current document download page has been viewed 457 times.
File size: 269 KB (1 page).
Privacy: public file
Share on social networks
Link to this file download page
Document preview
Задача 4552 - Nth Largest Value
1. Решить эту задачу.
Задача 4556 - The Next Permutation
1. Следующая перестановка – такая перестановка, которая больше текущей, причём на как можно меньшее
значение. Какие элементы перестановки можно обменять, чтобы получить большую перестановку?
2. При обмене каких элементов перестановка увеличивается меньше всего?
3. Что нужно сделать после обмена элементов?
Задача 4555 - Running Median
1. Какую асимптотику имеет лобовое решение?
2. Как улучшить асимптотику до ( )? (Подсказка: рассмотреть одно из применений идеи быстрой
сортировки).
)? (Подсказка: использовать очереди с приоритетами).
3. Как улучшить асимптотику до (
4. Можно ли обойтись одной очередью с приоритетами?
Задача 4553 - Equal Sum Partitions
1. Сформулировать жадное решение и обдумать детали его реализации.
Задача 4557 - Adjacent Bit Counts
1. Будем считать динамику [ ][ ] – число строк из бит, содержащих пар смежных единиц. Заполните
таблицу для
. Можно ли выразить значение [ ][ ] из меньших значений?
2. Как можно изменить динамику, чтобы получить простое соотношение перехода? (Подсказка: добавить в
динамику новую размерность – значение последнего бита строки).
3. Как теперь получить ответ на задачу?
Задача 4554 - Balls
1. Будем считать динамику [ ][ ] – максимальное число этажей, для которых можно определить ответ, если
есть шаров и попыток. Заполните таблицу для
. Как выразить значение [ ][ ] через меньшие
значения?
2. Сколь быстро растёт функция ответа? Массив какой размерности требуется объявить для хранения
динамики? Какие отсечения можно применить?
Задача 4560 - Theta Puzzle
1. Решить задачу 128 ACMP;
2. Как восстанавливать ответ в исходной задаче?
3. Сколько раз нужно выполнить поиск в ширину в исходной задаче?
Задача 4558 - Convex Hull of Lattice Points
1. Посмотреть лекцию Algorithms Part I – Week 2 Elementary Sorts – 5 - 6 - Convex Hull, чтобы познакомиться с
алгоритмом определения выпуклой оболочки.
Задача 4559 - Interior Points of Lattice Polygons
1. Как определить левую и правую точку внутренней полосы для данной координаты ?
2. Как определить, проходит ли данный отрезок через точку с ординатой ? Как получить абсциссу этой
точки?
3. Какие граничные случаи следует рассмотреть при решении этой задачи?

Link to this page
Permanent link
Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by e-Mail, Messenger, Whatsapp, Line..
Short link
Use the short link to share your document on Twitter or by text message (SMS)
HTML Code
Copy the following HTML code to share your document on a Website or Blog