awoo's blog

By awoo, history, 5 years 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

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

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

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

      Thanks!

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

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

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

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

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

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

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

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

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

    • »
      »
      »
      4 years 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 ?

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

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

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

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

    Ye-ye, hashmap, sure.

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

      or list with size less than 15MB.

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

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

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

I solve Problem C O(n) 67228111

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

    Could you please explain your solution?

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

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

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

How to solve D in python.

»
5 years 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 years 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 years 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.net/contest/1278/submission/67768254

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

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

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

Deleted [unsolvable]

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

https://codeforces.net/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!

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

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

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

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

»
3 years 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.

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

I am late but nonetheless I liked B a lot, here's my simple approach and solution

Let's say a >= b, let's assume we make n operations, let's consider finally we will arrive at some t such that a + t1 = b + t2 = t, and t1 + t2 = n * (n + 1) / 2

Now, just substitute values and then we get, - t1 = t — a - t2 = t — b - t — a + t — b = n * (n + 1) / 2 - 4 * t — 2 * (a + b) = n * (n + 1)

We get t = (2 * (a + b) + n * (n + 1)) / 4, also note that t >= a So, we have a and b just find such n such that t is valid, to speed up the process and find value of n very quickly, we can see n >= sqrt(2 * a — 2 * b)

#include <bits/stdc++.h>
#define int long long int

void solve(){
    int a, b;
    std::cin >> a >> b;

    if(a == b) {
        std::cout << 0 << "\n";
        return;
    }

    if(a < b) {
        std::swap(a, b);
    }

    int n = std::sqrt(2 * a - 2 * b);

    while(1) {
        int t = (2*(a + b) + n*(n + 1)) / 4;
        if((2*(a + b) + n*(n + 1)) % 4 == 0 && t >= a) {
            std::cout << n << "\n";
            return;
        }
        n += 1;
    }
}
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    int t = 1;
    std::cin >> t;
    while(t--){
        solve();
    }
}
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I suppose I was the only smooth-brained idiot who took the title of div-2 D too seriously and solved it with a segment tree: https://codeforces.net/contest/1278/submission/193536274

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

For problems like this F and https://codeforces.net/problemset/problem/1187/F, a useful way (for me) to think about it is to think about E[x]^n as a (E[x])^n => (sum of indicators)^n.

Then it becomes easier to analyze, since it's just polynomial multiplication. Viewing the indicators as objects that combine in this way made it click for me.

For example, the "distinct elements in tuples" intuition that the editorial provides can also be restated in indicators: Since (ind)^n = ind (an event is either true or false, so exponentiating true/false doesn't change the event), that sort of just implies that we only care about distinct events (and different indicators multiply together cleanly since everything is independent, for this problem at least).

So the problem becomes, "I give you a 'polynomial' that is composed of N indicators with EV 1/m, all completely disjoint from each other. Exponentiate this K times. What is the expected value"? and this rephrasing is easier for me to understand.

It's probably the same thing as what the editorial is saying, but with the way editorial says it, I still don't really get it.

I was taught this a few days ago by dbaumg and it seems like a very powerful tool to formalize "contribution to sum" technique

(Disclaimer: I don't know stats or any real probability so I don't know if what I said above can just be expressed in terms of other things)