→ Первое занятие (06.09.2010)

1. Дан квадрат NxN из 0 и 1, за O(N^3) нужно найти максимальный по площади подпрямоугольник состоящий только из нулей.
   Эту задачу можно сдать в контест 100906_30.
2. Дана реккурентная последовательность, какждый следующий элемент за O(1) выражается через 2 предыдущих. (x[n] = F(x[n-1],x[n-2]). Нужно за O(P+T) найти P и T. Где P – длина предпериода, а T – длина периода.
   Эту задачу можно сдать на acm.timus.ru (1175).
3. Дан неориентированный граф. Поступают операции вида AddEdge, DelEdge, IsConnected. Нужно все операции уметь выполнять за O(V), где V – число вершин в графе.

1. За O(N^2).
2. Используя O(1) памяти.
3. AddEdge и DelEdge нужно делать за O(1).

→ Второе занятие (13.09.2010)

1. Дано N <= 10^9, нужно найти все пары a, b: a^2 + b^2 == N.
   а) За O(N)
   б) За O(sqrt(N))
   в) Без использование функции sqrt
   г) Использую только + и -
   д) N == a^2 - b^2 (можно в стиле (в), не нужно (г))
   
2. Дано N <= 10^7. Найти и вывести все простые от 1 до N.
   а) Написать
   б) Понять, почему можно писать i*i <= n и j = i*i, а так же, почему NloglogN.
   
3. Даны N, K. У вас есть поле NxN и K ферзей на нем. Координаты ферзей даны. Выведите матрицу NxN - какие клетки биты, а какие нет.
   а) За N^2*K
   б) За N^2 + NK
   в) За N^2 + K
   

→ Третье занятие (16.09.2010, четверг)

1. putc (link) / getc (link) Example, 01-gets-puts.cpp: (link)
2. puts (link) / gets (link) Example, 02-putc-getc.cpp: (link)
3. printf (link) / scanf (link) Example, 03-scanf-printf.cpp: (link)
4. cin / cout
5. sscanf (link)

-3. Считать 2 числа, сложить их. Числа целые, до 100.
-2. Считать N и N чисел. Вывести их в обратном порядке. На одной строке через пробел. На конце строки не должно быть пробела. А вот перевод строки должен быть.
-1. Проверить, является ли файл пустым (0 байт)
0. Посчитать длину файла в символах (в байтах пока что не получится).
1. Посчитать число строк в файле.
2. Для каждого символа от 0 до 255, посчитать, сколько раз он встречается в файле.
3. Найти минимальное число в файле. Числа вещественные. Чотя бы одно число в файле точно есть.
4. В каждой строке или 1, или 2 числа. Для каждой строки вывести "сколько чисел в строке".
5. Посчитать сумму чисел во всем файле (все числа целые, пробелы повсюду)
   а) Сумма до 10⁹ по модулю
   б) Числа до 10⁹ по модулю
   в) Числа до 10¹⁸ по модулю
   
6. Распарсить запросы удаления-добавления ребер.
   Проверить корректность (нет мультиребер, если мы пытаемся удалить ребро, оно уже есть)
   Число вершин = 5000.
   + 1 2
   + 3 4
   - 2 1
   - 4 3
   
7. В каждой строке посчитать сумму чисел
   а) Разделены пробелом, оканчиваются переводом строки.
   б) Пробелы повсюду.
8. Считать все строки. Во всех строках поменять порядок слов на обратный. Строка = слова, разделенные ровно одним пробелом. Ведущих и коцевых пробелов нет.

1. Научитьcя число N раскладывать на множители быстрее, чем O(sqrt(N))
2. В графе найти самый короткий путь четной длины между A и B.
3. Научиться считать число различных подстрок строки за O(N³)
4. Найти минимальное натуральное число, у которого ровно K делителей. K до 1000.
5. Найти перестановку длины N, у которой ровно K инверсий

1. А за O(N^1/4)
2. А если нужно найти простой путь?
3. А за O(N²)?
4. Она и так сложная :)

→ Четвертое занятие (20.09.2010, понедльник)

→ Пятое занятие (23.09.2010, четверг)

1. Получение цифр числа (Вывести цифры числа через пробел)
2. Квадрат 1:
   

       2 11 19
       3 13 23
       5 17 29

3. Квадрат 2:
   

       1  2  4  7
       3  5  8  11
       6  9  12 14
       10 13 15 16

4. Все буквы строки сделать маленькими
5. Отсортировать строки (без функций работы со строками!)

1. 1563 - про число различных строк (link)
2. 1515 - мин.достоинство монеты (link)
3. 1551 - про турнир сумо (link)
4. 1579 - про шубы и жадность (link)
5. 1574 - про скобки (число правильных циклических сдвигов) (link)

1. 1508 - Динамика про японский кроссворд (link)

1. Научитьcя расставлять на доске NxN N ферзей так, чтобы они не били друг друга. N до 10⁴
2. Boxes из ЛКШ, А0-2010 (или B-2009)
   Есть люди, у них есть сила и вес. Нужно построить максимально высокую башню. Такую, что сила каждого в башне >= сумме масс, тех кто стоит на нем.

→ Шестое занятие (27.09.2010, понедельник)

(1) Функции работы со строками и с памятью

memset(a, 0, sizeof(a))                                     
memcpy(a, b, sizeof(a))
strcpy(a, b)
strcmp(a, b) // return < 0, = 0, > 0
strchr(s, '*') - s
strstr(s, "cat") - s

(2) Упражнения:

а) Найти подстроку в тексте за O(mn)
б) Разделить строку на две звездочкой. Вывести две половинки. Каждую на отдельной строке. Пример: ab*cd → ab \n cd
в) Отсортировать строки, попытка 2.

1. Timus 1723 (Халява?)
2. Timus 1089 (Исправление текста по словарю)
3. Timus 1067 (Дерево Директорий)
4. Timus 1297 (Max подпалиндром за O(N^2))

1. Полиномиальный хэш
2. Оценка вероятности N²/2⁶⁴
3. Хэш на подотрезкe = разница хэшей на префиксах
4. Пересчет хэша на подотрезке длины L за O(1)

1. Поиск строки в тексте за O(N+M)
2. Наибольшая общая подстрока O(NlogN) Timus 1517
3. Наибольший подпалиндром за O(N) Timus 1297
4. Подматрица в матрице (+ бинпоиск) Timus 1486

→ Седьмое занятие (30.09.2010, четверг)

1. if (x > 0) a; else b; <=> x ? a : b;

2. (a += b) <=> (a = a + b)

3. if (x > 0) <=> if (x)

4. if (x > 0) a = 2, b = 3; else a = 3, b = 2; // "," => Можно не ставить скобки

→ 8-е занятие (04.10.2010, понедельник

→ 9-е занятие (07.10.2010, четверг)

→ 10-е занятие (11.10.2010, понедельник)

→ 11-е занятие (14.10.2010, четверг)

→ 12-е и 13-е занятия (18.10.2010, 21.10.2010)

→ 14-е занятие (25.10.2010, понедельник)

→ 15-е занятие (28.10.2010, четверг)

→ 16-е занятие (01.11.2010, понедельник)

→ 17-е занятие (08.11.2010, понедельник)

Открыто дорешивание городской олимпиады!
Логины (link)
Контест = 101103a1. Удачи! ;-)
Условия контеста (link)

Нужно порешать задачи по геометрии (про выпуклую оболочку)

У нас новая тема: Приближенные вычисления в геометрии. [ПЛАН]

→ 18-е занятие (11.11.2010, четвег)

→ 19-е занятие (15.11.2010, понедельник, параллельно со сборами)

→ 20-е занятие (18.11.2010, четверг, параллельно со сборами)

→ 21-е занятие (22.11.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)