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 20:09, from IP address 95.104.x.x. The current document download page has been viewed 456 times.
File size: 269 KB (1 page).
Privacy: public file


Download original PDF file


GNYRC 2009 Questions.pdf (PDF, 269 KB)


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. Какие граничные случаи следует рассмотреть при решении этой задачи?


Document preview GNYRC 2009 Questions.pdf - page 1/1


Related documents


gnyrc 2009 questions
math words
regular totally separable sphere packings arxiv
sparse inverse covariance
insceditorials
research statement

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

QR Code

QR Code link to PDF file GNYRC 2009 Questions.pdf