Привет!
Сегодня в 16:00 по Москве состоит разминочный раунд Яндекс.Алгоритм 2017. Это хорошая возможность попробовать свои силы в соревновании по правилам TCM/Time, а также пройти в отборочный этап соревнования, для чего необходимо сдать хотя бы одну задачу.
Напоминаем, что для участия в турнире нужно зарегистрироваться, это ещё можно будет сделать на протяжении всей ближайшей недели.
Ссылка на вход в разминочный раунд появится на сайте соревнования незадолго до старта раунда.
Всем удачи!
Войти в контест!
UPD: Раунд завершён, всем спасибо за участие! Поздравляем четырёх участников, справившихся со всеми задачами:
Все участники, успешно сдавшие хотя бы одну задачу сегодня, автоматически проходят в отборочный тур соревнования.
UPD2: Разбор задач.
How to solve problem D?
I solved it with DP : DP[index][parity of previous element][parity of current element]. The main idea is you wouldn't use the operation twice on the same index.
Greedy — http://ideone.com/rhDW7F You do at-most 1 operation at each position. Fix operations on borders(4 cases), then starting from first position, do this greedy procedure — if any is of opposite parity, increment next 3. If last 2 are in order, update answer.
Как Е решать?
Да там
заходит за 0.6 с :(
Ну O(N3M) можно, например
Можно O(N2(N + M)), если, зафиксировав две точки, выбрать третьей такую, с которой получится максимальный радиус. Вроде это неправда, но заходит.
Если отсортировать центры по ориентированной площади относительно двух фиксированных точек и рассмотреть первую и последнюю, то это будет правдой.
Вообще говоря, нет.
Ого, 260 миллионов операция с даблами уже заходят в 2 секунды. Или можно как-то в целых числах проверять?
Не знаю как даблы, но я в целых делал.
Можно! Сейчас появится разбор, в нём это описано. Очень полезная техника, советую взять на вооружение.
Я просто домножил все формулы на знаменатель из формулы координат центра окружности, так себе техника)
Безусловно, можно избавиться от дробных вычислений и так, как ты сказал :)
Но у этого есть очень стройная интерпретация в терминах определителей, я описал её в разборе.
Thank you for this round!
Couple things I want to mention:
-DONLINE_JUDGE
to gcc — it's common practice that boilerplate code includes #ifdef to not include some headers at judgeI like short boring statements without story.
In problem C , What's wrong with first sorting the array and then doing a DP , where DP[i] = min(DP[i-1],DP[i-2]) + 1 . (DP[i-2] is only included when abs(arr[i] — arr[i-1]) <= 1 )
It should be abs(arr[i] — arr[i-1]) <= 2, can choose arr[i] — 1 and arr[i — 1] + 1.
Thanks. Is there anything else wrong with this approach ? I still get a WA on case 41.
I passed with this approach. maybe there is some minor bug in your program ? http://ideone.com/wW1ZsF
Thanks.
I got WA-41 too. Can anyone guess the type of test case?
Maybe something like:
10
1 2 2 2 2 3 3 3 3 4
ans = 5
Thanks, that helped
Not for me. :(
F = mincost?
Yep.