CodeChef invites you to participate in the July CookOff Challenge at http://www.codechef.com/COOK12
Time: 2130 hrs 24th July 2011 to 0000 hrs, 25th July 2011 (Indian Standard Time - +5:30 GMT)
Details: http://www.codechef.com/COOK12/
Registration: Just need to have a CodeChef user id to participate. New users please register here
Problem Setter: Shilp Gupta
It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.
Сортируем цены и скидки. Дальше ДП
DP[i][j]- ожидаемая скидка, если среди первых i предметов, мы купили j. Переход делается с учотом того что предмет попадает в множесто с нужных нам j предметов, среди і, c вероятностью j/i
Отсортируем обе последовательности. Понятно, что большие цены нужно брать с большей скидкой.
Рассмотрим отсортированный список всех чисел A и отсортированный список выбранных чисел B (общее количество различных списков B равно Total = С[n][k]). Посчитаем количество списков B, в которых i-е число списка A стоит на j-ом месте. Их количество равно Num = C[i][j] * C[n-i-1][k-j-1]. В ответ все такие ситуации добавляют A[i] * скидка[j] * (Num / Total).
Очевидно, что любая вещь у нас имеет равную вероятность быть выбраной k/n. Отсортируем наши вещи в порядке убывания стоимостей, аналогично поступим со скидками. Очевидно, что среди вещей которые мы берем выгоднее всего взять большую скидку на более дорогой предмет. Т.е. заведем динамику с помощью которой посчитаем для каждого предмета вероятность того что он будет i-ым по величине среди взятых предметов.
dp[i][j] - вероятность того что до этого было взято из i предметов j, p[i][j] - вероятность что i-ый предмет будет взят j-ым. Тогда очевидны следующие переходы:
dp[i][j] = dp[i-1][j]*(1-p[i-1][j])+ dp[i-1][j-1]*p[i-1][j-1].
А p[i][j] легко считается на основе dp[i][j]: p[i][j] = dp[i-1][j-1]*(число предметов которые надо взять)/(число оставшихся предметов).
Суть я думаю ясна (надеюсь в формулах не ошибся).
Last time I was the author.
This time I am the tester.
But I sure you that when I set the time limits I think that they are generous enough.
I have no aims for the contestants do some nasty optimizations.
I apologize for all inconviences.
Sometimes typos can tell us a lot ;) .
Из тех кто сдал задачу про медианы, какое у неё решение?
Я думал делать нечто в стиле переберем медиану множества, тогда знаем сколько левее, а сколько правее. Далее надо как-то быстро посчитать все возможные достижие суммы из необходимого числа элементов левее и правее (так и не придумал). Ну а далее используя два указателя легко ищем самую близкое к медиане среднее. Или у задачи другое решение?
Но вы в своем решение ходите по многим лишним суммам.
В момент просмотра первых i чисел нужны только суммы не большие суммы min(k/2,i) наибольших чисел из a[1], ..., a[i]. Это, конечно, не меняет асимптотику решения. но очень сильно уменьшает константу, раз в 6, наверно, при худших раскладах.
Хорошо хоть, ограничения указаны в условиях, в отличие от многих индусских контестов.
Кстати, а почему время у некоторых не-TL (в том числе и Accepted) решений показывается больше, чем TL, указанный в условии? Пример: (задача) (статус).
Тайм лимит на самом деле в 7 больше моего решения. На зимней школе Дима Жуков тоже давал задачу, где все дело было в константе. Просто когда разные решения имеют константу отличающуюся больше чем скажем в 10 раз, то это уже нельзя игнорировать.
Когда в 10 раз — да, легко отсечь, а вот когда в два (ну или во столько, во сколько TL должен быть больше времени жюри) — начинаются нежелательные спецэффекты.
Я был тестером этого контеста, и придумал тест, где валится обычный рюкзак (это было не просто). Поэтому все так мучались с этой задачей, думая, что можно затолкать обычный рюкзак.
А никто не пропихнул с обычным рюкзаком?
n=60, k=30..37
a[i] = (i<=30 ? i*i/3 : 1200-sqr(61-i)/3) + random_noise()
1 <= i <=60.
Я его вообще случайно придумал. До этого были тесты, где просто была обычная квадратичная зависимость, и они были в принципе ничего. Но этот их всех переплюнул.
Еще есть один
n=60, k=30..37
a[i] = (i<=25 ? 208-sqr(26-i)/3 : 1200-sqr(61-i)/3) + random_noise().
Тоже хороший.
Но возможно со степенями двойки тоже будет хороший, я не пробовал.
Просто эти тесты еще хороши тем, что там везде ответы ненулевые. Ведь очень хороший чит, отсекать как только нашли нулевой ответ. Но здесь это не поможет.
Нет никто. Все три прошедших решения где-то битмаски заюзали.
It is really nice of Anton to try and take all the blame on himself as he has a very deep sense of accountability towards the programming community. However, we do not believe that he is responsible in any way for the above glitches that you faced in the recent contests.
Let me admit that we at CodeChef are still learning the nuances of the short contest format. There have been issues which caused inconvenience to the community and we apologize to you all. We will certainly look into them and work towards resolving them. We hope to have you all there in the next contest. And please drop in a mail to feedback@codechef.com in case you feel we can do something to make things easier and better for you.