Здесь приводится разбор всех задач прошедшего раунда. Вопросы и предложения задавайте в комментариях. Отдельное спасибо пользователю sdya за подготовку разборов задач D и E, которые я использовал в качестве авторского разбора.

Задача А

В данной задаче нужно уметь проверять всего четыре условия:
1) помещается ли N в тип byte

2) помещается ли N в тип short

3) помещается ли N в тип int

4) помещается ли N в тип long

Именно в таком порядке и нужно проверить эти условия. Если все они неверны – то ответ BigInteger.

Как проще всего проверить условия 1) – 4)? Проще всего хранить числа в виде строк и написать функцию сравнения двух строк как чисел. В Java можно было пользоваться встроенным типом BigInteger.

Задача B

Тут нужно перебрать все возможные позиции для создания искусственного дождя, посмотреть сколько в каждом из случаев получается участков, содержащих воду и выбрать среди всех возможных вариантов максимальный. При этом подсчитывать ответ для текущей позиции будем, просто расходясь вправо и влево от текущей позиции. Итоговая сложность O(N^2).

Задача C

Понятно, что максимальное число файлов и максимальное число подпапок будет в каких-то из папок, находящихся непосредственно в корне каких-то дисков. Рассмотрим, чем характеризуется файл и чем характеризуется подпапка. Файл характеризуется путем, который записан в условии, а папка характеризуется частью пути до нее. То есть, к примеру, если есть путь: C:\folder1\folder2\1.txt, то отсюда нам надо выделить две папки и один файл, чтобы получить выражение для каждой из папок в данном пути и для файла. Имеем, что первой папке соответствует путь C:\folder1\, второй папке C:\folder1\folder2\, и файлу соответствует C:\folder1\folder2\1.txt. После того, как мы разделим так каждую строку из входных данных, у нас получится набор путей к папкам и отдельно набор путей к файлам. Решим задачу сначала для подпапок. Для этого соберем все пути к папкам, которые мы получили в результате предыдущей операции. Понятно, что некоторые пути могут встречаться там несколько раз. Отсортируем этот массив. Прежде чем удалить из него повторения, заметим, что ими можно воспользоваться для подсчета ответа по файлам. Для этого просто подсчитаем какая из строк встречается больше всего раз – это и будет ответом по файлам (подумайте почему). После, нужно удалить повторения – это можно сделать, отсортировав все строки-пути и пройдя один раз по полученному массиву. Теперь у нас остался отсортированный массив путей, без повторений. Пусть наш массив будет s. Будем идти по массиву и искать строку, в которой ровно два обратных слеша – это будет означать, что мы нашли папку, которая находится в корне какого-то диска. Пусть индекс этой строки в массиве k. Тогда рассмотрим все строки, начиная с k+1 по k+l, такие, что они содержат строку s[k] как подстроку, начиная с стартовой позиции. А s[k+l+1] уже не содержит. То есть, имеется в виду, что если s[k]=X:\folder1\, то все подпапки этой папки будут иметь вид X:\folder1\... И естественно они и только они содержат s[k] как подстроку, при этом начиная с начала (выделено жирным).

Тогда, мы получим, что у папки X:<span lang="EN-US">folder1\ будет ровно l подпапок. Аналогично, пройдя так до конца массива, мы найдем ответ по максимальному количеству вложенных подпапок. Также можно было решать эту задачу используя set, или map вместо сортировки.

Задача D

Выберем N различных простых чисел: p1, p2, …, pn. Пусть A=p1*p2*...*pn. Тогда, нетрудно видеть, что в качестве ответа подходят следующие числа: A/p1, A/p2, …, A/pn. Единственный особый случай, это N=2. Здесь ответа не существует.

Следует заметить, что для такого решения этой задачи нужна длинная арифметика, при этом из операций нужно лишь умножение (A/pi=p1*…*p(i-1)*p(i+1)*…*pn). Если выбрать в качестве p1, …, pn первые n простых чисел, то самое большое из чисел в ответе на n=100, будет содержать меньше 300 знаков.

Однако существует еще решение. Рассмотрим ответ для N=3 – 15, 10, 6. Тогда, для произвольного N>3 подходят следующие числа: 15, 10, 6, 15*2, 15*3, …, 15*(N-2).

Задача E

Разобьем задачу на две: определим те станции, с которых можно начинать, если мы едем по часовой стрелке и те станции, с которых можно начинать, если мы едем против часовой стрелки. Очевидно, если мы решим одну из этих задач, то сможем решить и вторую, аналогичным образом. Будем считать, что станции расположены в порядке обхода против часовой стрелки, при этом машина тоже будет двигаться против часовой стрелки. Рассмотрим следующие разности:

D1=a1-b1,

D2=(a1+a2)-(b1+b2),

D3=(a1+a2+a3)-(b1+b2+b3),

…

Dn=(a1+a2+…+an)-(b1+b2+…+bn);

Очевидно, что если какое-то из чисел Di меньше нуля, то от первой станции машина не сможет проехать круг против часовой стрелки. Также рассмотрим число D=min(Di) – оно нам пригодится в дальнейшем решении. Очевидно, если D<0, то первая станция не может быть стартовой. Таким образом, за время O(N) мы умеем проверять, может ли первая станция быть стартовой. Покажем теперь, как проверить за O(1), может ли быть вторая станция стартовой. Для этого рассмотрим числа:

E1=D1-(a1-b1),

E2=D2-(a1-b1),

…

En=Dn-(a1-b1).

Распишем эти числа в более развернутом виде:

E1=(a1-b1)-(a1-b1)=0=(a2+a3+…+an+a1)-(b2+b3+…+bn+b1) – так как сумма всех ai равна сумме всех bi по условию.

E2=(a1+a2)-(b1+b2)-(a1-b1)=a2-b2

E3=(a1+a2+a3)-(b1+b2+b3)-(a1-b1)=(a2+a3)-(b2+b3)

…

En=(a1+a2+…+an)-(b1+b2+…+bn)-(a1-b1)=(a2+…+an)-(b2+…+bn)

Но, мы видим, что числа E1 для второй станции имеют тот же смысл, что и числа D1 для первой станции. Поэтому достаточно лишь проверить условие min(Ei)>=0. Но как это быстро проверить? У нас есть числа Di и из всех их вычитается одинаковое число => если минимум среди Di было число Dk, то среди Ei минимумом будет число Ek=Dk-(a1-b1). Таким образом, на то, чтобы проверить подходит ли в качестве ответа вторая станция – нам уже нужно O(1) операций. Аналогичным образом, зная минимум для второй станции мы проверим, подходит ли к ответу третья станция и так далее. После этого нужно не забыть решить задачу в обратном направлении, когда машина двигается по часовой стрелке.