Здесь приводится разбор всех задач прошедшего раунда. Вопросы и предложения задавайте в комментариях. Отдельное спасибо пользователю 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) операций. Аналогичным образом, зная минимум для второй станции мы проверим, подходит ли к ответу третья станция и так далее. После этого нужно не забыть решить задачу в обратном направлении, когда машина двигается по часовой стрелке.
>>Также можно было решать эту задачу используя set, или map вместо сортировки.
:D только на 1:27 (примерно так) допилил наконец-то этот вариант, будем надеяться пройдет.
За контест большое спасибо!
Задачи действительно увлекательные, интересные и главное для 2 дива!
Браво!
6, 12, 24...3*2^(n-2), 10, 15
и все тип-топ))
и никакой длинной арифметики))
6, 12, 18, 24, ....
10, 20, 30, 40, ....
15, 45, 75, 105, ....
Как компромисс - можно было дать n побольше, или ограничение не "меньше 100 цифр", а, допустим, "меньше миллиона".
А то у меня в решении каждое следующее число в 2 раза больше предыдущего (6, 12, 24, 48...), а многие вообще в бигинтежеры полезли.
Сдается мне что ответ это все числа делящиеся на любые два числа из тройки 2 3 5.
Т.е. [6, 10, 15, 12, 18, 20, 24, 30, 36, 40, 42, 45, 48, 50, 54, 60, 66, 70, 72, 75, 78, 80, 84, 90, 96, 100, 102, 105, 108, 110, 114, 120, 126, 130, 132, 135, 138, 140, 144, 150, 156, 160, 162, 165, 168, 170, 174, 180, 186, 190]
Я использовал числа 2*3*5, 2*3*7, 2*5*7, 3*5*7, а потом добавлял наименьшие возможные.
Так что задача "где максимум наименьший" была бы очень злобной :)
Да, я думал на тему 2 3 5 7, но этого варианта не заметил... Тогда вообще задача начинает попахивать поиском клик в графе.
Я попробовал найти минимум перебором, но до 24 подходит по 2 3 5 последовательность, а дальше уже подвисать начинает.
UPD: Можно выделить некоторый "базис", который потом домножать на все простые... Для 2 3 5 7 такой базис это [6,10,14,105]. Следующим тогда будет [6, 10, 14, 22, 1155]. Хотя, как доказывать минимальность все равно непонятно.
Писал сегодня на хаскелле. Вторая задача не прошла тайм-лимит, хотя идея такая-же как и в разборе...
Можно-ли увидеть образцовое решение на haskell?
А следующим числом будем ставить первое, которое удовлетворяет описанным в задаче условиям.
не прочитал авторский разбор - значит еще не проснулся...
На этот раз это случилось с задачей B. Мой код. У меня на тест 1 2 результат 1. Компилятор Code::Blocks. Как надо изменить код, чтобы он зашел на сайте (если других ошибок нет)?
Вспомните себя, когда начинали. А то пишут "всякие красные да оранжевые" , что просто сравнить числа как строки или заметить что 19 значные числа можно сравнивать в беззнаковом лонге))
\texttt{\$}
:)
\text{ \ }
In particular, problem E!!
My solution to B is O(n).Unfortunately I can't see my code, but I think the run-time error will be something trivial.
What is test case 14 for problem C? I tried to simulate the file system yet it ended up in a RE.
http://codeforces.net/contest/66/submission/19224146
well...I don't need it myself but, problem C's Editorial has been delayed for 6 years...
For whoever is interested, here is an outstanding and creative approach taught to me by IOI silver medalist, ICPC world Finalist and my teacher razimantv to problem D. It does not require big integers and teaches an important fact about binary numbers.
First, let us consider all the numbers (from 1 to N) in binary.
For each bit position, associate two primes — P[i], Q[i]. Multiply all numbers which have the i-th bit set by P[i]. Multiply all numbers which have the i-th bit unset by Q[i].
Now, all pairs of numbers which have a common bit set have a common factor. We only have to deal with those numbers which don't have any common bit (i.e. ... Those numbers who's XOR gives a string of all 1s).
We give all pairs of numbers (i, X) a common prime factor if i^X gives a string of all 1s.
Now, we have ensured that any two numbers have a common prime factor and no prime divides all numbers, We are done !
Here is code for this approach and here is some explanation.
(Here's the same code on GitHub)
In case, anybody requires more explanation for Problem D, I have written a post about it here.
My solution for D is like this:
First element will always be $$$2\times3$$$ and fill $$$n/2$$$ elements with $$$2$$$ while fill remaining elements with $$$3$$$. It will ensure that $$$n/2$$$ and $$$n-n/2$$$ groups have pairwise $$$gcd>1$$$ inside their groups. This also means that $$$gcd$$$ of all elements is $$$1$$$.
Now for every element from $$$2$$$ to $$$n$$$ multiply it by 5. This ensures that each pair has $$$gcd>1$$$.
Now for elements to be distinct, multiply elements with unique prime numbers.
Note: It will not work for $$$n=3$$$.
Solution link
Can anyone suggest how to deal with the overflow in C++? Long long is not sufficient for storing the answer and trying to perform multiplication with strings is very complex.