pikmike's blog

By pikmike, history, 5 months ago, translation, In English,

1278A - Shuffle Hashing

Idea: Ne0n25

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: Ne0n25

Tutorial
Solution (Ne0n25)

1278E - Tests for problem D

Idea: Ne0n25

Tutorial
Solution (Ne0n25)

1278F - Cards

Idea: BledDest

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

»
5 months 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?

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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?

      • »
        »
        »
        »
        5 months 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.

      • »
        »
        »
        »
        5 months 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.
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

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

      How do you write mathematical terms in comments?

  • »
    »
    5 months 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)$$$.

    • »
      »
      »
      5 months 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?

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months 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

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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!

    • »
      »
      »
      5 months 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....

      • »
        »
        »
        »
        5 months 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?

        • »
          »
          »
          »
          »
          5 months 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.

    • »
      »
      »
      5 months 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 :)

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

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

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

      Thought the similar way. Loved your approach

    • »
      »
      »
      4 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 .

      • »
        »
        »
        »
        4 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 :)

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

          thanks .Your reply was so helpful

    • »
      »
      »
      4 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, :-(

    • »
      »
      »
      4 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.

      • »
        »
        »
        »
        4 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!

    • »
      »
      »
      13 days 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!

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are the best :)

»
5 months 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.

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

    Ye-ye, hashmap, sure.

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

      or list with size less than 15MB.

      • »
        »
        »
        »
        5 months 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.

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

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

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

I solve Problem C O(n) 67228111

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

    Could you please explain your solution?

    • »
      »
      »
      5 months 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.

»
5 months 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!!

  • »
    »
    5 months 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.

  • »
    »
    5 months 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 :)

»
5 months 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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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)$$$.

      • »
        »
        »
        »
        5 months 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.

»
5 months 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?

  • »
    »
    5 months 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.

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

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

»
5 months 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

»
5 months 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.

  • »
    »
    5 months 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

»
5 months 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.

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

THANKS YOU FOR THIS CONTEST

»
5 months 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).

»
5 months 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?

»
5 months 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$$$.

»
5 months 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}}$$$.

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

How to solve D in python.

»
5 months 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)
»
5 months 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?

»
5 months 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

»
5 months 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.

»
5 months 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?

»
5 months 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

»
5 months 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.

»
4 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

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

Deleted [unsolvable]

»
7 weeks 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!

»
7 weeks 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

»
3 weeks 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