План и Задачки кружка с 01.12.2010

1. Полный перебор
2. Отсечение по ответу: if (dep >= answer) return
3. Отсечение по ответу с оценкой на остаток if (dep + F >= answer) return
4. Отсечение "Динамика". if (мы уже были в этом состоянии) return
5. Внешний перебор ответа.
1. ищем путь минимальной длины = MinLen. Можно перебрать все пути, а можно только длины MinLen
2. Для этого перебираем во внешнем цикле MinLen (т.е. ответ на задачу)
6. Отсечение по времени =)

1. Рекурсия на примере задачи про различные пути. [statement, problem A]
2. Задача timus : 1152 (Зеркала). Отсечение по ответу.
3. Задача про самый длинный простой путь [statement, problem B]
4. Задача про StringDecomposition [statement, problem C]

Куда сдавать задачи?

1. 1152 - на acm.timus.ru
2. Все остальные в контест 101125_30 [statements]
3. Пожалуйста, решайте задачи по порядку!

Язык Си

1. clock(), CLOCKS_PER_SEC
2. time(NULL)

1. Функции работы со временем: clock, time, asctime, localtime, rdtsc, GetTickCount [link]
2. Функции работы с файловой системой: chdir, mkdir, ...
3. Работа с консолью: GetStdHandle, SetConsoleTextAttribute, SetConsoleCursorPosition, SetConsoleCursorInfo [link]
4. Перебор всех файлов в папке: _findfirst, _findnext, _findclose [link]
5. Работа с потоками: CreateThread, передача параметров, "общение" с потоками

Задачки

1. Создать дерево директорий "dir" → "dir\0", "dir\1", "dir\2". Глубина = 5.
2. Пустить летать звездочку по экрану. Траектория = [sin(3t), cos(5t)]
3. Вывести дерево директорий, начиная с текущей папки

1. Найти максимум в массиве. Без циклов. Глубина рекурсии O(logN).
2. Придумать 3 способа посимвольного вывода целых чисел. Вывести целое число посимвольно, рекурсивно.
3. Найти замощение доминошками поля с дырками (тупо перебором). Раскрасить доминошки от 1 до 9.
4. Теория: Дерево Отрезков, операции сверху
5. Наибольшая возрастающая подпоследовательность деревом отрезков за O(NlogN).

1. Задача1: [link] Интересная задача. Решается за O(NlogN) деревом отрезков. Если вы Гуру, нужно решить за O(N).
2. Задача2: 1238.Folding = Динамика (можно за O(n^3), accepted получает O(n^4))
3. Задача3: 1152.Mirrors = Перебор (можно решить динамикой по подмножествам, но интереснее перебором)

1. Отсортировать set-ом за O(NlogN) (сперва все insert-им, затем, пока не пусто вынимаем минимум). Протестить, что работает для N=2*10⁶
2. Дейкстра с кучей [link] (set - это куча). Про Дейкстру почитать можно здесь [link1] и здесь [link2]
3. timus.1037 [link] (set - это куча)

1. Задача E "инкрементатор" [link] (map - это сила)
2. Делители с регионалки (напишите перебор, который получат AC для 10⁸, а затем соптимизьте его map-ом) [2010-2011 day2, задача 7]

1. Details с регионалки (хранение графа как vector<int> []) [2009-2010 day2, задача 7]
2. Если вы не уверены в своих знаниях графов, можно сперва сдать 2 простые задачи на тимусе: [1080] (раскраска графа в 2 цвета) и [1022] (топологическая сортировка)

1. Найдите число различных подстрок строки длины <= 100 с помощью set и string. Какая у решения асимптотика времени работы?
2. Найдите min циклический сдвиг строки за O(N^2)
3. Более сложная задача: Disk-Tree [timus:1067]
4. На подумать (только тем, кто сдал все остальное): [timus:1684]

1. Простая [timus:1218]
2. bfs [read about]
3. bfs-01
4. Ford-Bellman [read about]
5. bfs-Ford-Bellman
6. bfs-hard [timus:1325]
7. Ford-Bellman - отрицательный цикл [timus:1162]

а) FB за O(VE)
б) FB с очередью за ~O(E)
в) Поиск отрицательного цикла за O(VE)
г) Поиск отрицательного цикла мин среднего веса за O(VElogMax)
*д) Поиск отрицательного цикла мин среднего веса за O(VE)
*е) MinCost flow (flow = k) (via FB)
*ж) MinCost circulation (flow = 0) (via negative cycle)
*пж) MinCost circulation за O((VE)^2)

1. Сделать файл, в котором записаны числа от 5 до 25.
2. Скомпилировать все cpp файлы.
3. Написать cmd-файл, который замеряет время.
4. Сгенерировать тесты 1..9 с 2-мя рандомными числами внутри
5. Отдебажить на них баг в программе y.cpp (x.cpp и y.cpp всем даны).
6. Стресс-тест (генератор прямо внутри cmd файла)

1. Посчитать факториал числа рекурсивной функцией
2. Посчитать факториал числа без рекурсии, for-ом

1. min тесты (главное, правильно прочитать условие и все разобрать)
2. max тесты (главное, не полениться написать генератор = один цикл for)
3. Крайние случаи - по желанию, зависит от вашей фантазии
4. Stress тест на маленьких тестах
5. Stress тест на больших тестах
6. Перебор всех входных данных от и до

1. O(sqrtN)
2. O(sqrtN / logN) для мультитеста
3. Тест Ферма за O(k*sqrtN) (проверить на первых k простых числах малую теорему Ферма)
4. Тест Миллера-Рабина (почитать можно тут [link])
5. Смешной тест = Ферма + проверить маленькие делители.
6. Как найти большое простое число? (100-значное)

1. Найти все исходники на cpp в данной папке, содержащие в своем имени букву "f"
2. Найти все исходники на cpp в данной папке, содержащие слово "struct". Вывести первые N.
3. В текущем cpp исходнике вывести все строки (с номерами), содержащие команды препроцессора.
4. Вывести дерево директорий. С отступами.
5. Вывести список всех некомпилирующихся/компилирующихся cpp файлов