Четвертьфинал ЧМ по программированию по Восточному подрегиону NEERC пройдёт с 9 по 12 октября 2014 года в Уральском федеральном университете (г. Екатеринбург). Основной тур состоится 11 октября.
Традиционно на Тимусе будет проходить интернет-версия соревнования.
Официальная группа соревнования: https://vk.com/qf2014. В ней, кроме собственно новостей по четвертьфиналу, я каждый день буду писать по байке на тему истории спортивного программирования (в основном, на Урале, но это как пойдёт). Заходите, читайте, комментируйте.
Кстати, а кто-нибудь знает, даты каких четвертьфиналов NEERC уже известны?
UPD:
На Snarknews появилось расписание четвертьфиналов:
Рыбинск — 14-16 октября
Саратов — 20-22 октября
Москва — 26 октября
Санкт-Петербург — 8 ноября
А нет никакой информации по Московской четверти?
Московский регион — 26го октября http://it-edu.mipt.ru/ru/qf2014
delete
Четвертьфинал в Южном подрегионе (Саратов) состоится 20-22 октября
А будет ли проводиться интернет-версия Южного четвертьфинала?
Да, конечно.
А по какой причине вы отменили Code Game Challenge?
Центральный регион — 14-16 октября.
Может ли быть тренер не из ВУЗа? Не нашел это в правилах.
Еще вопрос по правилам:
А обязательно ли быть студентом дневной формы для участия в ACM/ICPC? Можно ли с вечерки катать?
Можно и с вечерки.
A student must be enrolled in a degree program at the sponsoring institution with at least a half-time load. This rule is not to be construed as disqualifying co-op students, exchange students, students serving internships, or extramural students.
В прошлом году в моей команде был заочник. Никаких подводных камней.
Отлично, спасибо.
Подскажите как решить С?
Понятно, что если посчитать преф. сумму по датам, то ответ на запрос — это минимальная сумма на префиксе. Тогда сделаем следующее:
1) Сожмем входные данные
2) Будем делать прибавление, add — количество денег, на суффиксе массива преф. сумм. При прибавлении будем поддерживать минимум.
3) Ответ на запрос лежит в корне.
Как решалась F?
Мы построили граф из пассажиров, где рёбра это противоречия в показаниях. Обошли все компоненты, для каждой покрасив вершины в два цвета, чтобы не было двух инцидентных вершин одного цвета, выбрали вершины того цвета, которых меньше. Вроде из условия следует, что циклов в таком графе не будет, стало быть, всё выше описанное можно сделать очевидным образом. Ну и частный случай, если не выбрали ни одной вершины, то выводим первого пассажира.
Это WA22.
Скорее всего вы не все противоречия рассматривали. У меня было WA 22 и я рассматривал только случай, когда один пассажир говорил, что видел другого, хотя они должны быть в разных местах. Как только я понял, что есть другого типа противоречия, решение сразу зашло.
Кстати, условие не говорит, что нет циклов. Оно говорит, что вершины бывают двух типов, и между вершинами одного типа нет ребер.
циклы есть, но только четной длины.
Подскажите как решить B?
В разборе говорят пользоваться DFS'ом с тремя состояниями. При обновлении состояния вершины мы запускаем DFS оттуда. Чтобы не получать TLE можно увеличить размер стека или написать нерекурсивный DFS.
Заменим каждый бар на две вершины : вход и выход. Рёбра из исходного графа идут из выхода первого бар ко входу второго и имеют вес 0. Добавим рёбра вида вход — выход для каждого бара с весом, равным числу Б52 в баре. После этого обратим все рёбра (не поменяв их вес). Теперь вопрос переформулируется так: чем оканчиваются пути, исходящие из данной вершины, веса рёбер которых, кроме, возможно, последнего, равны 0 (прошу заметить, что по условию все вершины достижимы).
Рёбра веса ровно 0 образуют некоторый орграф, его можно разбить на сильно связные компоненты. Внутри одной компоненты ответ один и тот же, ответ для компоненты можно посчитать, зная ответы для компонент-детей и "тяжёлые" рёбра, исходящие из неё (ребро "тяжёлое" тогда и только тогда, когда его вес больше 0).
UPD 1. Конечно же, надо ещё проверить, что вход в первый бар достижим из нашей верщины по рёбрам нулевого веса, это может поменять ответ на unknown.
UPD 2. Получает TLE 9 (на тимусе)...
UPD 3. На Codeforces заходит с пятикратным запасом.
Спасибо организаторам, теперь и в Тренировках: 2014-2015 ACM-ICPC, NEERC, Восточный четвертьфинал.
Add monitor from Timus plz
/gym/100507/submission/8267121
FAIL Participant found the better answer than jury didОЛОЛО РЕДЖАДЖ? :)
Да, я об это писал жюри 11 дней назад. Вроде мою сообщение переслали нужному человеку, но ответа не последовало. Очевидно, у жюри где-то ошибка :(
А мне на форуме ответили. Перед unique в чекере надо sort делать, я сам это проглядел
what is the problem E:Magic and Science solution
I guess it's just a lot of boring geometry
Also:
You should construct a physic model of this problem. Some physics knowledges are still needed.
You have to solve one simple differential equation at some point.
In the end you should solve three trigonometric equations that have general form V = A*sin(x) + B and find necessary intervals (when the magion moves quite fast).
And of course you should properly construct the path magion moves.
At least all of this were in my solution. As you can see — all inclusive! =) I tried to solve this problem using discrete solution — but I didn't pass the time limit.
Where can I found solutions ? Especially the two most hardest ?
Can someone who did H and F share their solutions?
F : We need to find some partition of people in two non-empty groups without contradictions in each of groups. It is not hard to prove that if every two people in group don't contradict, then there is no contradiction in all group. So we have next graph: vertexes are people, edges are contradictions in their testimonies. In statement it is said, that this graph can be 2-colored. We need to find its 2-coloring with smallest non-empty set of first color vertexes. It is easy to see that every connected component can be 2-colored in exactly 2 ways that differ by inversing colors of every vertex. It means that we have to color every connected component in 2 colors by simple dfs and blame crime on smallest part. Also there is the case, when nobody contradicts nobody, we can blame anybody (but exactly one person).
How we check contradictions? Two people don't contradict, if their testimonies are about same location (because everybody could have been there), if their testimonies are about different locations, they contradict if and only if they both have seen somebody (i. e. 1 says 3 was in one location, 2 says it was in another), including them.
UPD. About absence of more than 2-people contradictions : if we have several people that don't contradict by pairs, than everybody is located in not more than one place by their testimonies, so there is not any "big" contradiction without smaller ones.
Thanks! But I can't understand why this 2-coloring is better than greedily choosing the vertex to be "removed" (treated as criminal). I was choosing the vertex by their degree (in this case, amount of other vertices that has contradicting testimonials with the vertex). It seemed to work and I couldn't find any counterexamples.
As I said, there are only two ways of 2-coloring a connected component (and they differ by inversing the color. If we have connected 2-colored graph with different sizes of independent sets it is partitioned in, and also there are two vertexes with maximal degree in different sets, you can't tell them apart and can pick up one that is in bigger of independent sets at first turn. If you picked up "right" vertex at first turn in the connected component, you are destined to get smallest part, however. So, if you do that greedy one time, you will fail with high probability on some test cases (consisting of several connected components with described qualities).
So you technique should work if you work for components independently, use random when in doubt and repeat process several times (about 25 should be enough with a fair margin) for each component, using the smallest result you get. But it is much more harder to implement than simple dfs, IMHO.
Nice explanation, thank you very much
What if some component wasn't 2-colorable? A cycle of odd length for example?
Graph is 2-colorable because of statement. Statement says there is a way to 2-color graph ( real innocents and real killers).
Didn't read the statement carefully, my bad!
Thank you for the explanation.
H : First about algorithm : we will have stack (at first moment it is empty). Stack will contain ghosts and hunters. We will add ghosts and hunters in the same order as in input. We will call ghost and hunter pair, if hunter can attack ghost.
What can happen when we add new ghost/hunter? 1) Stack is empty. We simply add it to stack. 2) Top of stack is pair to object. Let hunter of that pair attack ghost of that pair and pop the top of stack. 3) Top of stack is not pair to object. We simply add it to stack.
If stack is empty after we add all 2n objects, we have found match, else there is no match.
Why it works? Well, it is quite obvious, that solution we have found is always valid, because stack if LIFO. It is a bit harder the other way, though.
Подскажите как решить I?
В любом из направлений автомобили, едущие прямо или направо могут беспрепятственно проезжать, затрачивая одну единицу времени. Автомобиль, едущий налево, должен дождаться окончания встречного потока, или встречного автомобиля, едущего налево (смотря что настанет раньше). Отсюда следует решение:
Есть 2 указателя: один на первой, другой на второй строке.
В начале указатели указывают на начало. Пока указатель хотя бы одной из строк не указывает на конец, выполняем итерации следующего алгоритма:
Сдвигаем указатели вправо, пока не дойдём до буквы 'L' или до конца. Максимальный из этих сдвигов прибавляем к ответу (автомобили проезжают сначала в обоих направлениях, потом на одном из направлений автомобиль ждёт). Если хотя бы по одной строке не дошли до конца, прибавляем ещё единицу (1 или 2 автомобиля повернули налево) и сдвигаем оба указателя на единицу вправо.
Could someone please explain me how to solve C?
I've been told that it's solvable using a Segment Tree, but I couldn't come up with a solution.
1) We can in
for all letters find their positions in chronological order (first sent, second sent, ..., n-th sent).
2) Suppose father already knows about letters with a1, a2, ..., ak money (ai is spent/earned money; if money was earned, it is positive, else it is negative) in chronological order (so first was gained/spent a1 roubles, than a2 and so on. Suppose
(and s0 = 0). It can be proved that answer is min(s0, s1, ..., sk).
3) If we add zero in any place of {a}, answer will not change. So we can assume letters say 0 before they are read by father.
4) So now we will have segment tree on array s1, s2, ..., sn. It will have to add something on suffix (when 0 is changed to x on k-th position, si increases by x for all k ≤ i ≤ n, other si don't change) and say maximum on whole array. It is quite easy to do with lazy updates.
5) At start si = 0 for all 1 ≤ i ≤ n. Then we process queries in input order next way: when we read next letter (which is k-th in chronological order), which tells about m of money, we add m to sk, sk + 1, ..., sn. After that we print min(0, min(s1, s2, ..., sn)). We can second argument in
with our segment tree).
So total asymptotic is
.
P. S. Input size is quite big and you should use input method as fast as possible (I TLE'd with scanf).
Couldn't think about [2] when trying to solve it :(
Very good explanation, thanks for the reply!