358A - Дима и непрерывная линия
Автор — Berezin
Если наша линия имеет самопересечения, то существует пара полу-кругов, которые пересекаются. Пусть точки x1 < x2 соединены полу-кругом, и точки x3 < x4 соединены полу-кругом. Тогда эти полукруги пересекаются, если выполняется одно из условий:
1). x1 < x3 < x2 < x4
2). x3 < x1 < x4 < x2
Перебираем все пары отрезков, таким образом, решение работает за O(n2), что удовлетворяет ограничениям.
358B - Дима и СМС
Автор — Berezin
Очевидно, что добавление случайных символов означает, что мы можем попросту их игнорировать, они не меняют структуру фразы на этапе < 3word1 < 3word2 < 3... wordN < 3. Давайте соберем фразу Димы до вставки случайных символов: s = " < 3" + word1 + " < 3" + ... + " < 3" + wordN + " < 3". пусть i — номер символа в s, который мы сейчас ожидаем. изначально i = 0; будем идти по тексту смс, и если нам встретился символ, который равен si просто увеличим i.
Если после прохода по тексту смс |s| ≤ i мы нашли все нужные нам символы, ответ — да, иначе — нет.
358C - Дима и контейнеры
Автор — Berezin
Поскольку мы знаем числа наперед, очевидно, что мы хотим извлечь три максимума. Максимумы можно предпосчитать, определив следующий 0, и пройдясь по всем числам между соседними нулями. Осталось определить, какие операции мы будем применять. Мы обязаны делать извлечения из разных контейнеров, поэтому будем хранить максимумы в вершине стэка, начале очереди, и начале дека (можно и по другому). Нужно определиться, куда какой максимум ложить: к примеру, первый (самый большой) — в стек, второй — в очередь, третий — в начало дека. "мусор" — остальные числа, можно записывать в конец деки. Также нужно предусмотреть случаи, когда между соседними нулями меньше 3 чисел.
358D - Дима и зайцы
Автор — Sereja
Посмотрим на первого зайца: мы либо берем его перед вторым, либо после. Если он взят после второго, то задача от второго зайца и до последнего не зависит от первого зайца, иначе, если мы взяли первого зайца первее, мы получим почти такую же задачу, только скажем, что перед втором зайцем уже что то есть. Таким образом имеем две динамики:
1). d0i — ответ для суффикса, как для отдельной задачи
2). d1i — ответ для суффикса, если перед первым зайцем уже что то стоит
переходы:
d0n = an
d1n = bn
d0i = max(ai + d1i + 1, bi + d0i + 1)
d1i = max(bi + d1i + 1, ci + d0i + 1)
Ответ на задачу d01.
358E - Дима и пинки
Автор — Sereja
Первое что стоить понять, что ответ — это делитель максимальной по длине последовательности подряд идущих закрашенных клеточек.
Будем перебирать это число. Теперь осталось проверить таблицу зная величину шага K.
Найдем самую левую, а из них самую верхнюю закрашенную клетку. Пусть это (X, Y), тогда после каждого шага Дима мог оказаться только в клетках вида (X + K * a, Y + K * b). Пусть закрашенные клетки такого вида — вершины графа. А последовательности закрашенных клеток, соединяющие их — ребра. Построим граф. Проверим, что нету лишних закрашенных клеток. Проверим граф на связность и наличие Эйлерова пути. Если все условия соблюдены, то мы нашли очередной ответ.
При правильной реализации получим решение со сложностью примерно O(N * N * log(N)). На самом деле она почти никогда не будет достигаться.
Резве в задаче А условия пересечений должны быть не
x1 < x3 < x2 < x4
x3 < x1 < x4 < x2 ?
Скажем, если x1 < x3 < x4 < x2, то условие x1 < x3 < x2 выполняется, а пересечения нет.
спасибо.
В задаче Е, наверное, все-таки нужно проверять наличие Эйлерового пути, а не цикла?
да, старая версия задачи :)
Е легко решается за О(N*M): 4890948
Вроде у тебя тоже N^2logN за счет НОДа
Например, 4892297 — честное O(n*m). Вроде бы из кода видно, что НОД считается O(n+m) раз и это не влияет на асимптотику.
Согласен. Для чистого квадрата можно, например, прекалькнуть НОД.
А почему в задаче D n всего до 3000? Автор намеренно сбивал с правильного пути на какую-то двумерную динамику?)
Нет правила, что ограничения должны быть критичными.
Почему в задаче Е получается такая сложность решения? Если я не ошибаюсь, оценка количества делителей — корень кубический, а не логарифм.
Пусть делитель у нас есть K. Я умею делать проверку за O(N/K*M/K). Получаем сумму, которая выходит даже меньше O(N*M*log(N)), которую я написал как верхнюю оценку, само собой можно дать и более хорошую оценку.
solution to problem D still not clear, would appreciate if someone could provide a better explanation.
f[i][0]:set i before i-1 f[i][1]:set i-1 before i
f[i][0]=a[i]+max{f[i-1][0]-a[i-1]+b[i-1],f[i-1][1]-b[i-1]+c[i-1]} f[i][1]=b[i]+max{f[i-1][0]-a[i-1]+a[i-1],f[i-1][1]-b[i-1]+b[i-1]} =b[i]+max{f[i-1][0],f[i-1][1]}
i=1 is special since it doesn't have state f[i][1]
look my code for detail:my code
For any hare except the first and last there can be three cases :
So when I am at a particular hare I should know if I have fed the previous hare and I have to make a decision for the current one that whether it should be fed now or after the next hare
So state would be like
( int position, bool previous )Boundary conditions :
*Now I will call my solve function as solve(0,0) coz 1st hare has no left adjacent hare.so I assume it as hungry always
*When I am at my last hare I will take care not to feed any right adjacent hare of it
u can see the code here :)
awesome explanation, thank you so much!!
Crystal clear explanation. Thank you. :)
great explanation.. thxs a lot!!
problem A have more simple solution
you pick two consecutive points and check them with all other consecutive points
let the points to be x1,x2 and x3,x4. you want to check if semi-circle between x1 and x2 intersects semi-circle between x3 and x4.
**all you have to do is swap x1 with x2 if x1 > x2 and swap x3 with x4 if x3 > x4
this will lead to one condition if ( x1 < x3 < x2 < x4 ) then intersected**
i know it's easy to some people but some guys got stuck with it ^_^
Another possibilty though involving too much work is treat each semicircle as a circle and find centers and radius of each. Now two circle intersect iff
Same O(n^2) complexity
Problem A condition 1 and 4 are same. condition 2 and 3 are also same.
Почему в разборе задачи А условие 1) совпадает с условием 4). А условие 2) совпадает с условием 3).
Задача D напоминает что-то очень недавнее...)
Задачу с недавнего Гран-При мы 2.5 часа решали именно с таким понимаем условия :)
и мы часика полтора
Can we do problem D with recursion? If possible can anyone please explain the states and base case?
use recursion you will get TLE and has many repeated problem
I am talking about DP with recursion I have written this code but its not working,
int n,a[3001],b[3001],c[3001],dpTable[3001][2]; int feed(int depth,bool feeded) { if(depth == n) { if(feeded) return b[n]; else return a[n]; } if(dpTable[depth][feeded]!=(-1)) return dpTable[depth][feeded]; int x; if(feeded) x = max(b[depth]+feed(depth+1,0),c[depth]+feed(depth+1,1)); else x = max(b[depth]+feed(depth+1,0),a[depth]+feed(depth+1,1)); return dpTable[depth][feeded] = x; }http://mirror.codeforces.com/blog/entry/9334#comment-149501 this one is awesome!!
really awesome. thanks.
my recursive solution for D https://mirror.codeforces.com/contest/358/submission/91724299
I wrote the code for Dima and the Text Messages in CodeForces Round 208 division-2 in Java. Every time I submit the code it says TLE. But don't know why it says so even if I am using BufferedReader and PrintWriter for reading and printing the values. My solution code in 4901148.
String concatenation is not efficient in Java. It create a new String and copies the old value because in this language, Strings are an immutable type. You can use .concat or StringBuilder instead or rethink the algorithm.
Пытался решать D так (не дописал код пока): Берем разделяем всех зайцев последовательно на тройки(по три зайца), а остаток оставляем сбоку. И "заменяем" тройку на одного зайца(числа(если сыт слева, справа, оба, ни одного) для этого зайца можно посчитать перебором, только нужно считать когда правый сосед, когда левый(а не просто один сосед)). Остаток также заменяем на одного зайца считая для него также чиселки перебором. Перешли к такой же задаче, только с n2 = n1 / 3. И дальше так спускаемся, пока не получим одну задачу для n = 3 с тремя зайцами :]. Сложность получается O(nlogn)(каждый раз делим n / 3 и пробегаем по новому массиву). Верно ли это, будет ли оно работать? P.S. Писалось довольно неприятно :] (по сравнению с динамикой)
For the 3rd problem 'Dima and containers', what if after the end of all operations there are some numbers left in the containers? If this is a possible case then the approach given in the editorial would not work and if it this is an invalid case, shouldn't this be specified in the problem statement. I did not code the solution to this problem because of the following test case:
8 9 6 5 8 7 3 0 0
According to the editorial 9 would be stored in stack, 8 in the queue and 7 in the deck(front). all other numbers will be stored in the end of deck. For the first 0 operation all three containers will be popped giving 24 (9+8+7). But for the second zero only one container can be popped giving 6. so total answer is 30 while the optimal answer will be 38.
After the 0-command you should empty all the containers.
Guess I missed that...
actually, the second
8will be stored in the deck(front), while the numbers6,5,7,3will all be stored in the deck(back). therefore optimal answer for first0is8+9+8 = 25(not24)The first 8 is for the number of operations.
oops, sorry about that....then ur right, the answer should be
24.куда какой максимум ложитьскладывать и только складывать...
PS. лучше проверяй орфографию и пунктуацию при составлении поста или отсылай кому-нибудь, кто знает язык лучше. есть еще пара ошибок по мелочи, но это уже мелкие придирки:)
В таком уж случае "класть", а не "складывать".
И это не орфография или пунктуация, а морфологическая ошибка.
Да и вообще, как по мне, совершенно необоснованный запрет на это слово. Сколько не пытался найти причину, ничего толкового не находил, везде одно и то же: "в русском языке слова ложить нету" ...
Конечно, можно и "класть".
Это да, но в посте есть и такие ошибки, на которые я не считаю нужным указывать, ибо они по мелочи.
Вполне вероятно, что запрет необоснованный.
На каком-то форуме прочитал, что в Украине почти все говорят "ложить", так что снимаю свои, так сказать, "обвинения".
А если по сути, то контест очень удачный, разносторонний и с подвохами, что только в плюс автору.
В задаче С, как действовать, если нам придется извлекать мусор? Т.е., если между двумя запросами извлечения не вставляется ни одно число, а в деке осталось много чисел, то как быть?
UPD: эх, недосмотрел условие. Ну да, теперь понятно.
in problem E,ans is not "divisor of maximal-length sequence of standing one by one ones",for example testcase 3 maxlength=4 and ans=3,maybe i didn't understand idea and can someone explain me the main idea in detail?
answer should be "divisor of maximal length sequence" minus 1; because if the answer is
2, then there will be3consecutive1s (start square, end square, and square u have jumped over)more formally k should be divisor of all consecutive ones length,there is not Necessary maximum length.Am I right?
yes i think you are right.
Can someone explain the Problem C ? I understand that the first three maximums between two 0s in the input are stored appropriately in the containers provided, so that when asked to pop, we can pop the maximums, one from each container. Please correct me if I am wrong. If I am right, please clarify my doubt : What happens if there are consecutive 0s, that is you need to pop multiple times continuously. In that case, we would need to take care of not only the first three maximum numbers, but also assign the remaining numbers appropriately. This solution doesn't seem to handle that : http://mirror.codeforces.com/contest/358/submission/4883559 . However, it has been ACed. Please explain how it works.
Упс, не внимательно читал условие, там после извлечения нужно все контейнеры опустошать. =)
Может кто-нибудь пояснить почему по Е будет неправильным такое решение:" построим граф, где вершинами будут 1-клетки, у которых либо не ровно две соседние клетки содержат 1, либо две соседние клетки, но не на одной горизонтали/вертикали. Теперь проверим есть ли в графе Эйлеров путь. Если он есть, то возьмем НОД длин всех ребер в этом графе и выведем его делители" ?
The editorial for problem E reads: "The first thing to understand is that the answer is the divisor of maximal-length sequence of standing one by one ones".
Note that the answer will also be the divisor of ( minimum length consecutive segment of $$$1s$$$ of length $$$> 1$$$ that cannot be extended further $$$-$$$ 1) [with the exception of a grid containing all isolated $$$1s$$$, in which case, $$$0$$$ is the only possible solution and the output has to be $$$-1$$$ ].
This is super late but there is a simple $$$O(n)$$$ solution for 358A if anyone's interested: https://mirror.codeforces.com/blog/entry/66841
Could you link your submission for your O(n) solution? I found the O(n log n) for the A problem. Here it is 109041885
The idea is the following. We add the points incrementally and check and update our information about the state. If the closest neighbour to the newly added point from the left or from the right are closer to it than the previous added point, then there is an intersection. Of course there are some special cases when using std::set but nothing hard.
But how to get to O(n)?
I find the method of dynamic programming for problem D is interesting and quite new to me so are there any problems that are similar to that one? If yes, please give me some, I would appreciate it very much. Thank you!