Блог пользователя Aksenov239

Russian Code Cup QR 3
Автор Aksenov239, 15 лет назад, По-русски

Здравствуйте! Хочется Вам напомнить, что через некоторое время - в 17-00 15 мая (воскресенье;) состоится третий и последний квалификационный раунд "Russian Code Cup" в данном турнире. В данном раунде распределятся последние 200 мест в следующем раунде, а также 200 футболочек. Хотите футболочку? Всё зависит от Вас!

Good luck and have fun!

P.S.: Сайт - russiancodecup.ru. Там же Вы можете найти правила.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

А даже если и будут, то у футболок с онлайн-турниров есть плохая традиция - преодолевая почтой свой долгий путь, они теряются)

→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится
Функцию внеконкурсного участия так и не прикрутят?
→ Ответить
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Как закончиться - расскажите как сдать E, пожалуйста! Ведь там что-то сложнее "реализации", как я думаю. Или все таки ошибаюсь?
→ Ответить
  • 15 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

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

    Сначала будем считывать числа и распихивать их по очередям так:
     1. Берём очередное число
     2. Находим такую очередь с минимальным номером, что она либо пуста, либо последнее число меньше текущего.
     3. Если такая есть - вставляем элемент в неё, иначе выводим No
    Потом будет доставать минимальный из первых элементов очередей.
    Доказательство там вроде очевидное, но длинное
     
    → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      А ты сдал это решение? У меня большие сомнения, что оно будет работать правильно.У меня все то же самое, только в пункте 2 решения Scorpy  я нахожу такую очередь что у нее последний элемент меньше нашего, но максимальный из таких.
      → Ответить
  • 15 лет назад, скрыть # ^ |
    ← Rev. 4  
    Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

    → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Все. Понял. Моя реализация была немного не корректна
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите, как D нормально решалась, пожалуйста. Генерация всех подмножеств с суммой 1000, а затем нахождение максимального количества непересекающихся из них почему-то не прошли.
→ Ответить
  • 15 лет назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится +1 Проголосовать: не нравится

    Её можно было сделать динамическим программированием по подмножествам. Ставим подзадачу: какую минимальную сумму нужно потратить, чтобы отправить все предметы из подмножества i? Для каждой подзадачи перебираем подмножество j - предметы, отправленные последней бандеролью. Считаем стоимость этой последней бандероли и при необходимости обновляем ответ для текущей подзадачи. Здесь требовалось знание основных приёмов работы с множествами. Возможно, её можно сделать и попроще в смысле логики работы алгоритма, но это решение получается достаточно компактным и быстро пишется.
    → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Дп f[i] -- стоимость набора маски i.
    Из i пытаемся все остальные послать в разных коробках -- обновляем ответ, либо просто генерим маску из неиспользованнных элементов, чтобы их сумма была равна 1000(и обновляем f[i or mask])
    → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Надо было организовать перебор всех подмасок данной маски с выбором оптимальной суммы.
    → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Меня порадовала задача D. Что по ней надо было умного писать? Мне лень было думать, я написал тупой перебор, и он прошел.
→ Ответить
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

В D проходит наинаглейший перебор на питоне.
Делаем рекурсию от набора, в ней пытаемся вырезать всеми способами 1000 и вызваться дальше. Плюс мемоизация в виде словарика кортежей.
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
Здравствуйте, я сегодня писал задачу C и в первой попытке я получил PE. Исправил - WA. Очень долго искал ошибку в идее, но ничего не нашёл, пока не наткнулся на то, что выводил int ":" int. (знаю глупо - )).
Так вот я бы хотел спросить, почему WA? если как я понимаю там просто был тест с часами или минутами <10 и т.о. вместо 2-х цифр получалась одна, а вместо второй - ":". Насколько я понимаю это эталонный случай PE. 
Поправьте если я не прав - )
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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


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

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

→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится -62 Проголосовать: не нравится
все лохи.раунд уг.
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится -77 Проголосовать: не нравится
особенно со 190 по 220 они вооще лошары ! эу задроты! вы неудачики, а я молодец!! и маечку мне только за это!!
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится
Вдруг кто из организаторов увидит это сообщение. Очень хочется дорешивание, может проведете его на CF? =)
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Как посмотреть таблицу результатов одной страницей?
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится
Возник вопрос, а участникам, которым < 18  и которые прошли квалификацию, маечку высылать будут ? )
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится
Судебных приставов вышлют:)
Что-то это горячая тема очень)
→ Ответить