You are right

Im sure he needs your +1 while he has +248

İt is.

Макс, ты пока синий. Основной челлендж для тебя — вернуться в див1.

Keep on hoping

I'm sorry if what I wrote has disturbed you.

why minus?

Я некоторое время назад понял, что вводить общих персонажей или сеттинг для задач не очень хорошо. Потому что, как правило, некоторые задачи приходится подгонять под сеттинг, а это не всегда можно сделать. Так что никаких главных героев. Как задачу придумал — так на контест ее и дал.

Это первый контест с полностью моими задачами. Прошлые мои раунды я вместе с ACM-тиммейтами делал.

Fixed

Good Luck & Have Fun my friends :)

Wishing you successful Challenges , and Accepteds :) pardon the wordplay.

it's like centuries, 301 year belongs to 4 century. Century is 100 years

Maybe the author counts the non-regular rounds as well

e.g. ZeptoLab Code Rush, Rockethon, etc.

and in which hundred the first round is? and 101st?

Баг с временем

So what should we do?

присоединяюсь)

2 2
..
X.
2 1
1 1

Tricky case for C:

2 2
..
X.
2 1
1 1

There were lot of possible mistakes in B, it seems that most common of them is not checking that median of final array is large enough:

9 8 10 90 2
1 1 1 1 1 1 1 1

Dynamic programming, by stepnumber/cur_r/cur_s. cur_p each time can be calculated from other values.

Consider the dp[i][j][k], which denotes probability of having i rocks, j scissors and k papers remaining.

From this we can calculate,

dp[i-1][j][k] = dp[i][j][k] * ((i*k)/(i*j + j*k + k*i));

dp[i][j-1][k] = dp[i][j][k] * ((i*j)/(i*j + j*k + k*i));

dp[i][j][k-1] = dp[i][j][k] * ((j*k)/(i*j + j*k + k*i));

where i*j + j*k * k*i is the total number of ways to choose two different species, and each term from this sum denotes the number of ways to choose (r,s), (s,p) and (r,p)

The simply sum over, all dp[i][0][0] for all i = 1 to r for rocks, all dp[0][i][0] for scissors all i = 1 to s for scissors all dp[0][0][i] for paper for all i = 1 to p for papers

I calculated number of inversions in modified elements separately. Then for each modified element you calculate how many elements to the left of it are larger it, minus number of modified elements in the same interval plus similar thing for the right side. To calculate number of modified elements in range I used binary search on array of modified positions.

O(1) for iterators of vector.

O(1) because they are random access iterators. In sets, it is O(N).

I wish you luck anus <3 or uranus <3 or whatever is your name <3

(xo dezle var boshyo)

I think it's a greedy problem, you must practice a lot of greedy problems to be able to solve it pretty fast :D

Solved A, spent 20 mins on B, solved C in like 10 mins, read D realised it was dp so meh... read E realised it was bit with some normalization and map usage so I went back to B and after anthoner 20 mins I finally solved it . Hope you feel better.

It does not count when you are participating unofficially:)

Eh, I solved all with 1:47 but B failed systest :/

why did you Added ((r / total) * (p / (total — 1)) ?

I don't really understand your probabilities. I think it should be

r * p /(rp + rs + sp) for the first case and similar for others. (maybe its equivalent)

And note that you shouldn't divide integer by integer if you do. Cast to double one of them first

Давайте разделим последовательность на две группы:
1. U — Те позиций a[x] = x
2. C — Те позиций a[x] != x

Теперь есть три случая (a[i] < a[j] && j < i).
Т.е когда мы находим инверсий, мы фиксируем две позиций:
1. CC (a[j] != j, a[i] != i)
2. UC (a[j] = j, a[i] != i)
3. CU (a[j] != j, a[i] = i)

Все C можно запихать в массив (найти их можно map'ом).
Сумма всех CC — кол-во инверсий в нашем массиве.
А для нахождения UC или CU перебираем C а U можно найти бинпоиском. Для этого надо реализовать функцию calcU(l, r) — количество позиций a[i] == i (l <= i <= r). calcU(l, r) = r — l + 1 — calcC(l, r). calcC(l, r) — количество позиций a[i] != i. (если у нас есть все позиций в массиве all, то calcC(l, r) = upper_bound(r) — lower_bound(l)).

Oh, niyaznigmatul get Accepted all 5 problems with 33 minutes.

33 minutes > 30 minutes (failed challenge)