Автор awoo, история, 5 лет назад, По-русски

Привет, Codeforces!

В Dec/19/2019 17:35 (Moscow time) состоится Educational Codeforces Round 78 (Rated for Div. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Так же от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Codeforces and Harbour.Space

Привет Codeforces!

Истекают последние дни для подачи заявки на нашу стипендию магистра в Бангкоке!

Не упустите свой шанс и подайте заявку на участие в наших прогрессивных магистерских программах в области Data Science и Cyber Security всего за 3 шага:

1. Отправьте свое резюме, чтобы узнать, являетесь ли вы кандидатом на получение стипендии.
2. Если ваш профиль соответствует требованиям, один из наших сотрудников свяжется с вами.
3. Подайте заявку на программу, заплатите 125€ за заявку, пройдите серию интервью, и, если вы приняты, пакуйте чемоданы в Бангкок!

И, если вы знаете кого-то, кто может быть заинтересован в Digital Marketing, High Tech Entrepreneurship, Interaction Design или FinTech, поделитесь с ними информацией о нашей стипендии!

Больше информации→

Кроме того, не забудьте прочитать наши последние блоги!

Поздравляем победителей:

Место Участник Задач решено Штраф
1 HIR180 6 106
2 neal 6 162
3 receed 6 172
4 Geothermal 6 174
5 cerberus97 6 179

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 Akulyat 24
2 hoke_t 20
3 dhxh 18:-1
4 vovanstrr 14
5 WNG 13:-1
Было сделано 255 успешных и 458 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
A Dalgerok 0:01
B neal 0:04
C HIR180 0:08
D Tutis 0:17
E gxnncrx1993 0:20
F jqdai0815 0:07

UPD: Разбор опубликован

  • Проголосовать: нравится
  • +129
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +124 Проголосовать: не нравится

![ ](meme)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Best of luck to all those participating!!! Can't wait to see what problems there will be!!!

»
5 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

time to go blue.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why educational rounds has more greedy problems?

»
5 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Why educational rounds have more greedy problems?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Deleted

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -20 Проголосовать: не нравится

Clashes with Mirror replay round of ICPC Gwalior regionals on Codechef

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -20 Проголосовать: не нравится

    If you have to do something else, just don't do the contest here instead of whining about it in the comments. There's no contest time that can satisfy everyone in every time zone.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Would have considered that helpful, if u had replied before the contests started rather than now. Anyways peace out!

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

anyone please provide any good resource(book,blog,lecture) for understanding lazy-propagation i am unable to understand that.

»
5 лет назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

Who want to see my screencast(without comments)? Not sure I'm as cool as Um_nik tbh.

»
5 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Ставь минус раунду, если считаешь, что либо нужно ставить нормальный ML, либо не давать такие тесты как 72 задачи D.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -12 Проголосовать: не нравится

    Хотя там Е гениально связана с Д, поэтому можно и плюс поставить...

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    А в чем проблема 72 теста? Да, он находится далеко для первого теста покрывающего базовый случай, но с этим можно смириться.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

я сделал перепосылку по задаче Б, но штраф не обновился ? это фишка educational раундов или я что-то не шарю?

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Штраф прибавляется только, если первая успешная попытка провалилась на системном тесте, но вторая попытка прошла тесты.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      а какое решение потом будут взламывать ? какое будет проходить системные тесты? и что если первое решение сфейлится

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Solve D — Rejudge WA 72 — Find that in your solution there can be cycle but it outputs a tree — Write a dfs checker — Forget to call dfs function to get 3 more WAs. LOL... Anyway D and E are easier this time(Assuming they passes or does not get hacked).

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can D solved something like interval handling using set?

»
5 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

For problem B, who solved using https://oeis.org/A140358

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The link describes it as "Smallest positive integer k such that n = +-1+-2+-...+-k for some choice of +'s and -'s." What's the relation between this and problem B ?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Find the absolute difference of a and b. Then when we add number to the smaller of a and b, we're just reducing the absolute difference by that number. Otherwise we're increasing it. The problem becomes: Find the smallest positive integer k such that the absolute difference = +-1+-2+-...+-k for some choice of +'s and -'s. Effectively the problem is solved using the link above.

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

WHAT IS TEST CASE 2 OF DIV2B

»
5 лет назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

Screencast if anyone's interested: https://youtu.be/g4Gcl0yAgDU

»
5 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

How to solve D? P.s. round was great, so interestring problems!

»
5 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

What was pretest 2 of B?

I was first adding maximum possible n*(n + 1) /2 to the smallest number. Than answer = n + (difference between numbers) * 2;

whats wrong in this approach?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do you guys solved C? I thought of a greedy approach but it didn't worked :(.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    using 2 prefix sum arrays and then using maps

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Let us suppose you eat s1 strawberries and b1 blueberries in the left and s2 strawberries and b2 blueberries to the right. If total strawberries is s and b, then we want s — (s1 + s2) = b — (b1 + b2). Or, equivalently, (s — b) — (s1 — b1) = (s2 — b2). So, for given s1 and b1, you need search for minimum steps in the right to make difference equal to the above. You can maintain hashtable to store for every (s2 — b2) the minimum steps to reach it in the right. This will speed up the search...Complexity O(nlogn)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    What is wrong in the greedy approach?

    Cant I just eat up the jar which is closest to me?

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

    I reversed the problem; find the maximum possible of jars remaining such that the two types are equal in number. It is easy to see that such jars must form a prefix and a suffix of the given array.

    I thus separate the array into two halves ($$$A$$$ and $$$B$$$) and reverse the second half. I also treat strawberry as $$$+1$$$ and blueberry as $$$-1$$$. I then iterate through $$$A$$$ collecting prefix sums and storing it in a map (be sure to set $$$M[0] := 0$$$ before), thus for each prefix sum I now know the biggest prefix of $$$A$$$ with that sum.

    I then do similarly with $$$B$$$, except this time I treat strawberry as $$$-1$$$ and blueberry as $$$+1$$$, and I look up the prefix sums in the map. If the match exists, I add the two lengths and keep the biggest candidate seen. Finally, I restore the original answer by subtracting the maximum remainder from $$$2n$$$.

    Sample: 67283206

»
5 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

Eh, got stuck on E this time, had several approaches that worked on paper but didn't know how to translate them into code. So, how to solve E? :)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    Suppose you can build answer for any subtree of the current tree. Answer for subtree is a list of segments. We will say that the last segment in this list is the root.

    Then you have a tree, you built answers for every children.
    If there are no children, you can return a single segment {0,1}.
    Otherwise you do something that is drawn on the picture. Real segments mean a last (root) segment and the area near it means other segments in this subtree.
    a, b, c are children of d and a', b', c', d' are other segments in that subtrees. In this picture we build a tree d.
    You can see that there are no intersections between the children, but all the children root's are intersected with d.

    If you take the biggest (by count of segments in it) child as a base, you can add other children to this child and in total it will take nlogn time.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      Seems that O(N) is possible too:

      1. Encode single idx-th segment as a (linked) list of 2 events: (idx, 1) and (idx, 0) (1 — segment opens, 0 — segment closes). '+' will denote two linked list concatenation (done in O(1)). (N segments are represented as linked list of length 2*N)
      2. Root given tree at some node, say 1.
      3. Answer for subtree rooted at root_idx will always start with (root_idx, 1).
      4. Answer for leaf: solve(leaf_idx) = [(leaf_idx, 1), (leaf_idx, 0)]
      5. Answer for non-leaf: suppose we calculate answer for node d with children a, b, c. Denote solve(a)=[(a, 1)]+otherA, solve(b)=[(b,1)]+otherB, solve(c)=[(c, 1)]+otherC. Then solve(d)=[(d, 1), (a, 1), (b,1), (c, 1), (d, 0)] + otherC + otherB + otherA
      6. Restore l_i, r_i by traversing solve(1)
      7. Overall complexity: O(N)
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        Wow, that's nice. The idea is almost the same as mine one, but works much faster.

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Anyone solve C using binary search???

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I tried with binary search but i got Wrong answer on test 2

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Actually I managed to do that, you just need to build prefix differences (num2 — num1) & suffix differences, then sort the suffix ones and find a pair where suffix difference = -prefix difference using binary search.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you please explain the process in detail ?

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        The idea is as follows: 1. For all prefixes of the array containing from 0 to n elements inclusive we compute the difference between #of 1-s and 2-s (doesn't matter in which order). Going from the smaller to bigger ones, this is done in linear time. 2. Do the same thing for all suffixes from size 0 to n inclusive. Store the difference together with the size of the suffix 3. Sort the suffix differences from smaller difference to larger (if the differences match, put the one where the the length is bigger first) 4. For each of the prefixes, do a binary search in the sorted suffix differences array. We search for -prefix_differences[]. From all the suffixes with matching difference, select the largest (remember that due to our comparator being clever this requires almost no modifications). 5. Out of all the pairs select the one where 2 * n — prefix_length — suffix_length is smallest. This is the answer.

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve B?

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    1. Get the absolute difference.
    2. Keep increasing the sum and count from 1.
    3. If the sum equals the difference print the count. else keep adding to sum till both diff and sum are odd or even.
    4. Print count
    5. Try in cpp and try to decode the logic.
    6. Thank me later! ;) T.c O(1e5)
  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

    My answer for B. A and B

    Let the numbers be $$$a$$$ and $$$b$$$. After the operations, we end up with another number that is $$$c$$$ where $$$c\ge \max(a, b)$$$. Now the operations are adding $$$1, 2, 3 ...$$$ so after $$$n$$$ operations we have $$$\frac{n\cdot(n+1)}{2}$$$ as total increment in $$$a$$$ and $$$b$$$, distributed among them in some way.

    Now this total increment is also equal to $$$c-a + c-b = 2\cdot c -a-b$$$. Thus we have $$$\frac{n\cdot(n+1)}{2} = 2\cdot c-a-b$$$. Increment can also be written as $$$ |a-b|+2(c - \max(a,b))$$$.

    From here we get the two required conditions. We loop over $$$n$$$ to get first $$$n$$$ that satisfies:

    1. $$$\frac{n(n+1)}{2} \ge |a-b|$$$

    2. $$$\frac{n(n+1)}{2} - |a-b|$$$ should be divisible by $$$2$$$

    Now since we need increment $$$\frac{n(n+1)}{2} \ge \max(a,b)$$$ so at the max $$$n^2 = 10^9$$$, so the time complexity is $$$\sqrt{\max(a, b)}$$$.

    My submission: 67218512

    Btw I was watching William Lin's screencast, I have no idea what he has done. People have done it very quickly!

    EDIT: Just realised, no need to loop over so many values, since we know $$$\frac{n(n+1)}{2} \ge \max(a, b)$$$. Thanks to @aniervs. That will give constant complexity..

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      dude thanx from bottom of heart here i made only small change in your logic to keep it simple and it works like 1. total increment = n*(n+1)/2 2.suppose number at which a and b both land will be c

      so (c-a)+(c-b)=n*(n+1)/2 here c>=max(a,b) two cases arise (say)x=n*(n+1)/2+a+b

      1.x%2==0&&x>=2*max(a,b)

      iterate until above reach and print x

      below is my solution https://mirror.codeforces.com/contest/1278/submission/67251204

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      tmwilliamlin168 Care to explain?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I did the same thing, looping over the first n such that a >= b (assuming a < b at first) and that a and b will have the same parity.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      let's say $$$n$$$ is the value that $$$a$$$ and $$$b$$$ reach at the end, and there were $$$k$$$ operations. Then, $$$2n=a+b+\frac{k(k+1)}{2}$$$. Multplying by $$$2$$$, we get $$$4n=2a+2b+k(k+1)$$$. Let's say $$$a <= b$$$, then $$$4n>=4b$$$, so $$$2a+2b+k(k+1)>=4b$$$, we get $$$k(k+1)>=2b-2a$$$, then $$$(k+1)^2>=2b-2a$$$, so $$$k >= (2b-2a)^{1/2}-1$$$. But $$$2a+2b+k(k+1)$$$ is a multiple of $$$4$$$, so we can iterate $$$k$$$ by the first four values grater than or equal to $$$(2b-2a)^{1/2}-1$$$

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I took 2's as -1 and maintained prefix sum of array from left to center at each position and the same for the right of center.Then I stored first occurence of distinct prefix sum's to the left and right in different tables.Now just iterate over tables and check if an element in left table has a negative counterpart in the right one, if it does, then the gap is one of the possible answers.

»
5 лет назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

This was the most difficult B I've ever seen.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

That moment when you find the bug in the last second I'm so unlucky

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    That moment when C is easier than B :sad:

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Not really? You find the index of first triangle number larger than abs(b — a) that has the same parity as abs(b — a) :) Because you can increment the smaller number one by 1+2+3+...+n EXCEPT for (triangle number — abs(b — a)) / 2 (which is an integer) :)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think C can be solved using binary search (searching for the the minimum number of jars ) but why i got WA on test 2 ???? ooooohhhh

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Did you cover the case when you eat up no jar from the left side or right side?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    I don't think C is possible with bianry search, since (number of jar to use)->(whether the goal is possible) function is not monotonic.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you give me a test that explain your idea?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I do not think binary search is possible too because if an interval size satisfies the criteria of the question, bigger interval may violate it...I haven't generated the precise test case but consider the below transition:

        Binary search at len = x tells interval Lx,Rx is one of the feasible intervals: So interval is like : ..... 1 (1 2 2 1 1 2 2) 1 .... So just expanding the interval to the right or to the left or towards both sides changes the feasibility of interval to remain as answer.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      In which test case my solution is wrong?? https://mirror.codeforces.com/contest/1278/submission/67240467

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      i solved it using binary search,what i did is make two vectors (vector of pairs {value,index}) for left(1 to n) and right part(n+1 to 2*n) where each element of both arrays stores the contribution they give to the "difference".(if s=no. of strawberrys and b=no. of blackberrys then difference is abs(s-b) ).sort both vectors. Now apply binary search such that left_i + right_j = difference. Also check for left_i=diff and right_j=diff separately. This is my code : https://mirror.codeforces.com/contest/1278/submission/67254126

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For $$$C$$$ what is wrong with this approach:- Iterate from $$$2n$$$ to $$$n + 1$$$, If $$$a[i] == 1$$$ then $$$val = val + 1$$$ else $$$val = val - 1$$$, Push these values in an HashTable, $$$HashTable[val].pushback(index)$$$. Now iterate from 1 to n, keep a variable (let say) $$$val = 0$$$. If $$$a[i] == 1$$$ then $$$val = val + 1$$$ else $$$val = val - 1$$$, then find the smallest index corresponding to value $$$-val$$$ in HashTable(if present), and update the answer.

»
5 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

How to solve F?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    Essentially, the problem is this (My solution requires some knowledge about calculus and probability) Given a binomial distribution $$$B(n, \frac{1}{m})$$$, we want $$$E(X^k)$$$.

    Consider moment generating function $$$M(t) = E(e^{tX})$$$. Then, k-th moment, which is $$$E(X^k)$$$, can be achieved as $$$\frac{d^k}{dt^k} M(t)$$$ evaluated at $$$t = 0$$$. (one can prove this by taylor expansion)

    Also, a mathematical fact — $$$M(t) = (pe^t + 1 - p)^n$$$ for $$$B(n, p)$$$.

    Considering all this, try actually computing some derivatives. You can notice some pattern. By this pattern, we can get some $$$k$$$ degree polynomial about $$$n$$$ and $$$p = \frac{1}{m}$$$. The actual computation was quite messy, but the pattern was clearly noticable. The only task left is to implement this function and evaluate with rational numbers as given.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +26 Проголосовать: не нравится

      My approach is similar, but more intuitive IMO, if you have never seen the $$$M(t)=E(e^{tX})$$$ before.

      We want:

      $$$\sum_{i=0}^ni^k\binom{n}{i}\left(\frac{1}{m}\right)^i\left(\frac{m-1}{m}\right)^{n-i}$$$

      Notice, it is similar to our familiar binomial expansion:

      $$$\left(\left(\frac{1}{m}\right)x+\left(\frac{m-1}{m}\right)\right)^n$$$
      $$$=\sum_{i=0}^nx^i\binom{n}{i}\left(\frac{1}{m}\right)^i\left(\frac{m-1}{m}\right)^{n-i}$$$

      We want to create the term $i^k$ in the front, and then plug in $$$x=1$$$ to get our answer. How do we create the $$$i^k$$$? We, can do derivative with respect to $$$x$$$ :). Like this:

      $$$\frac{d}{dx}\left(\left(\left(\frac{1}{m}\right)x+\left(\frac{m-1}{m}\right)\right)^n\right)$$$
      $$$=\sum_{i=0}^nix^{i-1}\binom{n}{i}\left(\frac{1}{m}\right)^i\left(\frac{m-1}{m}\right)^{n-i}$$$

      Now, multiply $x$ and repeat! Do it $$$k$$$ times total to get the term $$$i^k$$$. Calculating the $$$k$$$ derivatives takes $$$O(k^2)$$$ time.

      Example: https://mirror.codeforces.com/contest/1278/submission/67249722

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Off topic note: does anyone know how to fix the inline latex not rendering correctly? :P

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Try to put \displaystyle in the beginning of a formula.

          $$$\displaystyle\sum_{i=0}^n\left[i^k\binom{n}{i}\left(\frac{1}{m}\right)^i\left(\frac{m-1}{m}\right)^{n-i}\right]$$$

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I don't get what the "multiply x and repeat" mean. It's easy for me to understand that after k times derivatice, the right of this equation is just what we want. But how to deal with the left part of this equation? I tried to multiply x and derivative the left part but found nothing. Would you like to explain it in details? Thx

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          The right side of equation starts with term $$$x^i$$$. After derivative it becomes $$$ix^{i-1}$$$. Then we multiply by $$$x$$$ to get $$$ix^i$$$. Then another derivative to get $$$i^2x^{i-1}$$$. Then multiply by $$$x$$$ again, etc. It is straight forward to see how this process can generate term $$$i^k$$$. Now, for left side, we must also do the derivative and multiply by $$$x$$$ repetition. For this, one strategy is to keep an array of size $$$k+1$$$ of coefficients of terms $$$\left(\left(\frac{1}{m}\right)x+\frac{m-1}{m}\right)^{n-i}x^i$$$ for $$$i=0,\ldots,k$$$, perform $$$k$$$ updates on this. This is the approach I used in submission above.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Couldn't we just calculate the original expression in the top without using any derivatives as only thing to care about there is the nci terms other than that all terms can be easily calculated.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          Ah, sorry, the sum is supposed to be to $$$n$$$, not $$$k$$$ (which is the reason why we can't calculate the sum directly). I have fixed the post now.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Can you tell why can we raise i to the power k?

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          Yes, it is actually from the definition of expected value. Informally, expected value of $$$f(x)$$$ is equal to:

          $$$\sum f(x)\cdot\left(probability\_of\_x\_jokers\right)$$$
          $$$=\sum f(x)\cdot\left(\frac{ways\_to\_get\_x\_jokers}{total\_ways\_to\_get\_any\_amount\_of\_jokers}\right)$$$

          In this case, $f(x) = x^k$, and the probability terms end up equaling the coefficients in my above comment.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Your solution was much better than the MGF one!

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Is there some pattern tbh? I am facing a lot of difficulty as to how to calculate those messy derviatives, how did you write the recursion for the same?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Yes, I can explain derivative implementation details :).

        $$$ \frac{d}{dx}\left(\left(\frac{1}{m}\cdot x+\frac{m-1}{m}\right)^n\right) =\left(\frac{1}{m}\right)^n\frac{d}{dx}\left(\left(x+m-1\right)^n\right) $$$

        We remove constant $$$\left(\frac{1}{m}\right)^n$$$ and account for it at the end. Now we do derivative and multiply by $$$x$$$.

        $$$ \frac{d}{dx}\left(\left(x+m-1\right)^n\right)\cdot x =(n)(x+m-1)^{n-1}x $$$

        Now, the second repetition.

        $$$ \frac{d}{dx}\left((n)(x+m-1)^{n-1}x\right)\cdot x $$$
        $$$ =(n-1)(n)(x+m-1)^{n-2}x^2+(n)(x+m-1)^{n-1}x $$$

        We notice all terms are of form $$$C\cdot(x+m-1)^{n-i}\cdot x^i$$$ for some coefficient $$$C$$$ and some power $$$i$$$. We create an array $$$a$$$ of size $$$k+1$$$ with indices $$$i=0,...,k$$$ such that $$$a[i]$$$ stores coefficient of above term. Now we can apply derivatives and multiplication of $$$x$$$ on this array. We can see this operation results in relation $$$a[i]=(n-i)\cdot a[i-1]+i\cdot a[i]$$$.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +59 Проголосовать: не нравится

    Let's rewrite $$$x^k$$$ as the number of tuples $$$(x_1, x_2, \dots, x_k)$$$ such that $$$1 \le x_i \le n$$$ and for every $$$i$$$, the $$$x_i$$$-th shuffle of the deck resulted in a joker. Then the expected value of $$$x^k$$$ is the expected number of such tuples.

    For each tuple, we need to determine the probability that it belongs to the set of tuples. If the number of distinct elements in a tuple is $$$y$$$, then this probability is $$$\frac{1}{m^y}$$$. Then for each $$$y$$$ calculate the number of tuples of size $$$k$$$ with exactly $$$y$$$ distinct elements; this can be done with dynamic programming — let $$$dp_{i, j}$$$ be the number of tuples of size $$$i$$$ with $$$j$$$ distinct elements; during each transition we either add a new element (there are $$$n - j$$$ ways to do it) or add a previously added element (there are $$$j$$$ ways to do it).

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +38 Проголосовать: не нравится

      F can be done in $$$O(K \log K)$$$ using FFT.

      $$$ \mathbb{E}(X^K)=\mathbb{E}((x_1+x_2+...+x_n)^K)$$$, where $$$x_i $$$ is indicator variable for the $$$i^{th}$$$ try.

      $$$ = \mathbb{E}(\sum_{y_1+y_2+..+y_n=K} {K \choose {y_1,y_2,...,y_n}} \cdot x_1^{y_1} \cdot x_2^{y_2}...\cdot x_n^{y_n} ) $$$

      $$$ = K! \cdot \mathbb{E}(\sum_{y_1+y_2+..+y_n=K} \frac{x_1^{y_1}}{y_1!} \cdot \frac{x_2^{y_2}}{y_2!} ... \cdot \frac{x_n^{y_n}}{y_n!})$$$

      Now, the Inner expected value can be calculated as :

      $$$ \sum_{i=1}^{min(N,K)} \binom{N}{i} (\frac{1}{M})^{i} \cdot \sum_{j=0}^{i} \binom{i}{j} \cdot (-1)^{i-j} \cdot \frac{j^K}{K!} $$$

      So, cleaning, we get :

      $$$ \sum_{i=1}^{min(N,K)} \frac{N!}{(N-i)!} \sum_{j=0}^{i} \frac{-1^{(i-j)}}{(i-j)!} \cdot \frac{j^K}{j!} $$$

      The inner sum part for each $$$i$$$ can be calculated over all $$$i$$$ using NTT, and so overall $$$O(K \cdot \log K ) $$$

      My Submission

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +60 Проголосовать: не нравится
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone have proof that the answer for problem $$$F$$$ is polynomial of degree $$$k + 1$$$?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Yes, as I wrote in the comment right above your comment, I tried computing some derivatives and could get $$$k$$$ degree polynomial. We start with $$$(pe^t + (1-p))^n$$$, and we differentiate it $$$k$$$ times. Also notice that since we are dealing with $$$t = 0$$$, $$$e^t$$$ term left in the solution will be evaluated to 1.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Note that we only need to find the expected value of $$$X^k$$$, where $$$X$$$ is a binomially distributed random variable with parameter $$$1/m$$$. For binomially distributed random variables, we know that the $$$E[D_r(X)] = \frac{n!}{(n-r)!} \cdot p^r$$$, where $$$D_r(x)$$$ is the falling factorial function with degree $$$r$$$. Also, we know that $$$x^k = \sum_{i=0}^{i=k} S(k, i) D_i(x)$$$, where $$$S(k, i)$$$ is the Stirling number of the second kind. Now the answer can be computed using a dp to compute $$$S(k, i)$$$ and then by taking the expected value of the identity above.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

I think n is too large in D/E. It's essential to solve problems like these using dfs approach, but you probably can't do it because stack size is not that large.

I've got StackOverflowError in this submission 67239760 and accepted the same code but with bfs instead of dfs 67244701.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

C can be solved with greedy approach in o(n) time. for right and left create a list X that each element is accumulated difference of the two types.

input = 1 1 2 1 2 1
becomes>>
right = [1 2 1]
left = [2 1 1]
X_right = [-1 0 -1]
X_left = [1 0 -1]

all numbers in X are between -5*10^4 and 5*10^4. then using X create a list ( or hashmap ) that is first occurrence of any number in X.

first_right = { -1:1 , 0:0}
first_left = {-1:3 , 0:0 , 1:1}

with this we decide how much of the total difference are we gonna cover from left or right.(greedy part) for example. 4 reds 2 blues so difference is -2.

right: 0 and left:-2 >> firstright[ 0] + firstleft[-2] >> n/a
right:-1 and left:-1 >> firstright[-1] + firstleft[-1] >> 1 + 3 = 4
right:-2 and left: 0 >> firstright[-2] + firstleft[ 0] >> n/a
»
5 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

I just browsed through some of the profiles and many of them says : William Lin fan-club

Anybody can shed some light on it for me?

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

when's the editorial coming?

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I think proof of B had similar idea as this question: https://atcoder.jp/contests/abc147/tasks/abc147_f

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится +13 Проголосовать: не нравится

The way I solved B was like this :

Let $$$P_n$$$ be a set of distinct natural numbers from $$$1$$$ up to $$$n$$$. And let $$$sum[i] = \frac{i*(i+1)}{2}$$$, which is sum of all natural numbers from $$$1$$$ to $$$i$$$. Choose two disjoint subsets $$$A$$$ and $$$B$$$ of $$$P_n$$$ such that $$$A \cup B = P_n$$$ and the difference between the sum of elements of $$$A$$$ and $$$B$$$ be $$$d$$$. You have to choose $$$A$$$ and $$$B$$$ is such a way that $$$d$$$ is equal to the difference between $$$a$$$, and $$$b$$$, and then add the subset having smaller sum with $$$max(a,b)$$$ and the other one with $$$min(a,b)$$$ to make $$$a$$$ and $$$b$$$ equal. Now the problem is to choose such a $$$P_i$$$ such that $$$i$$$ is minimum and $$$d = abs(a-b)$$$. Notice that if I choose $$$P_i$$$ such that $$$sum[i]$$$ is even, then the set of all possible $$$d$$$ made from $$$P_i$$$ contains all non negative even numbers up to $$$sum[i]$$$. The reason is, if you choose $$$A$$$ such that the sum of elements of $$$A$$$ is $$$x$$$, and then put all the other numbers of $$$P_i$$$ inside $$$B$$$, then sum of elements of $$$B$$$ and $$$A$$$ shall be $$$sum[i] - x$$$, and $$$x$$$ respectively. So, $$$d = sum[i] - x -x = sum[i] - 2x$$$. So, $$$d$$$ is even. And obviously $$$1 \leq x \leq sum[i]$$$, so we get all the non negative even numbers up to $$$sum[i]$$$. Similarly, if $$$sum[i]$$$ is odd, all $$$d$$$s are odd. So, the solution is to find minimum value of $$$i$$$ such that $$$sum[i] \geq abs(a-b)$$$.

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

whats the hack for D? and also is it a wa hack or a tle one?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

who can help me???67258839

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    problem C

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      I think your mistake is, you are adding 1 to $$$ans2[i]$$$ and $$$ans1[i]$$$ when you get 1, and adding -1 when you get 2. But, you need to check frequency of 1 and 2 first. If the frequency of 1 is greater, then you increment $$$ans[i]$$$ if 1 is found, and otherwise increment decrease $$$ans[i]$$$ by 1. I did the same mistake first.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится

        Can you give me a counterexample?thank you

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится

          I suggest you to use map. You are running the loop from 0 to $$$2*n$$$ and $$$2*n$$$ can be $$$2*10^5$$$ at most, but your array size is less than that. And also your nested loop may cause TLE.

»
5 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

When will system test start?

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

When system tests?-

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

someone can tell me why ( ans*(ans+1) — abs(a-b) )%2 == 0 in problem B ?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Imagine two numbers a and b. a=1 and b=5. The difference between both is 4. So we need a summation that is bigger than 4 like 1+2+3 which is equal to 3 steps. lets take the all the summation and add it to B so now the B becomes 11 and the difference is now 10. If you took the 2 from the summation and deleted it from B and added it to A, the difference will become 6 as you subtracted 2 from B and added it to A. do the same for the 3 and now the difference become 0. So overall, it has double the effect. 1+2+3=6 that summation accepts the difference between A and B to be:6,4,2,0. To sum up the idea, the summation result and the difference between A and B should be both either even or odd! I hope this helped!

»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

ООООООООООООООООООООчень плохие претесты по D. Там просто взяли и не засунули в претесты случаи, со вложенными отрезками с n — 1 ребром.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    А почему они должны были их туда засовывать?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      Чтобы решения не падали, а также чтобы люди понимали, что тупое решение не заходит

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Нужно же это самому продумать, а не требовать от жюри. Там не 5 тестов было, чтобы предъявлять, а 72.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

          Есть один косяк, что именно этот случай под корень режет тупой скан лайн

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    72-ой тест был именно такой ($$$n - 1$$$ ребро, но не дерево). Но его не хватило, видимо

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -24 Проголосовать: не нравится

      Там при этом нет ситуации, когда компоненты связанности вложенные, а это все-таки давольно-таки сложный случай

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody help me with the fact that — "What is the best way to approach a mathematical problem?"(Like Problem B in this contest).I usually try to make some test cases and from that cases try to form a general formula.But most of the times,i get WA in test case 4-5. :(

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Whenever you solve a problem(or maybe you fail to) always try to understand the mathematical solution behind it. It will add up to your knowledge and may help you next time. This is a never-ending process, you have to learn something new, every time.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think that each individual develops their own mathematical intuition for different types of problem and I am sorry to say that there is no shortcut to approach such problems, except one, practicing and up-solving lots and lots of math problems.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    1 — Solve codeforces under 1000-dif-math problem This is best way to get a better view of math problems(also all A&B problem)[I had the same problem solving math problems] and how to think better. As you done(became master solving this kind of problems easily), Start solving under 1500-dif and so on.
    2 — Study number theory.
    3 — Every step in thinking on a problem ask yourself what to do now? this gives your mind a really nice view about the problem.
    4 — Don't ignore some dumb ideas on a problem (sometimes this dumb ideas are the solution)
    5 — Search for the pattern not for a single testcase you wrote, think more open (for example : in problem B, it was better to write down all the differences that adding 1 to n can make. (I also did this & got Acc on B)
    Hope it was helpful.

»
5 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

When the ratings will be updated?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone share their approach to solve D?

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    basic idea is sort the range in increasing order of l. now consider a range at index i {l,r} find all the range that start b/w (l,r) and end after r then there will be intersection b/w segment without completely inside of another.

    now how can we do that optimally, maintain a segment tree such that v[i]=range[i].r after sorting. we can find the range of index of segment for which segment start b/w (l,r) using lower_bound. now we can update using segment tree, if max of v[i] is less than r for an interval in segment tree then we won't go into that node, otherwise there can be atleast one segment for which it start b/w (l,r) and end after r.

    In worst case there could nc2 edges but we don't need to go beyond n-1 edges. once there are n edges in graph it will no longer remain tree. so we can use dsu to maintain whether we got the cycle or not.

    to find a node in segment tree such that there will be intersection b/w segments, its complexity will be O(logn) using segment tree. we need to add atmost n-1 edges so combined complexity will be O(nlogn) and we need to maintain dsu for cycle check that can be O(nlogn) so overall complexity will be O(nlogn) Here is my Submission

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Shouldn't you have Min[p] = v[l] in your build function at line 111?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Oh yeah, my mistake I missed that in build function but reason it didn't made any effect on verdict because Min[i] will always be zero and the condition I applied (Min[i]>r) will never be true.

        I think my solution is pretty complex. return_me mentioned very simple idea for implementation as well in comment

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Get all the edges until it's less that n :) 67240718

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

when editorial will be published ?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can C be done in worst case O(n) time without using hashmap? I managed to do it in O(nlog n) using map, but I am curious about linear time!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think so using prefix and suffix sums and jumping pointers.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Instead of using a map to query the nearest index in the right half with required difference in strawberries and blackberries, we can maintain an array with size $$$2n$$$ initialized to -1. This works since difference ranges between $$$-n$$$ and $$$+n$$$. This will run in $$$O(n)$$$.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well yes, we can surely do that, but is there some general method to find if there exists a subarray whose sum is a given value, in linear time?

»
5 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

............When the ratings will be updated?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

when will the parsing be published? (if anyone has a discard please)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why does this solution 67308922 fails on case #434 on test 2?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

67469642 Could someone please explain to me which part of my code is causing the "heap use after free" error shown in the diagnostics section? (I understand my code is in no way a solution to the problem it was submitted for, I would just like to know what is causing the error before I try to convert what I have into a solution)

Thank you!