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

№	Пользователь	Рейтинг
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3382
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

№	Пользователь	Вклад
1	Qingyu	155
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	134
9	maroonrk	132
10	cry	130

Привет!

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

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

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

Всем удачи!

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

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

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

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

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

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

mahmud2690

10 лет назад, скрыть # |

How to solve problem D?

→ Ответить

himanshujaju

10 лет назад, скрыть # ^ |

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 )