Russian Code Cup QR 3

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

← Rev. 2 →

На ACM-like соревнованиях это чит. Можно под левым аккаунтом отсылать решения и тестить их на валидность и не поулчать лишнего штрафа.

Вот дорешивание бы...

→ Ответить

NikitaPogodin

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

Можно и без внеконкурсного участия зарегистрировать левый аккаунт и отсылать решения.Скан паспорта ни у кого не просят, это уже вопрос морали.

→ Ответить

dyussenaliyev

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

← Rev. 3 →

>>Вот дорешивание бы...

Есть тесты на сайте

→ Ответить

JKeeJ1e30

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

это не совсем то

→ Ответить

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

← Rev. 2 →

Как закончиться - расскажите как сдать E, пожалуйста! Ведь там что-то сложнее "реализации", как я думаю. Или все таки ошибаюсь?

→ Ответить

Scorpy

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

← Rev. 2 →

У меня прошла просто реализация.

Сначала будем считывать числа и распихивать их по очередям так:
1. Берём очередное число
2. Находим такую очередь с минимальным номером, что она либо пуста, либо последнее число меньше текущего.
3. Если такая есть - вставляем элемент в неё, иначе выводим No
Потом будет доставать минимальный из первых элементов очередей.
Доказательство там вроде очевидное, но длинное

→ Ответить

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

А ты сдал это решение? У меня большие сомнения, что оно будет работать правильно.У меня все то же самое, только в пункте 2 решения Scorpy я нахожу такую очередь что у нее последний элемент меньше нашего, но максимальный из таких.

→ Ответить

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

У меня такая же идея один в один.

→ Ответить

Scorpy

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

Да, сдал

→ Ответить

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

Конечно первая такая очередь будет содержать максимальный элемент, так как концы очередей всегда отсортированны по невозрастанию (если изначально во все очереди добавить заглушечный ноль).

→ Ответить

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

← Rev. 4 →

Задачу E можно сдавать, например, так. Пробуем по порядку поместить каждое число из входной последовательности в какую-нибудь из очередей, при этом число помещаем в очередь, только если в ней до этого не было элементов, больших нашего числа. Если на каком-то этапе нет такой очереди, выводим "NO". Иначе после окончания этого процесса идём по очередям и извлекаем элементы в том порядке, который нам нужен (для этого можно сделать копию исходного массива и отсортировать её). Попутно с этими двумя процессами формируем ответ. Данное решение проходит все тесты.

→ Ответить

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

Тупое моделирование процесса с одной идеей. Очевидно, что во всех очередях все элементы должны идти по возрастанию. Очередной элемент нужно класть в ту очередь, где последний элемент в очереди - наибольший, но меньше данного.

Заведем k очередей. Также отсортируем список, чтобы узнать порядок, в котором нужно выводить элементы из очередей.

Дальше повторяем следующий процесс. Сначала из начала очередей удаляем все элементы, если их пора вывести. То есть если тот элемент, который нужно вывести есть в начале какой-то очереди, то удаляем из очереди. Так пока не удалим все элементы, которые уже можно удалить.

Теперь пытаемся добавить в очередь следующий элемент из массива. Находим очередь, в которой последний элемент меньше данного (добавляемого), но при этом максимально возможный. Если такой очереди нет - берем любую пустую очередь. Если и такой очереди нет (т.е. во всех очередях есть элементы и все последние элементы больше данного), то выводим No.

→ Ответить

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

Пытался реализовать эту идею, по-ходу надо "прямить руки" :)

→ Ответить

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

Все. Понял. Моя реализация была немного не корректна

→ Ответить

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

Расскажите, как D нормально решалась, пожалуйста. Генерация всех подмножеств с суммой 1000, а затем нахождение максимального количества непересекающихся из них почему-то не прошли.

→ Ответить

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

← Rev. 3 →

Её можно было сделать динамическим программированием по подмножествам. Ставим подзадачу: какую минимальную сумму нужно потратить, чтобы отправить все предметы из подмножества i? Для каждой подзадачи перебираем подмножество j - предметы, отправленные последней бандеролью. Считаем стоимость этой последней бандероли и при необходимости обновляем ответ для текущей подзадачи. Здесь требовалось знание основных приёмов работы с множествами. Возможно, её можно сделать и попроще в смысле логики работы алгоритма, но это решение получается достаточно компактным и быстро пишется.

→ Ответить

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

Забавно:) Я пока было время, брал случайную перестановку предметов, а далее вычислял ее стоимость, предполагая что сначала идут предметы, отправленные в бандеролях по 1000г. Пишется очень быстро, и совсем не надо думать.

→ Ответить

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

Но это же за 14! работает? Или у Вас умнее?

→ Ответить

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

Если подобавлять каких-нибудь несложных отсечений, то все пройдет. Даже за 14! =)

→ Ответить

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

Эх, постеснялся писать такое :)

Придумал за 2^N ерунду, которая выдаёт неверный ответ.

→ Ответить

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

Спасибо большое. Понял, почему у меня не зашло.

→ Ответить

denys.astanin

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

блин. а я так и не дописал динамику. жаль.

перебор как-то уже и руки не поднимаются писать.

→ Ответить

taras.klaskovsky

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

Дп f[i] -- стоимость набора маски i.

Из i пытаемся все остальные послать в разных коробках -- обновляем ответ, либо просто генерим маску из неиспользованнных элементов, чтобы их сумма была равна 1000(и обновляем f[i or mask])

→ Ответить

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

Надо было организовать перебор всех подмасок данной маски с выбором оптимальной суммы.

→ Ответить

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

Меня порадовала задача D. Что по ней надо было умного писать? Мне лень было думать, я написал тупой перебор, и он прошел.

→ Ответить

Tranvick

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

Жесть... Я написал ДП и оно на чем-то упало =/

→ Ответить

Kenny_HORROR

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

В D можна написать ДП по маскам и перебор всех подмасок данной маски итого O(3^n).

→ Ответить

Urbanowicz

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

А еще O(4^n) заходит (неэффективный перебор подмасок).

→ Ответить

SergeyLazarev

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

Можно и за O(2ⁿ)

→ Ответить

Kenny_HORROR

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

Ммм. Мне как-то не очевидно как (возможно просто после пары часов учебы голова на варит). Можешь пояснить как?

→ Ответить

SergeyLazarev

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

Ой, ошибся с оценкой=) Сложность моей реализации получилась 2ⁿ· k, где k - количество подмножеств с суммой 1000. В худшем случае даже больше, чем 3ⁿ получается...

→ Ответить

pascal

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

У меня за О(2^N + nlogn)

→ Ответить

-dp-	13 лет назад, # \| ← Rev. 2 → 0 В D проходит наинаглейший перебор на питоне. Делаем рекурсию от набора, в ней пытаемся вырезать всеми способами 1000 и вызваться дальше. Плюс мемоизация в виде словарика кортежей. → Ответить

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

А у меня наглейший перебор на питоне получил TL...

→ Ответить

-dp-	13 лет назад, # ^ \| 0 Тут, видимо, фокус в мемоизации, это ж, на самом деле, динамика получается уже. → Ответить

kasyankrak

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

Здравствуйте, я сегодня писал задачу C и в первой попытке я получил PE. Исправил - WA. Очень долго искал ошибку в идее, но ничего не нашёл, пока не наткнулся на то, что выводил int ":" int. (знаю глупо - )).

Так вот я бы хотел спросить, почему WA? если как я понимаю там просто был тест с часами или минутами <10 и т.о. вместо 2-х цифр получалась одна, а вместо второй - ":". Насколько я понимаю это эталонный случай PE.

Поправьте если я не прав - )

→ Ответить

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

А какой смысл этот вопрос задавать здесь? Спрашивайте у жюри контеста.

→ Ответить

kasyankrak

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

Эмм... А разве автор поста не входит в состав организаторов?

→ Ответить

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

Какая разница - входит или не входит? Вопросы жюри задаются другим способом. Ну если, конечно, вас интересует не ответ жюри, а ответ частного лица - то пожалуйста.

→ Ответить

-dp-	13 лет назад, # ^ \| 0 Вообще WA против PE это давний холиварчик. И это, по-моему, как раз случай когда допустимы оба варианта. Меня лично ничуть не смутило WA на той же ровно тупой ошибке =) → Ответить

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

PE это плохо) PE это WA)

→ Ответить

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

Тесты опубликованы, можно запустить своё решение и посмотреть, в чём была проблема.
http://russiancodecup.ru/tests/russiancodecup-2011-qual3-tests.zip

→ Ответить

kasyankrak

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

Я её сдал - )

→ Ответить

Pycz	13 лет назад, # ^ \| 0 А как запустить, разрешите поинтересоваться? Я что-то не понимаю. (простите мою глупость). Написал задачу просто, но отправить не успел, интересно узнать верность решения. → Ответить

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

Я имел в виду скачать тесты и запустить вручную, у себя на компьютере. Через их систему после окончания контеста не получится.

→ Ответить

Pycz	13 лет назад, # ^ \| 0 Это я понял. Но что запускать именно и как решение подавать в программу? В этом загвоздка. → Ответить

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

Я не очень понимаю, в чём проблема. Вы тестируете своё решение точно так же, как тестировали написанный код во время контеста, только на тестах жюри.

→ Ответить

Pycz	13 лет назад, # ^ \| 0 Ох, файлы текстовые в тестах, значит? Черт, не подумал. Спасибо! Думал, что нужно как-то выполнять исходные тексты, которые там прилагаются. Зачем-то. → Ответить

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

Исходные тексты из архива - это проверяющие программы (т.н. чекеры) и решения жюри. С решениями жюри, возможно, будет полезно ознакомиться.

→ Ответить

Pycz	13 лет назад, # ^ \| 0 А нельзя в чекер программу засунуть? → Ответить

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

Нет, нельзя. Чекеры просто проверяют файл, сгенерированный Вашей программой, на правильность.

→ Ответить

Pycz	13 лет назад, # ^ \| 0 То есть, получается, что автоматом проверить решение нельзя и придется вручную проверять каждый тест? Печально. → Ответить

dalex

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

← Rev. 2 →

=================================
На самом деле можно скачать какую-нибудь тестирующую систему

А еще можно встроить в свою программу нечто вроде:
for (int i = 1; i <= кол-во тестов; i++) {
    открываем файл "i";
    решаем задачу;
    запоминаем свой ответ;
    открываем файл "i.a";
    сравниваем свой ответ с ответом жюри;
}
(но это только если ответ единственный)

→ Ответить

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

-------------------------------
Да, в качестве примера такой тестирующей системы можно привести http://www.contester.ru/

→ Ответить

ant.ermilov

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

Есть вот такая клёвая штука чтобы тестить решения: http://acm.timus.ru/tester/

→ Ответить

Qulinxao

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

>>А какой смысл этот вопрос задавать здесь? Спрашивайте у жюри контеста.<<

:) пусть X - число тех что младше 18 и попал в 200 в 3 квале

истино ли X>3?

→ Ответить

Rasifiel

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

А какая разница?) Между квалом и онсайтом еще тур, так что не думаю, что будут какие-то репрессии до этого момента.

→ Ответить

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

Истинно. Я как минимум четверых нашел :)

→ Ответить

the_saint

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

Ты на 204 месте?

→ Ответить

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

← Rev. 3 →

Нет, он похоже на 200м сейчас.
Хотя странно. Я точно помню, что Kozlov Sergij закончил на 200м месте, сейчас он 199й.

UPD: Агафонов Александр скорее всего был 200м со штрафным временем 71. Сейчас он 196й.

→ Ответить

SergiiKo

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

Через мгновение после того как я вздохнул на 200м, уже был на 203, через пол часа уже 199 ))) наверное убивали читеров...

→ Ответить

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

Администраторы услашали ваши мольбы X)

→ Ответить

ytrewq

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

-62

все лохи.раунд уг.

→ Ответить

denys.astanin

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

+12

и не лень регатся ради такого камента? ) отсылал бы уже от родного ника )

→ Ответить

Ferlon

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

Не, ну тут зато видно: человек честно говорит, от души :)

→ Ответить

ytrewq

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

-77

особенно со 190 по 220 они вооще лошары ! эу задроты! вы неудачики, а я молодец!! и маечку мне только за это!!

→ Ответить