Не нашел поста, посвященного сию мероприятию, поэтому начну его здесь.
В отличие от первых двух довольно стандартных задач, третья задача была реально интересной (по крайней мере, для любителей мат.статистики/эконометрики вроде меня). Интересно, как народ ее сдавал?
Я пробовал различные статистики для разделения перестановок, но лучшее что нашел — p[i]^3 * i, она дает точность распознавания примерно 85%, но, к сожалению, в этой задаче этого мало (нужно ~90%).
http://codeforces.com/blog/entry/11919
Thanks! Interestingly, I don't see it in "Recent actions".
C точностью распознавания 85% нужно в среднем 25 посылок чтобы сдать.
Да, но это же в среднем, а реально можно и с +50 не сдать. В любом случае, на раунде я решил, что слать до посинения — не лучшее расходование времени.
Вероятность не сдать с +50 — 12% :)
Да нет, понятно, что если бы цель была — просто сдать, то это как-нибудь можно было сделать. Например, я нашел 4-5 неплохих статистик, предсказывающих с вероятностью 70-85%, натравив на них SVM (благо, сидел в python с sklearn) явно что-нибудь приемлемое получилось бы.
Но у меня интерес был чисто научный — я подумал, вряд ли решение будет "возьмите 5 статистик с точностью 80%, натравите на них svm, получите точность 90+%", поэтому и искал статистику, которая дает искомую точность. Даже обидно, что попробовал кучу всякой хрени включая искривление линии кумулятивной суммы, и не попробовал количество элементов p[i] >/< i
Если подходить с научной точки зрения, naive bayes — первое что приходит в голову, разве нет?
Наверное, но не совам, вставшим в 5 часов утра после трех часов сна =) Меня не отпускала идея, что тут должно быть что-то простое и мощное, и я пытался ее найти.