Просто слив. =(((((

Что сдала команда Итмо в B за 5 минут?

Как решать K?

И почему вот это решение падает: перебираем количество черных карт, которое мы могли вытянуть до того как вытянули последнюю красную, считаем вероятность вытянуть такое кол-во черных и кол-во способов их вытянуть вместе с красными, перемножаем, плюсуем к ответу.

Или иной вопрос: условие, что мы стараемся максимизировать выигрыш означает то, что мы не будем продолжать играть, когда красные карты закончатся, а не то, что мы будем продолжать играть, пока они есть?

J. Sort the edges. Binary search for the answer. Sliding window over the edges gives us a sequence of queries to add and remove edges; need to check if the graph ever becomes connected when executing the queries. This can be done using divide and conquer that uses DSU with rollbacks.

G: Final order of numbers will be equivalent to sorting an array of pair(digit_sum(i), i). Now instead if you iterate through sum of digits, you can find number of numbers  ≤  N and with given sum of digits using dp. For any given sum of digits at most one number can be in its correct place, which you can find by binary search.

Очень интересует решение F и B на div2?

Кто-то утолкал решение за O(M^2) в J?

Какая конструкция в H?

D и E из второго дивизиона?

E вроде уже где-то видел, не могу вспомнить где.

Кто как решал E (про прямые)?

На всякий случай, я пытался делать так (wa3 :)):

1) прямые параллельны <=> их направляющие сонаправлены <=> их векторное произведение 0. Тогда беру
P = (A + C) / 2 (любая середина отрезка между точками на разных прямых), Q = P + (B — A)

2) нахожу пару ближайших точек (одна точка на первой прямой, вторая на второй), тогда
P = (E + F) / 2, Q = P + ((D — C) + (B — A)) (потому что сумма векторов будет биссектрисой угла между ними)

Угол всегда 180 :)

where can i see the problems??

Here is a solution of problem D.

If k = 2^x, the answer is always yes (Obviously). Else if k = 2x-1 or k = 2x, then f(k), the minimal n for which the answer is yes, equals to 2x+1.

f(2*x-1) >= 2x+1. |> Lets consider the last step, on which number k was obtained. (a, b) -> (a-b, 2b). 2b can't be equal to 2x-1. Then a-b = 2x-1; a >= 2x; b >= 1; n >= a+b >= 2x+1 <|

f(2*x) >= 2x+1, x is not a power of 2. |> Let p be an odd prime divisor of x. Initially all numbers equal to 1, thus are not divisible by p. The following invariant takes place: there is always a number which is not divisible by p. Indeed, if (a, b) -> (a-b, 2b) and a-b and 2b are divisible by p, then a and b are divisible by p. That means, we can not obtain a situation where one number is equal to 2x, and all other numbers equal to 0. Therefore n >= 2x+1 <|

Now if n = 2x+1, how to obtain 2x and 2x-1? The trick is to divide all the substance in two parts of volumes a and b, one of which is a power of 2. Then repeat the action on the two tubes until we are done. Why this works? Let's concider an action (a, b) -> (a-b, 2b). Since a+b = n, (a-b, 2b) = (2a%n, 2b%n). Therefore after t steps (a, b) will turn into (2^t*a%n, 2^t*b%n). Since n is odd and one of (a, b) is a power of 2, after some steps, this number will turn into 1, and on the next step it will turn into 2. Then the other number will be n-1 and n-2.

The only thing left is to divide in two parts. Let 2^x be the biggest power of 2 which does not exceed n. First unite 2^x tubes into one. Then after y steps you have (n-2^x)/(2^y) rounded up pieces of volume 2^y and one piece containing all the remaining volume. On y-th step you divide pieces of volume 2^(y-1) into pairs and unite them. If one piece was left without pair, you append it with the remaining piece. After x steps you have one piece of volume 2^y and one more piece containing all the remaining substance.