Пару месяцев назад мы провели очередную межвузовскую командную олимпиаду. Тренировка по задачам этого контеста состоится в воскресенье, 7 июня, в 13.00 по Московскому времени.
Авторами задач данного соревнования являлись Sinner, dalex, Slamur, также неоценимую помощь в подготовке оказали craus, Shlakoblock и I_love_natalia.
Зайти в контест вы сможете на этой странице: Тренировки Codeforces
Список предыдущих наших контестов:
- 2012, Отборочный контест СГАУ на четвертьфинал ACM ICPC
- 2013, VI Самарская областная межвузовская олимпиада по программированию
- 2013, Отборочный контест СГАУ на четвертьфинал ACM ICPC
- 2014, VII Самарская областная межвузовская олимпиада по программированию
- 2014, Отборочный контест СГАУ на четвертьфинал ACM ICPC
Спойлер к одной из задач:
Баян с прошлогоднего NEERC.
Ну да, там дано куча чисел, разделенных пробелами и переводами строк, надо вывести максимум и минимум, тут и без условия все понятно.
Problem M. Minimum
(извиняюсь за некропостинг, тему всё равно до меня подняли)
I have some question(I am new in CF & it is my first GYM contest):
Sorry for my poor English. Thanks in advance.
It will be gym contest, so:
Reminder: the contest starts soon, the registration is opened.
It's 20 minutes before start. We begin at 13.00 MSK.
Final reminder, 5 minutes before start (13.00 MSK)
Что в B нужно было забыть, чтобы не пройти 7 тест?
У нас падало на тесте p=10, n=14, x=5. Ответ 4.
What is the idea for L ?
K + 1 rings can be moved in 2K + 1 turns:
So you can use next algo to move N rings:
F(N) = F(N — K — 1) + (2K + 1) + F(N — K — 1)
F(N) = 2F(N — K — 1) + (2K + 1)
If you enumerate groups of (K + 1) rings, this fotmula will be:
G(i) = 2G(i-1) + (2K + 1)
G(0) = if (M = N mod (K + 1)) == 0 then 0 else (2(M — 1) + 1)
It can be solved with matrix exponentation or even with deriving of formula.
Как F решать?
Фиксируем тройку участников, строим граф: три вершины соответствующие нашим участникам, из них в сток ребра пропускной способностью равной их производительности. Затем пробегаем по всем задачам и делим на типы, тип — это 3х битовая маска, соответствующая кто из наших участников способен решить эту задачу, из этих вершин проводим ребра в соответствующие вершины участников. Пускаем поток.
Можно понять, что выгодно делать так:
Если участник один может решить задачу, то пусть он её решает
Если задачу могут решить все трое, то рассмотрим такие в самом конце
Теперь есть граф-треугольник, идём по всем парам участников и смотрим: если другой человек в паре не сможет в одиночку добить все задачи на этом ребре, то помогаем ему
Просто идём по всем парам и решаем, что решается
Каждый решает задачи, которые могут решить все трое, пока может
А что с треугольником на сторонах которого написаны 2ки, а на вершинах 4,1,1. Если "помочь" какой-то из единичек добивать ребро смежное с 4кой, то ничего хорошего не выйдет? То есть 4ка должна взять оба ребра смежные с ней, а единички общими усилиями все ребро между ними.
Вроде всё нормально должно быть, мой код выдал 6: http://ideone.com/G2HgCg
Интересное решение по D:
для n = 1 или n = 2: FAIL.
для n != 4 и n != 6: значения от 1 до 3*n по порядку заполняем в массивы по следующему правилу:
1, 2, 3,2, 3, 1,3, 1, 2,1, 2, 3, ...для n = 4: полный перебор всех вариантов.
для n = 6: ответ на тест дан в условии к задаче.
Вообще это баян с кодчефа, но там была более общая задача — было не обязательно три кости
Насчет случая с 6 — обычное решение работает и для него. Поэтому частный случай только с четверкой.
Странно, я сколько пересчитывал на листочке, для 6 не работало... Видимо устал и посчитать до 19 сложнее, чем кажется.
Увидев число 19, могу предположить, что это 36 / 2 + 1, значит скорее всего вы проводили пересчет влоб. Можно проще — так как мы всё зациклил, то число в i позиции однозначно больше всех других чисел из других граней на позициях меньше i, а следовательно нужно пересчитывать только для соответствующих элементов кости. То есть для n=6 нужно проверить только 6 пар чисел, из которых по приведенной схеме 4 будут в нужном направлении, две нет. Все оставшиеся пары разбиваются поровну, а значит эта схема подходит под условие.
Я пробовал альтернативное решение по Д — будем делать random_shuffle(), пока все не станет классно :) Мне почему-то показалось, что там исходы более-менее независимы и вероятность попасть на правильное разбиение довольно высокая. На самом деле это совсем не так.
В запуске для 1000 работало 0.15, но на 13 тесте поймало ТЛ. Сейчас попробовал с другими сидами rand(), стало только хуже и падает раньше.
Пришлось докручивать конструктив.
Расскажи пожалуйста L. А то мы видимо не смогли за весь контест понять условие
Тест 9. (5, 1) — 13. Никакое наше понимание не дает ответа на вопрос, как это возможно
k дополнительных стержней позволяют перекладывать блоки из L ≤ k + 1 последовательных дисков за 2L - 1 шагов : переложим все диски из блока кроме последнего на доп. стержни за L - 1 шаг, последний диск из блока на нужное место за 1 шаг, поставим диски с доп. стержней обратно за L - 1 шаг.
Разбиваем так на блоки, самым маленьким блоком должен быть самый верхний, его перекладывали больше всего (остальные блоки будут по k + 1 дисков).
Есть три обычных стержня (A,B,C) и один маленький, на которое только одно кольцо влезает (D).
За 13 ходов можно сделать вот так (с A на C): A-D, A-C, A-B, C-B, D-B, A-D, A-C, D-C, B-D, B-A, B-C, A-C, D-C.
Рандом шаффл я с I_love_natalia таки упихнул с приличным запасом за день до контеста. Основная идея: меняем случайные элементы местами, пока разность между минимальной и максимальной суммами костей больше какой-либо константы, например, 10. После этого проверяем за линию эту перестановку и всё по новой.
Это уже умный шаффл :)
Как вообще ведет себя число подходящих разбиений c ростом N? Вероятность "угадать", выбирая вообще случайные разбиения — уменьшается пропорционально какому-то полиному от N? Эмпирическим путем у меня получилось, что вероятность уменьшается примерно пропорционально росту N, но все же медленее.
как решить задачу Е ?
я пробовал деревом отрезков в котором держу минимальный показатель, и минимальный индекс где он встречаеться. Для первых К человек просто раскидывал их в касы, ну а потом для каждого следующего человека обновлял минимальный показатель...
не знаю на сколько понятно обьяснил как я решал... и простите за ошибки)
UPDATE всё таки доделал с деревом отрезков... опять накосячил из тупости.... спасибо тем кто ответил)
делали ровно то, что написано в условии через очередь с приоритетами, полагаю сет тоже сгодился бы.
добавляем все кассы в сет. На каждом шаге достаем минимум, пересчитываем, кладем обратно.
I was asked to write quick one-line hints for all problems. They are in the first revision.
There are also some typos but it's difficult to edit and make another spoiler, so I'll leave it as is.
Anotyer way to solve B in the first revision.
Can you provide the explanation for M? I dint get what dalex wants to say here.
Thanks.
Detailed M (see 1st revision)
Where can I find the 1st revision you are talking about, please ?
Above a comment, there is an option saying <-- Rev x.(x is some positive integer)
Pressing that gets you to previous versions of the comment.
У меня такой вопрос, будет ли выложен где-нибудь разбор по задачам этого контеста?
Any hint on question K please??
Hints are in the comment above by dalex. Just go back to revision 1 of the comment to see the hint.
Я тут нашел какой-то разбор. :)
Can someone who has solved problem A post the 13th test-case here. I am getting WA and I can't figure out my mistake. Thanks. This is my code http://ideone.com/hPM1Ud Problem A
Не могу пройти 5 тест в B :((
5-ый тест по B: 8 31 14. Ответ — 4 нажатия.
Учтите, что оптимальными способами добраться до нужной клетки являются не только способ напрямую из стартовой клетки и способ с промежуточным посещением последней клетки.
Problem C can also be found in Algorithm Design by Kleinberg and Tardos (here)