awoo's blog

By awoo, history, 21 month(s) ago, translation, In English

1278A - Shuffle Hashing

Idea: Neon

Tutorial
Solution 1 (pikmike)
Solution 2 (pikmike)

1278B - A and B

Idea: Roms

Tutorial
Solution (Roms)

1278C - Berry Jam

Idea: MikeMirzayanov

Tutorial
Solution (pikmike)

1278D - Segment Tree

Idea: Neon

Tutorial
Solution (Ne0n25)

1278E - Tests for problem D

Idea: Neon

Tutorial
Solution (Ne0n25)

1278F - Cards

Idea: BledDest

Tutorial
Solution (BledDest)
 
 
 
 
  • Vote: I like it
  • +65
  • Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

In Problem B : A and B, how do you arrive at those restrictions? Is there any other natural way to solve this problem?

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    It all comes pretty naturally when you know that every sum from $$$0$$$ to $$$\frac{x(x+1)}{2}$$$ can be obtained. The rest is simple math. Like let's add $$$s_a$$$ to $$$a$$$ and $$$s_b$$$ to $$$b$$$. Then you have

    $$$\begin{cases} s_a + s_b = \frac{x(x+1)}{2} \\ s_a - s_b = b - a \end{cases} \rightarrow \begin{cases} 2s_a = \frac{x(x+1)}{2} + b - a \\ s_a - s_b = b - a \end{cases} \rightarrow \begin{cases} s_a = \frac{\frac{x(x+1)}{2} + b - a}{2} \\ s_a - s_b = b - a \end{cases}$$$

    Obviously, $$$s_a$$$ should also be non-negative.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      How do you know that every sum from 0 to x(x+1)2 can be obtained?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 5   Vote: I like it 0 Vote: I do not like it

        Idk just look at the formula. Sooner or later (in no more than sqrt steps) $$$\frac{x(x+1)}{2}+b-a$$$ will become non-negative. Maybe in one or two more steps it'll get the same parity and become divisible by $$$2$$$. As there are no more constraints, that will be the answer.

        UPD: Whoops, wrong answer.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        Proof by induction.

        1. for $$$n=0$$$ every sum from $$$0$$$ to $$$0$$$ can be obtained;
        2. let every sum from $$$0$$$ to $$$\frac{k(k+1)}{2}$$$ be obtainable for any $$$k$$$;
        3. let's obtain every sum for $$$k'=k+1$$$. If some sum $$$s \le \frac{k(k+1)}{2}$$$, then we already know it can be obtained using first $$$k$$$ numbers without taking $$$k'$$$ into the subset. Otherwise take $$$k'$$$ into the subset and obtain $$$s-k'$$$ using the first $$$k$$$ numbers. $$$s \le \frac{k'(k'+1)}{2} \Leftrightarrow s \le \frac{(k+1)(k+2)}{2} \Leftrightarrow$$$ $$$s - k' \le \frac{(k+1)(k+2)}{2} - k' \Leftrightarrow s - k' \le \frac{(k+1)(k+2) - 2(k+1)}{2} \Leftrightarrow$$$ $$$s - k' \le \frac{k(k+1)}{2}$$$. Thus, it's obtainable with the first $$$k$$$ numbers as well.
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Ah thanks, I see, now I can understand it pretty well.

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you write mathematical terms in comments?

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

      Thanks!

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 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)$$$.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why is 1 <= x <= i? It means that the sum of elements in A, which is some numbers of from P_i, is at most i. I don't see the intuitive part in it.

      Can you explain a little more?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'll post my solution for Problem B.

    Suppose you had a < b. Take diff = a-b. Thus, diff is initially negative. Now suppose you keep adding numbers from 1 to k to a, this means that diff would increase by k*(k+1)/2; where k satisfies a-b + k*(k-1)/2 < 0 and a-b + k*(k+1)/2 >= 0. Thus, k is the least value where our diff becomes >= 0.

    Three cases arise :

    1. diff == 0. You're done as k is the answer.

    2. diff is even. Now, since diff = a-b + k*(k+1)/2 = a-b + k*(k-1)/2 + k <= k-1 , and diff > 0, and it is even; make diff 0 by subtracting 2x from it, where x is a number between 1 to k; this means that originally x was added to b rather than a. Thus, again k is the answer.

    3. diff is odd. Add k+1 to it. If the new value is even, your answer would be k+1, else it would be k+2. (Think about it, it's similar to the previous one!)

    My submission : 67240862

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hello there , I was going through your solution. Can you explain me the statement "Keep adding numbers from 1 to k to a." Thank you.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, that simply means that to the smaller of the two numbers(which we call a), we are adding all the numbers 1,2,...,k. I hope that's clear now

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah it is clear now. Thanks for the help Hey can we connect on some platform i might need some help if you don't have any issues. Thank you

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it +12 Vote: I do not like it

            How about codeforces itself :P

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice solution. please explain how you think like this as i am generally not able to think from problem B onwards.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hey, it's just about practice, I think so, even I struggle sometimes and then I realize nothing would help other than practicing. And CP needs a lot of practice!

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      hey buddy didn't get ur second point.....like why does it matter if diff is even or odd, since we are adding k(k+1)/2 to the smaller number (a or b), we should care about if we've added more than required or less than required.......that is whether diff=0 or diff>0. Please help me with it....

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You need to take care of all the things — if $$$diff == 0$$$, you're done; now suppose diff was even, what I can essentially say is that suppose you are at $$$k$$$, and you wanted to add the numbers $$$1,2,..i-1,i+1,...,k$$$ to $$$a$$$ and $$$i$$$ to $$$b$$$, this would essentially be same as adding all the values $$$1,2,...,k$$$ to $$$a$$$(and hence we get our $$$diff$$$) and then subtracting $$$2i$$$ from the $$$diff$$$, after which we get the answer as $$$0$$$. This would be possible only if $$$diff$$$ was even, since if it were odd, we couldn't subtract twice of some number(the number is $$$i$$$ here) and get $$$0$$$. I hope I am more clear now, should I explain with an example?

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I had wrongly Interpreted the question XP......i thought we are doing a+1+2+3+.....and b+1+2+3+.....separately until a=b I gotta attempt it again......anyways thanks for making me realize it.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I did not quite understood the editorial but I understood your solving process. Thank you for writing the steps so easily :)

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hey man, thanks a lot for your kind words :)

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thought the similar way. Loved your approach

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain more the case 2 & 3 of your post . In my head i'm not getting the logic clearly .

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'll try with an example - Take a = 5 and b = 9. So diff is $$$-4$$$ initially. Now you keep on adding numbers till diff is negative. So diff becomes $$$-3$$$, then $$$-1$$$ and then $$$2$$$, and $$$k = 3$$$ finally. So here diff is even and the second case tells you that you must subtract $$$2*x$$$ from diff to make it 0(here x is 1) so it means that 1 was originally added to b and not a. $$$[5 + 2 + 3 = 9 + 1]$$$

        For a = 5 and b = 10, the other case follows and is fairly similar :)

        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thanks .Your reply was so helpful

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Awesome .. I also thought same way but got offtrack in 3rd step..yeah the main step, :-(

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the explanation... Can you please explain point number 3?? I am having difficulty in understanding it.

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Try thinking a bit more :) It is very similar to the point number 2! In case you still have troubles, I would happily explain!

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

      Awesome explanation!

      But I would like to highlight that one who took help, should also upvote your solution, at least those for whom you answered their queries.

      I have done my part! And appeal others to do the same. Too less of upvotes is actually not a good gesture.

      PS: I know you didn't do it for upvotes, still!

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are the best :)

    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks this is much better. this way of proving a solution helps in actual contest.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hello, sorry for being kinda late, and awesome explication. However, theres a point that i havent got, Why would the answer still be k when diff is even , but it would be either k+1 or k+2 when its odd ? , more specifically, why the fact that when diff is even means that a number from 1 to k was added to b rather than a , but it doesnt means that when diff is odd ?

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, diff is $$$b-a$$$ in our case, and suppose instead of adding $$$k$$$ to $$$b$$$, we add it to $$$a$$$, then diff would change by $$$2*k$$$ and if diff were to be even, we could use diff/2 as $$$k$$$ in the above statement. If it's odd, we can't do such a thing and hence, we need to make it even once again!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the meaning of the statement "And we can get any integer from 0 to z(z+1)2 as a sum of subset of set {1,2,…,z}"? The tutorials uploaded here are never simple, I would suggest codeforces that the tutorials should be detailed and not short. Also how it turns out that we always can make integers a and b equal after applying x operations? Please explain with respect to the tutorial above.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

1278C - Berry Jam is O(n) overall.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ye-ye, hashmap, sure.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      or list with size less than 15MB.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        Ok, I see now, that's smart.

        Wait, it's not. Counting sort is boring, the solution of tyoungs is smart.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          oh, thx. )) And also thx for great contest.

»
21 month(s) ago, # |
  Vote: I like it +16 Vote: I do not like it

I solve Problem C O(n) 67228111

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain your solution?

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      if you have x more jam1 than jam2, you have to eat x morejam1 than jam2. so, if you eat A more jam1 than jam2 in left, you have to eat x-A jam1 than jam2 in right.

      than you eat right jam sequential and if you eat K( 1,2,...)more jam1 than jam2, store in v1[K](minimum number of jams).

      and do same in right.

      and calculate the answer.

»
21 month(s) ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In Problem D: Can you explain why we must check the connectivity of the graph after knowing the total of edges ?
I know that the tree will have strictly n-1 edges (Pls correct me if i was wrong :) )

thank you!!

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Because in tree, every vertexes are connected with one or more edges. and total number of edge is n-1.

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Every tree have n-1 edges but not every graph with n-1 edges is a tree :)

»
21 month(s) ago, # |
Rev. 3   Vote: I like it +24 Vote: I do not like it

Another approach to solve problem F:

Since, the probability of getting a good shuffle = $$$\frac{1}{m}$$$ and we perform $$$n$$$ trials. The number of good shuffles $$$x$$$ follows a binomial distribution. $$$P(x) = \binom{n}{x} \frac{1}{m^x} (1 - \frac{1}{m})^{n-x}$$$

Now, we know that $$$E[x] = \sum\limits_{x=0}^{n} x P(x)$$$.

And $$$E[x^k] = \sum\limits_{x=0}^{n} x^k P(x)$$$

This cannot be used directly since $$$n$$$ is quite large. However, $$$E[x^k]$$$ can also be calculated using the moment generating function $$$M(t)$$$. For binomial distribution, $$$M(t) = (pe^t + q)^n$$$ where $$$p = \frac{1}{m}$$$ and $$$q = 1 - p$$$

Now all we have to do is differentiate $$$M(t)$$$ $$$k$$$ times w.r.t $$$t$$$ and get $$$M^k(t)$$$. Then, $$$E[x^k] = M^k(0)$$$ While differentiating $$$M(t)$$$ we can observe that the coefficients of $$$e^{at}$$$ follows a recurrence which can be easily implemented using $$$dp$$$.

67281862

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please elaborate a little on the dp recurrence ?

    Thanks in advance.

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 3   Vote: I like it +6 Vote: I do not like it

      So we have $$$M(t) = (pe^t + q)^n$$$

      After differentiating once,

      $$$M^1(t) = n(pe^t + q)^{n-1}pe^t$$$

      After second differentiation,

      $$$M^2(t) = n(n-1)(pe^t + q)^{n-2}p^2e^{2t} + n(pe^t + q)^{n-1}pe^t$$$

      Now let's define,

      $$$C_a = p^a (pe^t + q)^{n-a} n(n-1)...(n-a+1) e^{at}$$$

      Then,

      $$$M^1(t) = C_1$$$

      $$$M^2(t) = C_1 + C_2$$$

      And, you can check that

      $$$M^3(t) = C_1 + 3C_2 + C_3$$$

      $$$M^4(t) = C_1 + 7C_2 + 6C_3 + C_4$$$

      Let's denote coefficient of $$$C_a$$$ by $$$b_a$$$ after some $$$m$$$ differentiation operations.

      Then you can see that $$$b_a$$$ after $$$m+1$$$ differentiation,

      $$$b_a = b_a * a + b_{a-1}$$$

      The intuition here is that $$$e^{at}$$$ in $$$C_a$$$ gives $$$b_a*a$$$ and $$$(pe^t + q)^{n-a+1}$$$ in $$$C_{a-1}$$$ gives $$$b_{a-1}$$$ on differentiation.

      Now we have to find all $$$b_a$$$ $$$1 \leq a \leq k$$$. Since, we are doing differentiation $$$k$$$ times. This can be done in $$$O(k^2)$$$.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks a lot for writing a detailed explanation. It was quite interesting how you came up with a formula for 'b'. This solution seems easier than the editorial.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D: what is the time complexity in the solution of Problem D? In worst condition, the solution access all the elememt in the 'set'. why not use lower_bound or upper_bound to count?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Notice that on each element accessed $$$cnt$$$ will be increased by $$$1$$$. Thus, the total number of accesses will not exceed $$$n$$$.

    Also you can't use lower_bound to count something quickly, difference of iterators on set is linear in complexity. Moreover, you need the elements themselves, not just their amount.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I see. If cnt exceeds n, the algorithm stops. Thank you!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can B be solved with bfs? I tried but got TLE. May be 2^n complexity. Can anyone help? submission. 67329205

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why cant C Berry Jam be solved using greedy?

I will eat the reqd jars that are closest to me

Suppose I have to eat blue jars, then I will go to the side which has a closest blue jar.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's consider this example : n = 11 1 1 1 1 2 2 2 2 1 2 2 [STAIRS] 2 2 2 1 1 1 1 1 1 1 1

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For Problem E, A little simpler to understand implementation using linked-list, so that insertions in between is possible: Here

Idea is the same. When in dfs, for a subtree, let :

  1. Ending position of current node = r
  2. Starting position of current node = l
  3. Some child to the current node = c
  4. Answer recursively from subtree of child c = SubAnswer

We have to:

  1. Append c to the left of r (So that starting point of child is in between current node's segment)
  2. Append SubAnswer to the right of r (Rest of the segment of the child is to the right of the parent segment's end point).
(l)(r) ->  (l)(c)(r)(SubAnswer)

Notice that we are ensuring that each child is completely inside the previously included children by appending to the left and right of the parent's endpoint.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

THANKS YOU FOR THIS CONTEST

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can C be solved by DP?

If can,what'd be the dp state(s).

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

BledDest Can you please explain what does inv() do? Does it invert the number? Why the output is equal to the inverted number?

Or can you introduce a source so i can read and understand?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    inv() returns the modular inverse using fermat's little theorem

»
21 month(s) ago, # |
  Vote: I like it +18 Vote: I do not like it

Problem F:

Denote $$$p=1/m,q=1-p=1-1/m$$$.

One can show that $$$ans=\sum_{t=0}^n \binom{n}{t}p^tq^{n-t}t^k$$$.

Notice that $$$t^k=\sum_{i=1}^{k}S(k,i)t^{\underline{i}}$$$, where $$$S$$$ denotes the Stirling Number of the second type.

So

$$$ ans=\sum_{t=0}^{n}\binom{n}{t}p^tq^{n-t}\sum_{i=1}^kS(k,i)t^{\underline{i}}\\ =\sum_{i=1}^kS(k,i)\sum_{t=0}^n\binom{n}{t}p^tq^{n-t}t^{\underline{i}}\\ $$$

Denote $$$f(x)=\sum_{t=0}^n \binom{n}{t}p^tq^{n-t}x^t=(px+q)^n$$$

One can get $$$\sum_{t=0}^n\binom{n}{t}p^tq^{n-t}t^{\underline{i}}$$$ by taking the derivative of order $$$i$$$ of $$$f(x)$$$ and put $$$x=1$$$, i.e., $$$f^{(i)}(1)$$$.We get that $$$E(t^{\underline{i}})=n^{\underline{i}}p^i$$$.

$$$ ans=E(t^k)=\sum_{i=1}^kS(k,i)E(t^{\underline{i}})=\sum_{i=1}^kS(k,i)n^{\underline{i}}p^i. $$$

Time complexity is $$$O(klogk)$$$ or $$$O(k^2)$$$.

But in fact, one can give a combinatorial explanation:

We sum the contribution of the $$$k-tuple$$$ $$$x_1,x_2,\cdots,x_k$$$, where $$$x_i \in [1,n]$$$.

Assuming it has $$$i$$$ distinct values of the $$$k$$$ values, we can choose these $$$i$$$ values from $$$1..n$$$ in $$$\binom{n}{i}$$$ and put $$$1..k$$$ in the $$$i$$$ ordered sets in $$$S(k,i)i!$$$ ways, and notice that it contributes $$$p^i$$$ to the answer because the $$$i$$$ distinct indexes must take $$$1$$$ (get the joker) at the same time (its expectation equals to its probility).

$$$ ans=\sum_{i=1}^k\binom{n}{i}S(k,i)i!p^i=\sum_{i=1}^kS(k,i)n^{\underline{i}}p^i $$$

To generalize this, if we get the joker at the $$$i-th$$$ time in probility $$$p_i$$$, denoting $$$a_k=[x^k]\prod_{i=1}^n(1+p_ix)$$$, one can show that we just substitute the term $$$\binom{n}{i}p^i$$$ by $$$a_i$$$.

$$$ ans=\sum_{i=1}^kS(k,i)i!a_i $$$

For more general case, one can notice that we can consider about each random variable separately only if they are individual. We can get $$$E_i(k)=E(x_i^k),k \ge 0$$$.

By using binomial convolution, we can combine them to get $$$E=E_1 \circ E_2 \circ \cdots \circ E_n$$$ , where $$$E(k)=E(S^k), S=\sum_{i=1}^n x_i$$$, which can be derived by multinomial theorem.

Maybe in some problem, $$$E_i$$$ should be calculated by dynamic programming with some parameter about $$$i$$$.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Another way to implement the dp in problem F is as follows.

Let $$$dp(i, j)$$$ be the no. of different $$$i$$$-tuples having $$$j$$$ different elements. So,

  • $$$dp(i, j) = 0$$$, if $$$i < j$$$

  • $$$dp(i, j) = j * (dp(i-1, j-1) + dp(i-1, j))$$$, otherwise

This formula is based upon the following reasoning: Consider the last element of the tuple. There are $$$j$$$ ways to choose it.

Now, the $$$i$$$-th occurrence is either the last occurrence of this element, in which case, the no. of tuples are $$$dp(i-1, j-1)$$$, or it is not the last occurrence of this element, in which case the no. of tuples are $$$dp(i-1, j)$$$.

Now, the final answer is $$$\large{\sum\limits_{d=1}^k \binom{n}{d} \frac{dp(k, d)}{m^d}}$$$.

Since $$$n$$$ is large $$$n \choose d$$$ may be calculated from $$$n \choose {d-1}$$$ as:

$$$\large{\binom{n}{d} = \frac{n-d+1}{d} * \binom{n}{d-1}}$$$.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D in python.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem C is actually a "two-sum" problem, so we can use:

  • sort + two pointers: O(N^logN)
  • hashmap: O(N)
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, I couldn't understand the following statement: "When we add a segment, we find all segments which intersect with it — that is, all segments that end earlier than it." Can someone explain the solution in more detail?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

The author's solution for problem D is quite hard for me to grasp, the way he/she add both start and ending time into vector evs is so clever. I have implemented this approach by my style, I think it maybe help someone. My submission

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain why in problem F number of time joker comes out != n/m.

»
21 month(s) ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

Is there any solution using dp for problem C?

I came up with this:

Let dp[i][j] be the minimum number of jars that need to be emptied so that there is an equal number of strawberry and blueberry jam jars left.

Then:

dp[i][j] = 0,if S[0, i] + S[j, 2n] = B[0, i] + B[j, 2n]

dp[i][j] = min(dp[i-1][j] + 1, dp[i][j+1] + 1),otherwise

S[l, r] denotes the number of strawberry jars in a range - B[l,r] denotes the number of blueberry jars in range

Memory space can be optimized to be O(n), but running time is O(n^2).

Is there any way to improve this? or is this the best you can do with dp?

»
21 month(s) ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I solved problem D use direct way :record the minimum right point of segment intersection relation in the map, the current segment would delete all record that (old segment right point) < (current segment left point) and if the deleted one is a small single connected graph then the big graph is not connected . after delete, the current segment would update the minimum right point in the map and if (current segment minimum right point) > (old segment minimum right point) then the graph have cycle.
after all segment update, the map would only contain one single graph

https://codeforces.com/contest/1278/submission/67768254

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

problem F were one of the best problems that i have seen :). nice contest.

»
20 months ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

It's my first solution in English, but I'm not good at it...

Problem F can be solved in $$$O(k)$$$, it's based on $$$O(k \log k)$$$ solution.
Denote $$$p = 1/m$$$, the answer is:

$$$\sum\limits_{i=0}^k S(k,i) n^{\underline i}p^i$$$

We can expand that Stirling number:

$$$ \sum\limits_{j=0}^k\frac{1}{j!}\sum\limits_{i=0}^j(-1)^{j-i}\binom{j}{i} i^k j! \binom nj p^j$$$
$$$=\sum\limits_{i=0}^ki^k\sum\limits_{j=i}^k(-1)^{j-i} \binom nj \binom ji p^j$$$
$$$=\sum\limits_{i=0}^ki^k\binom ni\sum\limits_{j=i}^k(-1)^{j-i}\binom{n-i}{j-i}p^j$$$
$$$=\sum\limits_{i=0}^ki^k\binom ni p^i\sum\limits_{j=0}^{k-i}(-1)^j\binom{n-i}{j}p^j$$$

Denote

$$$f(i) = \sum\limits_{j=0}^{k-i} (-1)^j \binom{n-i}{j} p^j$$$

obviously that $f(k) = 1$ .

$$$f(i)-f(i+1)=(-p)^{k-i} \binom{n-i}{k-i} + \sum\limits_{j=0}^{k-i-1}(-p)^j \left(\binom{n-i}{j}-\binom{n-i-1}{j} \right)$$$
$$$f(i)-f(i+1)=(-p)^{k-i} \binom{n-i}{k-i} + \sum\limits_{j=1}^{k-i-1}(-p)^j \binom{n-i-1}{j-1}$$$
$$$f(i)-f(i+1)=(-p)^{k-i} \binom{n-i}{k-i} - p\sum\limits_{j=0}^{k-i-2} (-p)^j\binom{n-i-1}{j}$$$
$$$f(i)-f(i+1)=(-p)^{k-i} \binom{n-i}{k-i} - \left( (-p)^{k-i} \binom{n-i-1}{k-i-1} + pf(i+1)\right)$$$
$$$f(i)=(-p)^{k-i}\binom{n-i-1}{k-i}+(1-p)f(i+1)$$$

Now $f(i)$ can be calculated from $$$f(i+1)$$$ in $$$ O(1)$$$.
So the problem F can be solved in $$$O(k)$$$ ( rquired linear-sieve to calculate $$$i^k$$$ ).

Especially, this solution is wrong when $$$n \le k$$$. My Submission

»
18 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Deleted [unsolvable]

»
17 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1278/submission/75598239 Can someone please help me figure out why my code gives TLE on TEST 49 for problem D? It would be a huge help ! Thanks in advance!

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey have you got the reason i am also having same problem

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution of Problem D seems to have a complexity of N^2...correct me please if I am wrong... Thanks in advance

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    well, potentially $$$cnt$$$ could be $$$O(n^2)$$$ but we stop early, as soon as $$$cnt \geq n$$$.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am following a basic algorithm for question B. But it fails to work for test case 2. Can someone find out the error in logic? 78991112

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My approach for B was like: first i increase n until n*(n+1)/2>=gap (*gap=abs(a-b)) . if difrnce of N*(n+1)/2 and gap between is even this is the answer(bcoz we can remove then having half value of the dif and the two no will become equal) else increase n until this becoomes even and print n

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E what does non-degenerate segment mean??

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I have a much simpler solution for E. Perform DFS and for every node push all its children in reverse order of the traversal and push the initial node and that's it. Here is the code.