I think he just share the feelings with gray coders :)

He tried to draw a heart cardiogram.

He didn't drop to grey !?

just for fun = =

Actually this is not rare :D

http://codeforces.com/profile/sillycross

Thank you, Gerald!

I hope the problem setter will have explanation for the first example for problem A.

Don't worry it's unrated for you :)

And what about girls?

Oh, My eyes! :)

Он просто сдал её через минуту (и через две, кстати). Возможно, он написал её раньше, а сразу после того, как сдал С, нашёл баг в Е и её тоже сдал.

Ну и ещё есть шанс, что там полная фигня, написанная лишь для того, чтобы пройти претесты.

I can't understand russian version of problem's E statement, although Russian is my native language.

I couldn't understand the statement of E.

It's not only you. For problems A-D the english translations were alright. For problem E, WTF?? I still don't understand what the problem wants us to do.

The statement says there is guaranteed to be a solution for given m, k. Which means that a test with m=0, k=1 will not appear.

Отличительная черта ментальности украинцев — позитивность, общительность и жизнерадостность, поэтому у нас все комбинации неотрицательные:)

Maybe your program writes "0"

0 2

Ещё системного тестирования не было.

такие решения должны падать

Скорее будет странно, если у кого-то не зайдет за N * N * K * K (если, конечно, восклицание не относится к факториалу:) )

Рассмотрим массив P(n), i-й элемент которого — количество чисел с i единицами в двоичной записи на промежутке [n+1,2n]. Например, для n=9 P(n) = {1,4,3,1,0,0...}. Во-первых, при переходе от меньшего n к большему элементы массива P(n) не могут уменьшиться. Потому что при увеличении на n на 1 мы выбрасываем из рассматриваемого промежутка число n+1, но добавляем число 2*n+2, у которого такая же двоичная запись плюс нолик справа. Во-вторых, мы прибавляем к этому промежутку еще и число 2*n+1, которое и модифицирует массив P(n). Например для P(10) = {1,4,4,1,0...}, потому что число 19 имеет три единицы в двоичной записи, и оно увеличило третий элемент массива P(9) на 1.

Получается вот что: все четные числа приходят в рассматриваемый промежуток на смену своим половинам, и только нечетные реально модифицируют массив P(n), причем только один элемент и только на единицу. Поэтому если мы хотим найти число, в промежутке которого m чисел с k единицами в двоичной записи, нам достаточно найти нечетное число которое изменило k-ый элемент массива P(n) с m-1 на m. Иными словами, m-ое нечетное число, в двоичной записи которого k единиц. Если такое число с — ответ на задачу равен (c+1)/2.

Как именно это сделать, я подробно описывать не буду, потому что у меня какая-то переборная хрень.

Можно так: Научимся отвечать на вопрос: "Сколько чисел с k битами меньше или равны X" (пусть это f(n, k). Тогда для нашего некоторого n — количество чисел с k битами на интервале равно f(2 * n, k) — f(n, k) = Y. Заметим, что с ростом n Y возрастает. Сделаем бинарный поиск. Теперь, как считать f(n, k). Найдем старший бит в n. Пусть его позиция — p. Тогда к ответу прибавим С[p-1][k] (числа с k единицами у которых старший бит меньше p). Поставим одну из единиц на позицию p (вычтем из n эту старшую единицу) и рекурсивно продоржим.

I used Dynamic Programming

Compute the total number of ways to break number n into summands which are <= k. Let it be S. Then number of ways to break n into summands which are <= d-1. Let it be R, these ways to break the number are "bad" and should not be counted in the final answer. Thus, the final answer is S-R.

I do not believe you.

Interesting!

if s[i]=='4' then A[s[i]-'0'] is A[4]

scanf("%d %d %d %d\n",a+1,a+2,a+3,a+4);

Бинарный поиск + фенвик работает быстрее всех авторских решений укладывается примерно в 0.7-0.8 секунды. Сложность O(Qlog²(N)) кажется. Правда там еще сжатие координат было... Постараюсь побыстрее дописать в разборе.

I have solved it in O(N^2) using DP. I think it can't be solved faster. So, n could be somewhere around 2000.

Same here! Wasted 5 minutes and then solved C before realizing n is always 5.

48 here same as '0'. Read this http://www.asciitable.com/

As for your code, the behavior of X >> i is undefined when i = 64, for the behavior of op1 << op2 and op1 >> op2 is undefined if the op2 is negative, or greater than or equal to the length in bits of the op1. So, you can get AC in both MS C++ and GNU C++ by replacing X >> i with i < 64 ? X >> i : 0 for example.

the problem asked you to print the number of paths , how it can be negative ?

You can blame broken % operator in C++. But don't blame contest authors ;)

The subproblem can be formulated as this: You have an area of land, with h[i] being the height of the i-th section. You want to pour V liters of "rain" on this land (so that the water level is the same for each section that isn't dry). Find the resulting water level.

Now you have the initial heights, and a bunch of queries that either change the height of one section, or ask you to solve the subproblem for a given V.

Editorial

Try writing big random test generator and brute checker function, and test your solution with it.

It seems far more productive that brute forcing tests.

Changed 6676977

Всегда так.