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

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Привет!

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

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

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

Всем удачи!

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

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

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

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

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

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

mahmud2690

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

How to solve problem D?

→ Ответить

himanshujaju

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

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 )