Разминочный раунд Яндекс.Алгоритм 2017

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Привет!

Сегодня в 16:00 по Москве состоит разминочный раунд Яндекс.Алгоритм 2017. Это хорошая возможность попробовать свои силы в соревновании по правилам TCM/Time, а также пройти в отборочный этап соревнования, для чего необходимо сдать хотя бы одну задачу.

Напоминаем, что для участия в турнире нужно зарегистрироваться, это ещё можно будет сделать на протяжении всей ближайшей недели.

Ссылка на вход в разминочный раунд появится на сайте соревнования незадолго до старта раунда.

Всем удачи!

Войти в контест!

UPD: Раунд завершён, всем спасибо за участие! Поздравляем четырёх участников, справившихся со всеми задачами:

Все участники, успешно сдавшие хотя бы одну задачу сегодня, автоматически проходят в отборочный тур соревнования.

UPD2: Разбор задач.

Комментарии (27)

Написать комментарий?

mahmud2690

8 лет назад, # |

How to solve problem D?

→ Ответить

himanshujaju

8 лет назад, # ^ |

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.

chintu

← Rev. 2 →

+13

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.

Fcdkbear

Как Е решать?

Svyat

Да там $\text{[math]}$ заходит за 0.6 с :(

MrDindows

← Rev. 3 →

Ну O(N³M) можно, например

kefaa

Можно O(N²(N + M)), если, зафиксировав две точки, выбрать третьей такую, с которой получится максимальный радиус. Вроде это неправда, но заходит.

mad.russian

Если отсортировать центры по ориентированной площади относительно двух фиксированных точек и рассмотреть первую и последнюю, то это будет правдой.

Zlobober

Вообще говоря, нет.

Ого, 260 миллионов операция с даблами уже заходят в 2 секунды. Или можно как-то в целых числах проверять?

+10

Не знаю как даблы, но я в целых делал.

Можно! Сейчас появится разбор, в нём это описано. Очень полезная техника, советую взять на вооружение.

Я просто домножил все формулы на знаменатель из формулы координат центра окружности, так себе техника)

Безусловно, можно избавиться от дробных вычислений и так, как ты сказал :)

Но у этого есть очень стройная интерпретация в терминах определителей, я описал её в разборе.

mgoncharov

Thank you for this round!

Couple things I want to mention:

please add -DONLINE_JUDGE to gcc — it's common practice that boilerplate code includes #ifdef to not include some headers at judge
problem statements (except for F) are kind of boring and too straight in the face. Maybe somebody likes it but it would be nice to have a "story" (even totally superficial)

allllekssssa

+32

I like short boring statements without story.

SarvagyaAgarwal

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 )