By awoo, history, 5 years ago, translation, In English

Hello Codeforces!

On Dec/19/2019 17:35 (Moscow time) Educational Codeforces Round 78 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Hi Codeforces!

The deadline to apply for our Master’s Scholarship in Bangkok is very soon!

Don't miss your chance and apply for our progressive Master’s programs in Data Science and Cyber Security in just 3 steps:

1. Submit your CV to see if you are an eligible candidate for the scholarship
2. If your profile matches the requirements, one of our admissions officers will get in touch with you
3. Apply for the program, pay the 125€ application fee, pass a series of interviews, and if you’re accepted, pack your bags to Bangkok!

And if you know someone who might be interested in Digital Marketing, High Tech Entrepreneurship, Interaction Design or FinTech, send them our way!

MORE INFO→

Also, don’t forget to read our newest blogs!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 HIR180 6 106
2 neal 6 162
3 receed 6 172
4 Geothermal 6 174
5 cerberus97 6 179

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Akulyat 24
2 hoke_t 20
3 dhxh 18:-1
4 vovanstrr 14
5 WNG 13:-1
255 successful hacks and 458 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
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: Editorial is out

  • Vote: I like it
  • +129
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +124 Vote: I do not like it

![ ](meme)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Why educational rounds have more greedy problems?

»
5 years ago, # |
Rev. 2   Vote: I like it -20 Vote: I do not like it

Clashes with Mirror replay round of ICPC Gwalior regionals on Codechef

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +55 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can D solved something like interval handling using set?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried and got MLE on test 51 :(

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes, it can.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought of similar approach but stopped. Isn't your time complexity in worst case O(N^2) since you are also iterating the set of segments containing the i as starting point?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        sort the segments depending on the endpoints.
        now for each segment i, all you need to iterate on is the segments j between i + 1 and n that satisfies the condition: start_point[i] <= start_point[j] <= end_point[i]
        which is the number of edges in the created graph

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        when you have more than n-1 edges, just stop.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Okay, I get if(it.first > a[j].r) break; this makes it run faster.

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # |
  Vote: I like it +1 Vote: I do not like it

WHAT IS TEST CASE 2 OF DIV2B

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Try for cases like 2 4 (Ans:3) or 5 14 (Ans:5)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how is the answer for 2,4 equal to 2 ? could you explain it a little more

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry my mistake. Corrected.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          also for 5,14 case , i am getting 6 not 5 as the answer.

          first 5 + 1 = 6 //step 1
          6+2 = 8 // 2
          8 + 3 = 11 // 3
          11 + 4 = 15 // 4
          15 + 5 = 20 // 5
          14 + 6 = 20 // 6

          Is there a better way ?

»
5 years ago, # |
  Vote: I like it +47 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    input: 1 31 20

    output : 5

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    test this: 1 5 answer is 3 because: 1) 1 6 2) 3 6 3) 6 6

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for this case!

      So what was the approach to solving the problem?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        Sorry for my poor english, I cant explain this problem to you. The main idea that (a + b + tmp) mod 2 = 0 and (a + b + tmp) / 2 >= max(a, b), where tmp = 1 + 2 + 3 + .. + n. You can check my submission, I think it will help you. https://mirror.codeforces.com/contest/1278/submission/67230823

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Is there any chance of getting the second problem being hacked?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I think no.Educational rounds usually have strong sys tests

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But you just did ++tmp it does't mean tmp = 1 + 2 + 3 + ... +n.

          i hope you understand.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            tmp in my code its just a number that we will add next time, when we will need it. I increase a every time in cycle.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    using 2 prefix sum arrays and then using maps

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    What is wrong in the greedy approach?

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

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +2 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Anyone solve C using binary search???

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please explain the process in detail ?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve B?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    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 years ago, # ^ |
    Rev. 2   Vote: I like it +21 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      tmwilliamlin168 Care to explain?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +52 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    That moment when C is easier than B :sad:

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you give me a test that explain your idea?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    you don't cover the case when you eat no jar from the left or right

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You may have missed some corner cases..

»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

How to solve F?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 4   Vote: I like it +26 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
          Rev. 2   Vote: I like it +3 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            THX!How stupid of me for forgetting this is a "programming" competition lol

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your solution was much better than the MGF one!

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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 years ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it +38 Vote: I do not like it

      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 years ago, # ^ |
      Vote: I like it +60 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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 years ago, # |
  Vote: I like it +6 Vote: I do not like it

when's the editorial coming?

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
5 years ago, # |
Rev. 4   Vote: I like it +13 Vote: I do not like it

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 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

who can help me???67258839

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    problem C

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Can you give me a counterexample?thank you

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          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 years ago, # |
  Vote: I like it +37 Vote: I do not like it

When will system test start?

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

When system tests?-

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +37 Vote: I do not like it

When the ratings will be updated?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share their approach to solve D?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

when editorial will be published ?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!