Приветствую всех на Codeforces Beta Round #13, который состоится в четверг, 6 мая в 18:00 по московскому времени. Автором задач этого контеста буду я.
Хочется сказать отдельное спасибо Михаилу Мирзаянову, который сделал проведение контеста возможным, Роману Едемскому и Андрею Максаю за помощь в тестировании авторских решений, а так же Дмитрию Матову за перевод условий на английский язык. Надеюсь, задачи вам понравятся.
Желаю чтобы число 13 оказалось для вас счастливым!
UPD: Поздравляю Ивана Метельского, который стал победителем решив все 5 задач!
Задачи можно посмотреть тут.
Полные результаты можно посмотреть тут.
UPD2: добавлен разбор.
Немного личной информации:
Я учусь в Киевском Национальном Университете им. Т. Шевченко на первом курсе. Более-менее серьезно начал заниматься олимпиадным программированием в конце 10 класса после провала на республиканской школьной олимпиаде и пока не собираюсь бросать :) Год тренировок не прошел даром и после него последовало золото на IOI 2009. Сейчас решил почувствовать себя по другую сторону баррикад, выступив в роли автора задач, а не в роли участника. Очень рад что представилась возможность поучаствовать в жизни такого замечательного ресурса как Codeforces.
Обсуждение задач предлагаю проводить здесь в комментариях после конца контеста.
Может перенести на завтра?)
Считаю весьма коварным тот факт, что в задаче B условие ("а третий соединяет 2 точки на разных отрезках.") а на деле оказалось совсем иначе. Причем когда посмотрел в рассылку - понял, что зря я так извращался с нахождением пересечения 2-ух отрезков в "общем случае". На деле всё выходило куда проще, но будучи уже прилично злым на непонятные WA я бросил задачу, так и не дорешав.
Может быть, что глюки были в чем то ещё - но само решение было бы однозначно проще и я его бы сдал, если бы я сразу понял то, что было написано в рассылке . :(
Вопрос - есть ли решение с той же асимптотикой без шаманств?
Мне почему-то кажется, что у авторского решения такая же ассимптотика (т.е. N^2 * (N + M)).
заменив long long на double
Вообще с учетом того, что даже N^2 (N + M) решения требовали значительных оптимизаций, мне кажется, что более щедрый тайм-лимит по этой задаче (скажем, 4 секунды вместо 2-х) был бы более правильным.
http://mirror.codeforces.com/contest/13/status/D
Там он немного кривой, т.к. пришлось в TopCoder Arena писать (у меня не было плюсов на компьютере).
Вот например в графе если ребро соединяет две вершины, то ведь эти две вершины являются концами ребра.
/\
/ \
--/----\--
/ \
Может стоит как то более наглядно оповещать всех о рассылке?
Большую часть времени участник сидит наверно на странице "Мои посылки".
Может стоит уведомление показывать так, чтобы его можно было как можно быстрее для себя увидеть, а не только на странице с задачами?
Мне задачи очень понравились. Простые для понимания, новые для меня, красивые задачи :-) Автору respect!
А про задачу B:
По-моему, могли бы клар и не давать. На некоторых контестах, жюри посовещалось бы и ответило "No comments". ;-)
А всем, кому хочется на некоторую неточность условия пожаловаться, могу посоветовать ответить для себя на вопрос "Как нужно было думать на контесте, на что следовало обратить внимание, чтобы такой проблемы с пониманием условия для меня не было?".
Не хотел бы я участвовать в таком "некотором" контесте :) Я не вижу явного противоречия в том, чтобы понять условие как "третий отрезок пересекает каждый из двух остальных", хоть эта интерпретация и кажется совершенно неинтуинтивной.
Overall, the problems were nice. Thanks for the round!
I think (and this is a question to Mike) it would be nice to have a kind of standard for setting time limits at Codeforces. For example, time limit must be at least twice the running time of the reference solution implemented on the slowest available language (or something like this).
The slowest language here would be Ruby or Python (or maybe php?) - and they are pretty slow. 2x Ruby speed allowance might sometimes make slower C++ pass.
The slowest language here would be Ruby or Python (or maybe php?) - and they are pretty slow. 2x Ruby speed allowance might sometimes make slower C++ pass.
In this case, it would be nice to define the subset of allowed languages such that each problem is guaranteed to be solvable on each of these languages. Then the limit can be set based on the reference solution written on the slowest language from this subset. I'm not sure if it's a good idea to include only C/C++ in this subset.
Anyway, I don't really mind how the time limits are set. It just would be nice to have a common publically available standard to set them.
Ещё раз повторюсь, что в идеале надо так тщательно подгонять размер входных данных (или даже корректировать формулировку задачи!), чтобы алгоритм с плохой асимптотикой не проходил даже при сколь угодно хороших оптимизациях.
что надо рассмотреть только концы третьего отрезка.
Насколько я понял, автор поста обращает внимание именно на слово концы
именно так я и сделал :)
Задача B конечно тяжка в плане аккуратной реализации.
Вроде бы все сделал правильно. Нашел общий конец 2-х отрезков. Из этих двух отрезков сделал треугольник, высчитал все длины, по ним определил, как эти отрезки вообще расположены, т.е. не образуют ли они вырожденный треугольник. Далее через теорему косинусов нашел косинус угла между 2 отрезками, т.к. по синусу фиг поймешь, больше 90 он или нет.
Далее из алголиста скопипастил уравнения для принадлежности точки отрезку. Посчитал быстренько равенство при котором точка принадлежит. Вроде пашет. Ну и дальше проверил отношения длин.
Вроде бы все правильно, локальные тесты проходит, а все равно WA.
Далее заменялись int'ы на long long'и, long long'и на double'ы... Вместо косинуса поставил арккосинус, но все тщетно...
Дело в том, что если я делаю присваивание обрабатываемой переменной текст из условия, задача 1 тест проходит, валится на втором (понятно почему).
Если же я беру данные для обрабатывания из STDIN, то задача валится на 1 тесте.
Если 1 тест отличается от примера в условии, можно его узнать?
+135 у победителя и +36 у vepifanov.
1
0 10 0 5
0 10 0 0
0 2 0 7
Rejudge will be dishonest.
So, ignore contest results?
F(position,value) - number of steps you need to do in order to obrain a non decreasing sequence starting at 1 and ending at position, when the number in position is equal to value.
F(1,value)=abs(a[1]-value), where a[1] is the initial value at first position.
F(P,V)=min(F(P-1,W<=V)+abs(V-a[P])) for P>1
The second key observation was that it is not optimal to change value of a[i] to value that hasn't been in the initial sequence. F(P,v1), F(P, v2), .. and so on can be computed in linear time by updating value of minimum on each step and the whole complexity is equal to O(N^2).
5 5 1
I've seen a similar problem at BOI'2004: http://www.boi2004.lv/Uzd_diena1.pdf (third problem). The main two differences: the limit on sequence length is 1000000, resulted sequence must be strictly increasing. I've been thinking for quite a lot on that problem and still don't have any working ideas. If anybody has clues on how it can be solved, could you please post.
This property leads to O(N^3) solution and this is the best I was able to come with so far. Of course, something much faster is required...
The ones on the left and the ones of the right of the fixed element.
- For example, If you consider the elements at the right of t[k]:
If you consider the vector c[i] = t[i+1] - t[i] - 1 for each
You can compute the result by doing two passes one for the elements lying at the right and left of the fixed element.
I don't know if this is correct yet but I will try to explain myself later.
Thank you for the reference, even with google translator it was a very good source of learning. But I couldn`t find the specific article in the magazine page, if you know how to get it in PDF or something like please tell me or Maybe I`ll just e-mail Filip Wolski xD
My solution is same but getting WA in #6.
My solution is same as maksay described but getting WA.
F(P,V)=min(F(P-1,W<=V)+abs(V-a[P])) for P>1
What's W<=V ? What's W ?
Вот смотрите - алгоритм для B (могу код послать):
- берём первое число и запускаем цикл for длиной в него
- в начале берём первые три строки запихиваем их в массивы ((x, y), (x, y))
- параллельно ведём массив allpoints всех точек (6 штук)
- смотрим - если все значения в массиве allpoints разные - сразу отлуп с NO
- затем смотрим по количеству совпададающих элементов в массиве allpoints - если есть элемент повторяющийся ровно два раза и такое повторение одно, то запоминаем эту точку (intersection) и проверяем дальше, иначе сразу отлуп с NO
- далее создаём массив из двух отрезков с общей вершиной (далее - "пересекающихся") и переменную с ещё одним отрезком, который "третий"
- у пересекающихся отрезков считаем длины, затем считаем длину отрезка между вторыми точками этих отрезков
- по теореме косинусов находим угол между "пересекающимися" и проверяем его модуль что он меньше пи пополам (одна формула)
- для каждого из "пересекающихся" отрезка находим точку у "третьего", которая на них лежит (проверяем - если расстояние от точки на "третьем" отрезке до обоих концов отрезка в сумме равно длине отрезка) - сразу же запоминаем эти длины, используемые для сравнения в сумме, для сравнения их между собой (критерий 1/4).
- сравниваем между собой, если больше 1/4, сразу отлуп с NO
- если не нашли на "третьем" точку, которая принадлежала бы определённому отрезку, сразу отлуп с NO (break из цикла по "пересекающимся").
- по завершении цикла по пересекающимся пишем YES
На этом весь алгоритм. Регение валится по времени на тесте 2.
Или, что ещё более тупо, косяк со считыванием. Ты говоришь "берём три строки"... если считывание действительно как-то по строкам, а не по отдельным числам, то может вешаться из-за мусора во входном файле вроде лишних переводов строки или пробелов где не надо.
I know this blog entry has been inactive for quite a long time. However, I recently heard there is an O(N log N) solution to problem C. Can anyone explain it?
EDIT: Here's a link: http://mirror.codeforces.com/blog/entry/18424#comment-234171