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

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

I solve Problem C O(n) 67228111

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

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

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?

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.

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.

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?

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

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$$$.

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).

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$$$.

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$$$.

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 \lt 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}}$$$.

How to solve D in python.

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

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

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.me/contest/1278/submission/67768254

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

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:

We can expand that Stirling number:

Denote

obviously that $f(k) = 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

Deleted [unsolvable]

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

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

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

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

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.

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();
    }
}

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.me/contest/1278/submission/193536274

For problems like this F and https://codeforces.me/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)

Problem F can also be solved using FFT in $$$O(k \cdot \log k \cdot \log MOD)$$$.

I will explain the solution assumming that the solution of the tutorial is clear.

The strategy is to use divide and conquer over the $$$n$$$ experiments to select $$$j$$$ of the experiments in which we get the joker (These $$$j$$$ experiments are not necessarily distinct).

Let $$$dp[i][j]$$$ be the number of ways to do this with $$$i$$$ experiments selecting $$$j$$$ of them. It's not hard to see that this can be calculated as

That is, we divide the segment in two parts and iterate over the ways to choose the number of events in each of those.

Since we want to count the number of $$$k$$$-tuples (and account for the probability), we will also count the number of ways to order these events that we choose. To do this, we can just multiply each result by $$$n!$$$ (all the possible permutations of the events that we choose) and we will also have to divide by $$$k_i !$$$ for each experiment we choose (where the event happens) where $$$k_i$$$ is the number of times this experiment was chosen.

This can be done by defining

After defining these base cases, we can see that we can just calculate $$$dp[i]$$$ by multiplying the two vectors $$$dp[i/2], dp[(i + 1)/2]$$$ using fft. And at the end, the answer will be $$$dp[n][k] \cdot n!$$$

Link