Напоминаю, что сегодня (10.11.2012) в 18:00 по Москве состоится второй контест хорватской олимпиады по информатике. Залогиниться/зарегистрироваться можно тут. Продолжительность: 3 часа. Удачи!
№ | Пользователь | Рейтинг |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
Напоминаю, что сегодня (10.11.2012) в 18:00 по Москве состоится второй контест хорватской олимпиады по информатике. Залогиниться/зарегистрироваться можно тут. Продолжительность: 3 часа. Удачи!
Название |
---|
Как решать 4ую?
Отсортируем все блюда по неубыванию обычной цены (**B**). Предподсчитаем 3 массива:
Рассмотрим 2 случая:
sum[k] - maxD[k]
sum[k-1] + minA[k]
Выберем минимум из этих вариантов — это и будет ответом для текущего k.
Третья уже была :)
Anyone has idea for problem 6? It looks like we have to maintain a set of slopes to calculate the queries, but I can't find an effective way to add a new slope since the profit values are not monotonous.
The trick is to find a way to reduce number of times you have to rebuild the hull.
Как решать 5ую задачу?
Сделаем паросочетания цифра — место. Каждое наблюдение делает 2 вещи. Если мы знает что на одном отрезке минимальное число Х, то во-первых, на этом отрезке числа могут быть только от X до N-1, а во-вторых число X может быть только на этом отрезке. Получаем матрицу из 1 и 0. Дальше можно делать всё, что угодно — макс. паросочетания, Венгерка и.т.п.
Матрицу можно получить следующим образом: будем считать "во-первых" и "во-вторых" отдельно. "Во-первых": сначала пробежимся по наблюдениям, и посчитаем, какие числа могут на этим месте быть. Заметим, что это отрезок. Соответственно, обновлять можем за O(M*N) — для каждого наблюдения пробежаться по каждому месту. Потом обновим матрицу "во-вторых": для каждого наблюдения возьмём "пограничное" число и обнулим его вне допустимого отрезка. O(M*N). Итого, получили матрицу.
Just published Results.