What's up y'all.

These past few years I spend an odd week here and there making roguelike-adjacent games. Most of them are mediocre (maybe outright terrible), although I did have one title that had relative success.

Recently, I (re)released my most recent creation — Wizard Chess 2. It's a combination of an encounter-based roguelite (think Slay the Spire) and a tactical battle (think Heroes of Might and Magic). Now look, I know the visuals and UX are, ahem, lacking, but the game has a lot of complexity of the kind that you, fellow competitive programmers, might find appealing. So I thought to invite you to give it a try :)

An imaginary conversation with you:

-Eldar, your css skills are shit
-I know

-And your UX is terrible, I can't figure out what's going on
-Very true. That said, you can watch my shitty tutorial and read the in-game help menus for _some_ info

-What was that about $$$ prizes?
-I'm glad you asked! I'm giving away Amazon gift cards for certain achievements: https://itch.io/t/2392425/-prizes. I swear they are achievable.

-Wait, I have to record a video to prove my results? Don't you already have a high score server?
-Unfortunately, because this is a browser-based game, it's not hard to cheat it in various ways, so a full video of the run is the only cheater prevention I could think of.

-Hey I just got to the first bossfight and the music turned into some demonic howling, wtf?
-Oh I forgot to warn you that I'm a big metalhead, so almost every bossfight has a metal soundtrack. In fact, the idea of playing Septic Flesh's "Pyramid God" during a bossfight compelled me to make this game in the first place.

-Okay you're weird
-I know

If you do give the game try and have a question, or something nice or constructive to say, please drop a note here or in the game's discussion forums. Love y'all <3

Hello friends!

As I've recollected in a previous post, I am an old competitor who hadn't really participated since ~2014, and recently got a bout of nostalgia to return to Competitive Programming. So, I did a couple Topcoder SRMs, suffered through some SNWS rounds, participated in three regional 5hr competitions on three consecutive days, and dozed off at every Codeforces contest I tried to wake up for.

A lot of things are still the same as 8 years ago: tourist is still at the top, grey coders still ask for how many minutes to solve a problem before reading the editorial, Russian university teams continue winning ACM ICPC, and Snarknews never gives up on his alternate competition formats. But in this post, I want to focus on the new patterns that emerged since my last time around.

#1: Codeforces rounds timing

Did you know that there used to be a time when not ALL the freaking CF rounds were held at 5:35pm MSK? Back in the day, no matter what timezone you were in, there would be an occasional round you could compete in without having to interrupt your sleep (or your work).

I'm personally pretty salty because 5:35pm MSK is like 6:35am in my timezone, and my brain simply refuses to operate for 2 consecutive hours this early in the day. And while a quick check of Ratings shows that most users are congregated in between Moscow and Japan timezones, I do wish we had rounds in more varied time slots.

#2: Petr and Java

Did you know that Petr used to write all contests in Java? Imagine you were looking for an intelligible implementation of any contest problem. You would sail through the ocean of C++ submissions filled with FOR0(n) and #define int long longs, and spot the safe haven of Petr's delightful Java solutions that read like a page from Dostoyevsky's masterpieces. His variable names alone could teach you more about solving this problem than the editorial itself. In fact, I was under an impression that Petr did not use prewritten code, and created each of his beautiful algorithms from scratch every time.

Well folks, those days are gone. Checking Petr's recent submissions, I noticed that he turned to the dark side and the values in his Lang column for over 2 years now show... this:

#3: The AtCoder library and the Codeforces Catalog

There is another curious pattern in the submissions of some top contestants: namespace atcoder and a myriad of data structures and algorithms that magically pop out of this namespace, like a rabbit from a magician's top hat. The source of all this sorcery seem to be the AtCoder library. I mean, come on, red and nutella coders, can't you even write your own min-cost max-flow over a network generated by lazy propagation segment tree with 2-SAT FFT butterflies stored in each node? Meh!

More generally, I can see there is a whole catalog here on CF, with links to tons of educational materials. And, in all seriousness, that's awesome — there was but a fraction of this available back when I was a student!

#4: The new MOD to rule them all

A lot of programming contest problems request to find some value modulo a large prime. The most common reason for this is that we are counting the number of ways to do something, but this quantity is extremely large. By requesting the answer modulo a large prime, we keep the calculations in a datatype that fits into machine word, thereby letting the solver focus on the "interesting" part of the problem.

10 years ago, the most common moduli used in contest problems were 1,000,000,007 and 1,000,000,009. These are nice, easy to remember big primes whose sum fits into a signed 32-bit datatype, making them perfect for the scenario above. Or maybe they were not, because fast-forward to today, I saw like 10 different problems requesting the answer modulo...

998244353

I mean, seriously, what the fuck is this? This is one ugly-ass forgettable prime and you should be ashamed for using it in your problems!

P.S. I found Petr's blog post discussing the properties of this number. And it seems like the problem where it was introduced at the time actually relied on these properties, but not every problem does! Also, this post is from 2014 — are y'all telling me you've been using nine-nine-eight-two-four-four-three-five-three in contest problems since 2014!?

#5: Probabilities modulo MOD

One of my favorite topics in programming contests was always probabilities and expectations. You can just feel the blood coursing through your veins when your dynamic programming solution prints out a sexy 0.07574094401. But y'all had to ruin this as well by introducing... probabilities modulo a prime!? o_O

Most probability theory-related problems I've seen in the past months request the answer modulo, you guessed it, 998244353, and proceed to add a note explaining that the answer can be represented as p/q where q is not a multiple of the given modulo. So essentially now to solve any problem with probabilities you have to also throw in some number theory and probably even more combinatorics. And you can't even receive a 0.07574094401 as an answer!

Can anyone explain how this new fad started?

#6: Li-Chao Segment Trees

Saving the best for last! A couple weeks back, I was delightfully reading Um_nik's list of things he allegedly does not know, and it was heralded by a data structure called a Li-Chao Segment Tree. I initially thought that this was a joke, but a quick google search revealed that people write tutorials on this thing.

Then I told myself that surely nobody would bring a problem utilizing a Li-Chao Segment Tree on Codeforces, but the very next Codeforces round editorial made sure to prove me wrong by mentioning a Li-Chao tree (I didn't dig into details, but you get the point!).

Come on guys, was Heavy-Light Decomposition not an obscure enough data structure to bring to contests? Someone has to stop this madness!

Hello friends!

I hope a few of you might still remember me. This old dinosaur participated in very early rounds of Codeforces, and before that did Topcoder for a number of years. I've been away from competitive programming for several years now, but the recently started Advent of Code rekindled the spark, and I proceeded to open Topcoder arena and participate in the recent SRM.

To my utter befuddlement, there were less than 100 participants in Div 1 in this SRM — and looking through recent match history, it seems to be a fairly standard participation rate for a while now. For comparison, back in the good days Topcoder Div 1 routinely had several hundreds of coders.

I've got to admit that seeing this saddened me considerably — I have a ton of fond memories of competing at Topcoder, like rushing those 250-pointers, taking perpetually unsuccessful stabs at 1000-pointers, the violent heartbeat as I pressed the "Challenge" button every time, the nervous fidgeting in anticipation of System Tests that would reveal who stood tall, and who was bound to fall. I have a lot of nostalgia for those days..

So, I wanted to ask y'all — what happened to Topcoder? Did most old-timers stop competing, and the new generation just does not know about it? Did the website redesign hide the Arena applet so deep that you can't find it? Is the Arena just not user friendly enough, so everyone ran towards shinier platforms (wink wink)? Are the problems not as fun anymore?

Share your story — why did YOU stop competing? :)

Привет, Codeforces!

От лица компании Rocket Fuel Inc. я рад анонсировать соревнование по программированию "Rockethon", которое состоится на Codeforces. Контест подготовлен сотрудниками Rocket Fuel в составе Джон Дерриберри, Александр Рафф и я, Эльдар Богданов. Мы надеемся, что вы получите не меньше удовольствия от решения задач, чем мы от их подготовки. Лучшие участники получат призы и футболки. Кроме того, Rocket Fuel заинтересованы в рекрутинге сильнейших из вас, поэтому позвольте рассказать немного о нашей компании и почему надо у нас работать.

About Rocket Fuel

Rocket Fuel is building technology platform to do automatic targeting and optimization of ads across all channels — display, video, mobile and social. Our pitch to advertisers is very simple "If you can measure metrics of success of your campaign, we can optimize". We have run campaigns for many large advertisers. Examples include BMW, Pizza Hut, Brooks Running Shoes and many more!

We buy all our inventory through real time bidding on ad exchanges like Google and Yahoo. Ad exchanges are similar to stock exchanges except the commodity being traded is ad slots on web pages. Our serving systems currently process 40B requests/ day (~6X Google search volume), 700K requests/ second at peak with response time requirement of 100ms. Our data platform has several PBs data that is used for analytics as well as modeling.

Our engineering team is still small (~100) enough for any one person like yourself to make a huge impact. The team represents many top schools in US and outside — Stanford, CMU, MIT, Wisconsin-Madison, IIT (India), Tsinghua (China).

Rocket Fuel has been named #4 on Forbes Most Promising Companies in America List in 2013 and #1 Fastest Growing Company in North America on Deloitte’s 2013 Tech Fast 500.

In this post you will find the authors' solutions for the problems and subproblems featured in the competition, as well as some bonus questions related to these tasks.

391A - Генная инженерия

Note that we can consider each maximal sequence of identical characters independently, since there is no way to insert a character and affect more than one such sequence. Also, note that there are multiple ways to correct a single maximal sequence by inserting one character into it: we can either insert a different character somewhere in this sequence and divide it into two sequences of odd length (this is always possible for a sequence of even length), or even just add the same character in any point of this sequence, thus increasing its length by 1 and changing its parity.

Therefore, the answer to the problem is the number of maximal sequences of even length. One can find all such sequences in linear time. A pseudocode of the solution follows:

i = 1
ans = 0
while i <= length(s) do
  end = length(s) + 1  // we will use this value if current sequence is the last in this string
  for j = i + 1 .. length(s)
    if s[j] <> s[i] then
      end = j
      break
  // at this point, we have the next maximal sequence of identical characters between i and j-1, inclusive
  if (j - i) mod 2 = 0 then
    ans = ans + 1
  i = j

337A - Пазлы

В первую очередь, упорядочим числа f[i] по возрастанию. Теперь допустим, что самый маленький пазл, который приобретет учительница, состоит из f[k] фрагментов. Понятно, что в таком случае для минимизации разницы она должна приобрести наименьшие n пазлов, равных или превосходящих f[k] по размеру, то есть пазлы размеров f[k], f[k+1], ..., f[k+n-1] (это не совсем правильно, если среди f[i] встречаются повторяющиеся числа и выполняется f[k]=f[k-1], но такие случаи можно не рассматривать). Разница между наибольшим и наименьшим количествами фрагментов в таком наборе равняется f[k+n-1]-f[k].

Чтобы выбрать оптимальное f[k], переберем значение k от 1 до m-n и выберем наименьшую возможную разницу. Таким образом, весь алгоритм выглядит следующим образом:

read(n, m, f[1..m])
sort(f[1..m])
best = INFINITY
for k = 1 to m-n
  best = min(best, f[k+n-1] - f[k])
print best

Всем привет!

Через несколько часов (16 августа, 20:00MSK) начнется Codeforces Round #196.

Главным образом вам снова придется помогать Манао, задачи которого на этот раз варьируют от просмотра фильмов и участия в викторинах до древостроения и борьбы с нечистью.

Хочу поблагодарить за помощь в подготовке раунда координатора задач Gerald; Seyaua, который тестировал задачи; Delinur, которая переводила условия на английский язык; и Aksenov239, который вычитывал условия.

Разбалловка в обоих дивизионах будет стандартная.

Также добавлю, что я даже старше, чем Sammarize, поэтому перехватываю титул самого старого автора Codeforces-раунда до появления следующего претендента ;)

Контест окончен, я очень надеюсь что он вам понравился. Результаты: Див1, Див2. Мои поздравления лучшей пятерке первого дивизиона:

1. tourist
2. ilyakor
3. al13n
4. aa2985759
5. rng_58

Также поздавляю победителя второго дивизиона Ruthles!

Разбор задач можно найти здесь.

268A - Матчи

При ограничении в 30 команд самое простое решение заключается в симуляции всех поединков:

for i = 1 to N
  for j = 1 to N
    if i != j and h[i] = a[j] then
      ++ans

Существует также решение, работающее за O(N + M), где M — длина диапазона номеров цветов (то есть 100 при данных ограничениях). Для начала нужно посчитать для каждого цвета i количество команд cntH[i], у которых домашняя форма цвета i, и количество команд cntA[i] с выездной формой цвета i. Ответ задачи — сумма произведений этих количеств для каждого отдельного цвета, то есть сумма cntH[i] * cntA[i] по всем i.

268B - Кнопки

Для начала озвучим наихудший сценарий. Более-менее очевидно, что в худшем случае при угадывании i-ой (1 <= i <= n) по счёту кнопки Манао должен допустить n-i ошибок, потому что после этого становится понятно, какая кнопка правильная.

Посчитаем, сколько в сумме нажатий потребуется Манао прежде, чем он поймёт, какая именно последовательность кнопок правильная. При угадывании первой кнопки он допускает n-1 ошибку, но "цена ошибки", то есть на сколько кнопок нужно нажать чтобы её допустить, равна 1 нажатию. При угадывании второй кнопки цена ошибки уже 2 нажатия, потому что каждый раз приходится набирать первую (уже известную) кнопку. Продолжая в том же духе, получается что при угадывании i-ой по счёту кнопки Манао сделает (n-i) * i нажатий.

После того, как Манао понял правильную последовательность, ему остаётся её один раз ввести, что требует ещё n нажатий.

Отсюда получается алгоритм за O(n): просуммировать (n-i)*i для i=1, ..., n-1, и добавить к полученному числу n.

При значениях n, которые не выходят за диапазон 32-битных целых чисел, можно решать задачу и за O(1)*. Раскроем сумму (n-i)*i = n*i - i*i. Сумма первых слагаемых — это n*(1+...+n-1), где нам поможет сумма арифметической прогрессии. Сумма вторых слагаемых — это сумма квадратов от 1 до n-1, что вычисляется с помощью кубического полинома: http://pirate.shu.edu/~wachsmut/ira/infinity/answers/sm_sq_cb.html

*Единственная проблема — что ответ при больших n не умещается даже в 64-битный целый тип данных, но можно например вычислять его остаток при делении на что-нибудь.

268C - Красивые множества точек

Очевидно, что когда в множестве есть некоторая точка (x', y'), в нём не может быть никакой другой точки с x=x' или y=y', потому что тогда между этими двумя точками обязательно было бы целое расстояние. Есть всего n+1 различных x-координат и m+1 различных y-координат. Соответственно, размер искомого множества не может превосходить min(n, m) + 1.

Без условия x+y>0 нам бы подошло множество из точек (i, i) (0 <= i <= min(n, m)). Расстояние между точками (i, i) и (j, j) равно |i-j|*sqrt(2) и может быть целым только при i=j. С другой стороны, таких точек min(n, m) + 1, а мы уже знаем, что больше взять невозможно.

Раз точку (0, 0) использовать нельзя, сменим "диагональ": будем использовать точки (i, min(n, m) - i).

268D - Шведская стенка

Те, кто хорошо знаком с динамическим программированием, могут скроллить сразу вниз до "Итогового решения". Те, у кого есть некоторый опыт в этой теме, могут почитать мою попытку объяснить, как дойти до итогового решения. У кого опыта нету, тем наверное большого смысла это читать нету :)

Представим себе решение, которое перебирает все возможные дизайны, постепенно добавляя ступеньки снизу вверх. Например, допустим что оно уже выбрало направления для первых 10 ступенек и они вот такие: 2123412413 (то есть первая палка торчит в направлении 2, вторая — в направлении 1 и так далее). Теперь есть четыре варианта продолжить эту последовательность, приписав к ней '1', '2', '3' или '4'. Для каждой из 4^n стенок-строк нам нужно проверить, что для хотя бы одного символа выполняется следующее условие: первое его вхождение в строку не дальше позиции h, каждое следующее отстоит от предыдущего не более чем на h позиций, а последнее далее позиции n-h.

Естественно, такое решение при больших значениях n за разумное время не работает, но от него можно оттолкнуться в поисках лучшего подхода. Заметим, что проверку строки можно делать при добавлении каждого нового символа: если оказалось, что где-то посередине строки для всех четырех символов нужные условия уже не выполняются, то не имеет смысла перебирать её до конца. Также заметим, что нам не нужна вся строка для того, чтобы проверять при добавлении символа выполнение условий. Достаточно лишь знать, когда в последний раз встретился каждый из символов '1', '2', '3' и '4', и выполнялись ли для них условия до сих пор. Но тогда получается, что два префикса, у которых [каждый из символов в последний раз встретился на одних и тех же позициях] и [для каждого из символов выполнение/невыполнение условий совпадает], абсолютно эквивалентны с точки зрения дальнейшей работы такого перебора. То есть например при h=4 следующие два префикса можно окончить (то есть дополнить их до любой длины n) равным количеством способов:

44123424132
12424224132

Последний раз каждый из символов встретился на одной и той же позиции, символы '1' и '3' для обеих строк уже "потеряны", то есть условия для них уже не выполняются, а символы '2' и '4' ещё могут обратить строку в удовлетворительную.

На основе сделанных наблюдений уже можно построить полиномиальный алгоритм, основанный на принципе динамического программирования. Пусть ways[curN][i][j][k][l][ii][jj][kk][ll] будет количеством дизайнов стенки, в которых есть curN штук ступенек, последняя ступенька, торчащая в направлении 1, была на высоте i, в направлении 2 — на высоте j и так далее; ii, jj, kk, ll — boolean переменные, обозначающие, выполняются ли до сих пор условия для ступенек в соответствующих направлениях. Направив ступеньку на высоте curN+1 в одном из направлений, мы получим дизайн с curN+1 ступеньками, где эта последняя ступенька будет на высоте curN+1, а другие останутся на своих местах. Выполнение условий тоже можно и нужно пересчитать. Учитывая, что curN всегда равен одному из {i, j, k, l}, можно получить алгоритм со сложностью O(n^4). Так как это слишком медленно, подробно его разбирать не стану.

Сделаем следующее наблюдение: если мы сейчас рассматриваем палку на высоте curN, а последняя палка в некотором направлении была раньше чем curN-h палок назад, то нас не интересует, на какой конкретно высоте она была — это направление уже непригодно. Получается, что количество состояний в нашем алгоритме можно сделать порядка O(n*h^3). Более того, параметры, отвечающие за выполнение условий в каждом из направлений, коррелируют с высотами последних ступенек в этих направлениях, так что при желании от них можно (почти) избавиться, уменьшая количество состояний ещё в несколько раз.

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

Итоговое решение

Как ни странно, давайте заведём пятимерную динамику :) Пусть ways[curN][alive][last1][last2][last3] будет количеством таких дизайнов, где:

• Ровно curN ступенек

• Если то направление, в котором торчит последняя ступенька, всё ещё "живое", то alive = 1, в противном случае 0. Живое направление — это в котором первая ступенька была не выше h, а каждая следующая была не больше чем на h над предыдущей.

• last1, last2 и last3 содержат информацию об остальных трех направлениях. Направления никак не пронумерованы. lasti = 0 в двух случаях: если в соответствующем направлении ступенек не было вообще, или если последняя была более чем h ступенек назад. В остальных случаях в lasti записано, сколько ступенек назад была ступенька в этом направлении, то есть разница между curN и высотой последней ступеньки в данном направлении.

В целях оптимизации можно иметь last1<=last2<=last3, что уменьшает количество состояний примерно в 6 раз. Тем не менее, это усложняет код и в этой конкретной задаче особого выигрыша не давало (потому что обработка переходов стала более долгой). Переходы я буду рассматривать без учета данной оптимизации.

Теперь рассмотрим обработку переходов из конкретного [curN][alive][last1][last2][last3]. Обрабатывать состояния мы будем в порядке от curN = 1 до curN = n-1. ways[1][1][0][0][0] (то есть поставлена лишь первая ступенька) положим равным четырем, как базисный случай. Так вот:

• Если следующей мы ставим ступеньку в том же направлении, что и последняя (та, что на высоте curN), то мы грубо говоря получаем состояние [curN+1][alive][last1+1][last2+1][last3+1]: curN увеличилось на 1; направление, в котором поставили последнюю ступеньку, если было "живое", то определенно так и осталось и не могло "ожить" если не было; все lasti увеличились на один. Тут надо уточнить, что если lasti было равно 0, то его увеличивать нельзя (этой ступеньки или не была, или была но слишком давно). Также надо уточнить, что при lasti=h-1 оно превращается в 0 (последняя ступенька уже слишком низко).

• Если следующей мы ставим ступеньку в направлении, где последней была ступенька на высоте last1, то получаем состояние [curN+1][last1 > 0 || curN < h][alive][last2+1][last3+1]. Расшифровка: если last1>0, тогда это направление "живое". Также last1 может быть 0, но количество имеющихся ступенек быть меньше h — тогда это может быть лишь первой ступенькой и поставив её, мы будем иметь "живое" направление. На месте направления, за которое отвечал параметр last1, теперь то, в котором смотрела последняя ступенька. Соответственно, она была 1 ступеньку назад и надо написать там [1]. Но возможно, что это направление уже было мертвое и тогда надо написать [0]. Получается, что оно совпадает со старым значением alive. last2 и last3 меняются как и в прошлом пункте.

• Направления last2 и last3 обрабатываюся аналогично направлению last1.

Когда мы переходим по переходу этой динамики, новому состоянию добавляется количество вариантов, которым получалось старое. Итоговый ответ — сумма по всем [n][1][a][b][c], где 0<=a,b,c<h, плюс сумма по всем [n][0][a][b][c], где хотя бы одно из a, b, c ненулевое. Таким образом, у нас есть алгоритм со сложностью O(n*h^3), которому нужно асимпотически столько же памяти. Если его неаккуратно реализовывать (особенно на Java), то он словит ML. Лечится это дело несложно: так как для вычисления значений [i][][][][] нужны лишь значения [i-1][][][][], можно в любой конкретный момент запоминать лишь O(h^3) состояний.

Да уж, до написания разбора она мне такой громоздкой не казалась :)

Можете посмотреть решение пользователя SteamTurbine: 3027309, там довольно компактная реализация похожей идеи.

268E - Плейлист

Для начала давайте найдём ответ для фиксированной последовательности песен. Рассмотрим любые две песни, которые стоят в плейлисте на местах i и j, i < j. Если Манао понравилась песня i и не понравилась j, то произойдёт повторное прослушивание песни i. Соответственно, длина процесса с вероятностью p[i]*(1-p[j]) увеличится на L[i]. Сумма L[i]*p[i]*(1-p[j]) по всем парам (плюс сумма всех длин песен, потому что Манао их один раз послушает точно) и есть мат. ожидание для фиксированного порядка.

Получается, что из двух песен (l1, p1) и (l2, p2) следует поставить раньше первую, если l1*p1*(1-p2)>l2*p2*(1-p1), и вторую в противном случае. Если у нас всего две песни, то это очевидно. Если у нас есть ещё песни, то можно сказать — а вдруг, несмотря на то что это неравенство выполняется, есть ещё третья песня (l3, p3), для которой с первой песней неравенство определит, что надо её ставить до этой первой, а для второй — что после второй? Тогда было бы непонятно, какой из порядков даёт максимальное мат.ожидание. Посмотрим на этот случай пристально:

l1*p1*(1-p2)>l2*p2*(1-p1)
l1*p1*(1-p3)<l3*p3*(1-p1)
l2*p2*(1-p3)>l3*p3*(1-p2)
<=>
l1*p1/(1-p1)>l2*p2/(1-p2)
l1*p1/(1-p1)<l3*p3/(1-p3)
l2*p2/(1-p2)>l3*p3/(1-p3)

(Тут я закрыл глаза на факт, что p[i] могут быть равны 0 или 1, но это не важно)

Что за фигня, у нас противоречие! Видимо таких случаев не бывает :)

Далее, рассмотрим некоторый порядок песен (l[1], p[1]), ..., (l[n], p[n]), где существует пара соседних песен i и i+1, для которых не выполняется l[i] * p[i] * (1 - p[i + 1]) >= l[i + 1] * p[i + 1] * (1 - p[i]), и допустим, что этот порядок оптимален. Очевидно, что при замене местами песни i и i+1, ответ изменится на ту величину, которую в него вносила именно эта пара песен (имеется в виду величина l[i] * p[i] * (1 - p[i + 1])). Все остальные песни остались относительно каждой из песен i и i+1 в том же порядке. Но мы имеем l[i] * p[i] * (1 - p[i + 1]) < l[i + 1] * p[i + 1] * (1 - p[i]), значит, поставив песню i+1 перед песней i, мы получим большую величину. Таким образом, получаем противоречие — изначальный порядок был неоптимален.

Получается, что надо всего лишь упорядочить песни по убыванию l[i]*p[i]/(1-p[i]) для достижения перестановки с максимальным мат.ожиданием. Осталась проблема вычисления ответа для конкретной перестановки: до сих пор мы это умели делать только за квадрат, что при n=50000 многовато. Тут можно использовать идею, которая наверное тоже в какой-то мере является примером динамического программирования. Допустим, мы зафиксировали j и считаем, сколько песня j добавляет к ответу, если Манао она не понравится. Это величина (l1*p1 + l2*p2 + ... + l[j-1]*p[j-1]). Для j+1 аналогичная величина будет иметь вид (l1*p1+...+l[j-1]*p[j-1]+l[j]*p[j]). Раз эти величины отличаются на 1 слагаемое, можно их пересчитывать за O(1), если рассматривать j один за другим по возрастанию. Идею вычисления ответа для фиксированной перестановки можно выразить вот так:

lovedLenExp = 0.
answerExp = 0.
for j = 1 to N
  answerExp += l[j]
  answerExp += lovedLenExp * (1 - p[j])
  lovedLenExp += l[j] * p[j]

Вот в принципе и всё :)

Всем привет!

Через несколько часов начнется Codeforces Round #164 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса.

Главным героем в задачах будет Манао, немало лет напрягавший умы грузинских участников. Добраться до страничек Codeforces ему помогли Gerald, помогавший мне в подготовке раунда, и Delinur, которая перевела условия на английский, за что им отдельное спасибо. Также задачи тестировали Seyaua, sdya и Aksenov239.

Распределение баллов по задачам немного нестандартное: 500-1000-1500-2500-2500.

Удачи :)

UPD: Соревнование завершено, поздравляем победителей:

1. first_love

2. dianbei_10

3. yefllower

4. dpij

5. cenbo

Разбор задач можно найти здесь.