Just a kindly reminder that TopCoder SRM #568 will start in about hour and a half
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
16:42:31
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
16:42:31
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 00:52:29 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Егор, спасибо, а то я бы опять пропустил :)
Чуть не заставил об этом жалеть :)
Какой клёво сбалансированный контест.
Секунды решают десятки, если не сотни мест. Хорошо, хоть очки зависят от секунд, а не как здесь — от минут
PS Никаких претензий к автору. Он молодец.
А челлендж решает 300+ мест.
Великолепно, учитывая что их возможность сильно зависит от комнаты.
Как делать 500?
У меня были идеи с дфс и кучей муры, но так я это и не дописал.
Ну пока сэмплы проходит такое решение: посмотрим на таблицу, как на двудольный граф, где ребра — клетки, в которых стоит не '-'. Тогда в каждой компоненте связности такого графа можно определить все значения(это как раз какой-то дфс), проверим сразу что все они неотрицательные и найдем в каждой компоненте минимальное, пусть они получились v0, v1, ..., vm - 1. Тогда нам нужно найти количество таких наборов чисел x1, x2, ..., xm - 1, что min(0, x1, x2, ..., xm - 1) + min(v0, v1 - x1, ..., vm - 1 - xm - 1) ≥ 0(вообще говоря сумма слева это и будет минимальное число во всей таблице). Для этого можно например зафиксировать левый минимум и первое из чисел на котором он достигается. Тогда на все остальные иксы будут просто лежать в каких-то отрезках, надо просто перемножить их длины.
прошло, но на задачу пришлось потратить два срма :o
Что такое куча муры?
Куча Муры — это дохера кода, в котором не понятно где +/- 1 и много левых ифов :)
а я уже гуглить начал)
Что интересно, были 2ые задачи на много легче сегодняшней, но имели стоимость 600.
Сложность относительна внутри одного матча
Есть же универсальное мерило — челлендж. Тогда надо и его стоимость менять.
Upd. Поясню: если написанное выше верно, то можно было бы сделать стоимости, например, 25000-50000-100000. Но так сделать сложно, ведь они "завязаны" на челленджи, которые бы обесценились.
Upd2. На самом деле написанное Егором правда, но этого не достаточно чтобы оправдывать стоимости задач, так как есть челленджи.
Челлендж есть, но изменения в стоимостях задач достаточно малые, чтобы нарушить баланс челленджа. Ведь стоимости в 512 СРМе явно ставили не задумываясь о челленджах ;)
Why KADR's solution was challenged? It looks right as for me.
TL
He has sorted 504 vectors. It seems that constructing of such number of vectors takes too much time.
МГУ Хэт Трик, однако :)
I compete on SRM 568 DIV 2 and using dp table 55 * 5 * 55 * 55 * 55 for 500 pt that approximately 45753125 and I got SIGKILL on final test, I wanna ask, what's is memory limit for topcoder ? Thanks
It is 64 Mb