Еще вопрос: кто-нибудь знает, как поставить ссылку на профиль пользователя в посте?
A. Задача Читериуса
В этой задаче теоретически могли быть следующие проблемы: считывание, сравнивание, "я не прочитал, что n<=1000" и "электричка опоздала на 10 минут к началу раунда". У меня была последняя :)
Считывать можно было либо построчно, либо по токенам. Всё языки это умеют.
Сравнивать два квадрата можно опять же как угодно. Я делал так: считал две строчки, соеденил в одну и поменял 3й и 4й местами. Получилась "ленточка". Две "ленточки" можно сравнить двумя циклами: первый перебирает сдвиг, второй проверяет, что всё совпало.
Далее оставалось лишь посчитать количество стопок. Это можно было делать так: перебираем все непомеченные квадратики, добавляем один к ответу и помечаем все квадратики, которые равны текущему.
Задача тоже не ахти какая сложнае, если знать, как строятся парсеры в общем виде.
Для начала требовалось прочитать все строчки и склеить их в одну.
После чего поступаем так: заводим указатель на текущий рассматриваемый символ. Изначально он равен нулю. Затем делаем вспомогательную процедуру "прочитать строку". Она пытается посимвольно прочитать что-нибудь, начиная с текущего символа, и, если удалось - возвращает True и перемещает указатель вправо, если нет - возвращает False, и указатель не трогает.
После этого можно написать рекурсивные процедуры ReadCell, ReadRow и ReadTable - каждая из них возвращает количество ячеек в текущей таблице.
ReadCell работает так: прочитать <td>, если дальше не удалось прочитать </td>, добавить к ответу ReadTable() и прочитать </td>. Вернуть 1.
ReadRow: считали <tr>, пока не удаётся прочитать </tr>, делаем ReadCell. Вернуть сумму по всем ReadCell.
ReadTable: считали <table>, пока не удаётся прочитать </table>, делаем ReadRow. Вернуть сумму по всем ReadRow.
В конце надо посортировать количества ячеек во всех таблицах и вывести.
Также можно было делать так: завести функцию getTag, которая возвращает какой из 6 тегов был, а далее разобрать три случая:
"table" => stack.push_back(0)
"td" => stack.top++
"/table" => ans.push_back( stack.top() ), stack.pop_back()
C. Три базовых станцииДля начала упростим себе задачу: посортируем дома и удалим одинаковые.
Теперь давайте в цикле переберём самый правый дом, который покрывает первая станция.
Этот дом однозначно определяет её минимальную мощность. Далее хочется быстро найти границу для второй станции. Что мы хотим минимизировать? Максимум из мощности второй и третьей станций (т.к. первая у нас уже фиксированна). При движении границы слева направо мощность второй растёт, а третьей - убывает. Соответственно, максимум из этих двух величин до какого-то времени невозрастает, а затем - неубывает. Хотим найти момент этого перехода - в нем и будет искомый минимум. Это можно сделать при помощи указателя, т.к. этот момент всегда движется только направо.
Т.о. получаем решение за линейное время.
Считывать можно было либо построчно, либо по токенам. Всё языки это умеют.
Сравнивать два квадрата можно опять же как угодно. Я делал так: считал две строчки, соеденил в одну и поменял 3й и 4й местами. Получилась "ленточка". Две "ленточки" можно сравнить двумя циклами: первый перебирает сдвиг, второй проверяет, что всё совпало.
Далее оставалось лишь посчитать количество стопок. Это можно было делать так: перебираем все непомеченные квадратики, добавляем один к ответу и помечаем все квадратики, которые равны текущему.
B. Анализ таблиц bHTML
Для начала требовалось прочитать все строчки и склеить их в одну.
После чего поступаем так: заводим указатель на текущий рассматриваемый символ. Изначально он равен нулю. Затем делаем вспомогательную процедуру "прочитать строку". Она пытается посимвольно прочитать что-нибудь, начиная с текущего символа, и, если удалось - возвращает True и перемещает указатель вправо, если нет - возвращает False, и указатель не трогает.
После этого можно написать рекурсивные процедуры ReadCell, ReadRow и ReadTable - каждая из них возвращает количество ячеек в текущей таблице.
ReadCell работает так: прочитать <td>, если дальше не удалось прочитать </td>, добавить к ответу ReadTable() и прочитать </td>. Вернуть 1.
ReadRow: считали <tr>, пока не удаётся прочитать </tr>, делаем ReadCell. Вернуть сумму по всем ReadCell.
ReadTable: считали <table>, пока не удаётся прочитать </table>, делаем ReadRow. Вернуть сумму по всем ReadRow.
В конце надо посортировать количества ячеек во всех таблицах и вывести.
Также можно было делать так: завести функцию getTag, которая возвращает какой из 6 тегов был, а далее разобрать три случая:
"table" => stack.push_back(0)
"td" => stack.top++
"/table" => ans.push_back( stack.top() ), stack.pop_back()
C. Три базовых станции
Теперь давайте в цикле переберём самый правый дом, который покрывает первая станция.
Этот дом однозначно определяет её минимальную мощность. Далее хочется быстро найти границу для второй станции. Что мы хотим минимизировать? Максимум из мощности второй и третьей станций (т.к. первая у нас уже фиксированна). При движении границы слева направо мощность второй растёт, а третьей - убывает. Соответственно, максимум из этих двух величин до какого-то времени невозрастает, а затем - неубывает. Хотим найти момент этого перехода - в нем и будет искомый минимум. Это можно сделать при помощи указателя, т.к. этот момент всегда движется только направо.
Т.о. получаем решение за линейное время.
D. Геометрическая задача
Первое, что требовалось вспомнить - бываю еще и нули.
Давайте для начала научимся понимать, является ли последовательность геометрической прогрессией. У каждой прогресси либо есть знаменатель b (возможно, 0), либо он может быть любым (c=0). Для каждых двух соседних элементов опять же, либо есть однозначные знаменатель, либо нет. Собирав эту информацию со всех элементов и проверив на непротиворечивость, мы убедимся что последовательнось - прогрессия.
Побежим по последовательности слева направо. Заведём две переменные - знаменатель последовательности (b) и флаг, определили ли мы его уже (exb). Вначале exb=false.
Далее мы обрабатываем элемент (a1) и предыдущий (a0). Мы должны проверить, что они не конфликтуют с уже известной информацией и что они вообще могут встретиться рядом хоть в какой-то последовательности. Если это так, то нам надо пересчитать знаменатель (если a0 != 0), иначе сразу возвращаем false.
Для проверки на конфликты у меня была функция equal. Она работает следующим образом: если a0 = 0, то надо проверить, что a1 = 0 и вернуть true, иначе выбросить исключение. Иначе, если знаменатель еще не определён, то вернуть true. В противном случае проверить, что отношение элементов и знаменатель совпадают.
Если в конце оказалось, что конфликтов и исключений не было, то да, такая геометрическая прогрессия есть.
Теперь у нас есть функция проверки, является ли последовательность прогрессией. Мы уже можем написать квадратичное решение. Для получения OK нам требуется чуть-чуть изменить квадрат и сделать precalc.
Как работает тупой квадрат? Выкидываем по очереди элементы и проверяем, что прогрессия есть. Теперь давайте заметим, что массив без одного элемента - это какой-то его префикс плюс суффикс.
Что значит, это это объединение есть прогрессия? Что, во-первых, каждый из них является прогрессией, и, во-вторых, что их можно "склеить". Т.е. что пара (an, b1) не конфликтует ни с первой прогрессией, ни со второй.
Теперь у нас есть цикл, внутри которого идёт куча вызовов вида check(0, 0), check(0, 1), check(0, 2) и т.д. Их можно объединить в один и с запоминанием результатов на каждом шаге. Это даёт линейное решение со всеми разобранными случаями.
Давайте для начала научимся понимать, является ли последовательность геометрической прогрессией. У каждой прогресси либо есть знаменатель b (возможно, 0), либо он может быть любым (c=0). Для каждых двух соседних элементов опять же, либо есть однозначные знаменатель, либо нет. Собирав эту информацию со всех элементов и проверив на непротиворечивость, мы убедимся что последовательнось - прогрессия.
Побежим по последовательности слева направо. Заведём две переменные - знаменатель последовательности (b) и флаг, определили ли мы его уже (exb). Вначале exb=false.
Далее мы обрабатываем элемент (a1) и предыдущий (a0). Мы должны проверить, что они не конфликтуют с уже известной информацией и что они вообще могут встретиться рядом хоть в какой-то последовательности. Если это так, то нам надо пересчитать знаменатель (если a0 != 0), иначе сразу возвращаем false.
Для проверки на конфликты у меня была функция equal. Она работает следующим образом: если a0 = 0, то надо проверить, что a1 = 0 и вернуть true, иначе выбросить исключение. Иначе, если знаменатель еще не определён, то вернуть true. В противном случае проверить, что отношение элементов и знаменатель совпадают.
Если в конце оказалось, что конфликтов и исключений не было, то да, такая геометрическая прогрессия есть.
Теперь у нас есть функция проверки, является ли последовательность прогрессией. Мы уже можем написать квадратичное решение. Для получения OK нам требуется чуть-чуть изменить квадрат и сделать precalc.
Как работает тупой квадрат? Выкидываем по очереди элементы и проверяем, что прогрессия есть. Теперь давайте заметим, что массив без одного элемента - это какой-то его префикс плюс суффикс.
Что значит, это это объединение есть прогрессия? Что, во-первых, каждый из них является прогрессией, и, во-вторых, что их можно "склеить". Т.е. что пара (an, b1) не конфликтует ни с первой прогрессией, ни со второй.
Теперь у нас есть цикл, внутри которого идёт куча вызовов вида check(0, 0), check(0, 1), check(0, 2) и т.д. Их можно объединить в один и с запоминанием результатов на каждом шаге. Это даёт линейное решение со всеми разобранными случаями.
E. Пентагон (спасибо, @Sereja)
Пускай массив Q означает наличие ребра между двумя вершинами, а st - степень вершины.
Для начала для каждой пары посчитаем количество вершин которые "лежат между ними", иными словами, достижимы от обоих из них. Запишем эти данные в массив A (это можно сделать за кубическое время).
После того, как мы знаем эти данные, переберем 3 вершины из цикла, две из которых будут лежать "рядом" в цикле. Назовём их i, j и l (Q[i,j]=1). Тогда возьмем две переменные, которые будут отвечать за количество вершин "между" i и l , j и l. Это будут значения A[i, l] и A[j,l], но при этом, в случае Q[j, l] = 1 от первого нужно отнять 1, для второго - аналогично. Это делается для того, чтобы никакая вершина не входила в цикл два раза. К ответу добавим произведение этих значений. Есть еще один отдельный случай: когда Q[i, l]=1 и Q[j, l]=1, то от ответа нужно отнять st[l]-2? Чтобы понять это, нужно на листке бумажки расписать, как будут происходить добавления новых циклов, и через какие вершины мы их пропустим.
Полученный ответ делим на 5 для удаления повторов (каждый цикл мы считаем из каждой его вершины), это и будет финальный ответ.
В комментариях есть обобщённое решение на случай более длинных циклов.
Для начала для каждой пары посчитаем количество вершин которые "лежат между ними", иными словами, достижимы от обоих из них. Запишем эти данные в массив A (это можно сделать за кубическое время).
После того, как мы знаем эти данные, переберем 3 вершины из цикла, две из которых будут лежать "рядом" в цикле. Назовём их i, j и l (Q[i,j]=1). Тогда возьмем две переменные, которые будут отвечать за количество вершин "между" i и l , j и l. Это будут значения A[i, l] и A[j,l], но при этом, в случае Q[j, l] = 1 от первого нужно отнять 1, для второго - аналогично. Это делается для того, чтобы никакая вершина не входила в цикл два раза. К ответу добавим произведение этих значений. Есть еще один отдельный случай: когда Q[i, l]=1 и Q[j, l]=1, то от ответа нужно отнять st[l]-2? Чтобы понять это, нужно на листке бумажки расписать, как будут происходить добавления новых циклов, и через какие вершины мы их пропустим.
Полученный ответ делим на 5 для удаления повторов (каждый цикл мы считаем из каждой его вершины), это и будет финальный ответ.
В комментариях есть обобщённое решение на случай более длинных циклов.
F. Гусеница
А задачу B про парсер нельзя было решить с помощью функции getTag, которая возвращает какой из 6 тегов был, а дальше делать примерно так:
"table"? - stack.push_back()
"td"? - stack.top++
"/table"? - ans.push_back( stack.top() ), stack.pop_back()
Дальше сортируем ans и выводим.
Пускай массивы Q означает наличие ребра между двумя вершинами , а st степень вершин.
Для начала для каждой пары посчитаем количество вершин которые "лежат между ними", иными словами достижимы от обоих из них. Запишем эти данные в массив, допустим A.
После того как мы знаем эти данные переберем 3 вершины из цикла, две из которых будут лежать "рядом" в цикле. Допустим это будут вершины i,j,l(Q[i,j]=1). Тогда возьмем две переменные которые будут отвечать за кол-во вершин "между" i и l , j и l. Это будут значения A[i,l] и A[j,l] , но при этом , в случае Q[j,l] = 1 от первого нужно отнять 1, аналогично для второго(Это делается для того что-бы 1 вершина не входила в цикл два раза). К ответу добавим произведение этих значений. Но есть отдельный случай: когда Q[i,l]=1 и Q[j,l]=1 , то от ответа нужно отнять st[l]-2 ? что-бы понять это нужно на листке бумажки расписать как будут происходить добавляения новых циклов и через какие вершины мы их пропустим. Полученный ответ делим на 5, это и будет финальный ответ.(удаляем повторные циклы)
Сначала посчитаем степени матрицы смежности. Используя их, посчитаем ответ методом включений-исключений. А именно, переберём все "топологии" цикла - какие вершины совпадают. Для каждой такой "топологии" посчитаем количество циклов, удовлетворяющих топологии, т.е. у которых вершины, помеченные одинаковыми, одинаковы, а остальные могут быть как одинаковыми, так и разными (с помощью посчитанных степеней матрицы). Дальше просто формула включений-исключений. В этой задаче возможных топологий было всего 3 штуки, поэтому их можно было разобрать вручную, и не возникало проблем с коэффициентами в включениях-исключениях.
Задачу D можно вот так же:
1) Если количество элементов менше 1000, можно решать за O(n2)
2) Иначе, заметим, что коеффициент прогрессией должен быть -1, 0 или 1, иначе либо не все числа будут целые, либо какое-то из них будет больше 104. Не могу строго доказать, но кажется всем понятно почему...
Там в каком-то из последних тестов коэффициент 1/3.