### awoo's blog

By awoo, history, 13 months ago, translation,

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)

• +65

 » 13 months ago, # |   +1 In Problem B : A and B, how do you arrive at those restrictions? Is there any other natural way to solve this problem?
•  » » 13 months ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » 13 months ago, # ^ |   +1 How do you know that every sum from 0 to x(x+1)2 can be obtained?
•  » » » » 13 months ago, # ^ | ← Rev. 5 →   0 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.
•  » » » » 13 months ago, # ^ |   +20 Proof by induction. for $n=0$ every sum from $0$ to $0$ can be obtained; let every sum from $0$ to $\frac{k(k+1)}{2}$ be obtainable for any $k$; 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.
•  » » » 13 months ago, # ^ |   +4 Ah thanks, I see, now I can understand it pretty well.
•  » » » 10 months ago, # ^ |   0 How do you write mathematical terms in comments?
•  » » » 27 hours ago, # ^ | ← Rev. 2 →   0 Thanks!
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 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)$.
•  » » » 13 months ago, # ^ |   0 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?
•  » » » » 13 months ago, # ^ |   0 Oh my bad... it should be $1 \leq x \leq sum[i]$
•  » » 13 months ago, # ^ |   0 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 : diff == 0. You're done as k is the answer. 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. 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
•  » » » 13 months ago, # ^ |   0 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.
•  » » » » 13 months ago, # ^ |   0 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
•  » » » » » 13 months ago, # ^ |   0 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
•  » » » » » » 13 months ago, # ^ |   +12 How about codeforces itself :P
•  » » » 13 months ago, # ^ |   0 Nice solution. please explain how you think like this as i am generally not able to think from problem B onwards.
•  » » » » 13 months ago, # ^ |   0 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!
•  » » » » » 13 months ago, # ^ |   0 ok thanks
•  » » » 13 months ago, # ^ |   0 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....
•  » » » » 13 months ago, # ^ |   0 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?
•  » » » » » 13 months ago, # ^ |   0 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.
•  » » » 13 months ago, # ^ |   +3 I did not quite understood the editorial but I understood your solving process. Thank you for writing the steps so easily :)
•  » » » » 13 months ago, # ^ |   0 Hey man, thanks a lot for your kind words :)
•  » » » 12 months ago, # ^ |   0 Thought the similar way. Loved your approach
•  » » » 12 months ago, # ^ |   0 can you explain more the case 2 & 3 of your post . In my head i'm not getting the logic clearly .
•  » » » » 12 months ago, # ^ |   0 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 :)
•  » » » » » 12 months ago, # ^ |   0 thanks .Your reply was so helpful
•  » » » 12 months ago, # ^ |   0 Awesome .. I also thought same way but got offtrack in 3rd step..yeah the main step, :-(
•  » » » 12 months ago, # ^ |   0 Thanks for the explanation... Can you please explain point number 3?? I am having difficulty in understanding it.
•  » » » » 12 months ago, # ^ |   0 Try thinking a bit more :) It is very similar to the point number 2! In case you still have troubles, I would happily explain!
•  » » » 8 months ago, # ^ |   +3 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!
•  » » » 8 months ago, # ^ |   0 You are the best :)
•  » » » 8 months ago, # ^ |   0 Thanks this is much better. this way of proving a solution helps in actual contest.
•  » » » 6 months ago, # ^ |   0 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 ?
•  » » » » 6 months ago, # ^ |   0 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!
•  » » » » » 6 months ago, # ^ |   0 Wow, thanks a LOT man :)))
 » 13 months ago, # |   0 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.
•  » » 13 months ago, # ^ |   0 1+2+3+ ... z = z(z+1)/2
 » 13 months ago, # |   0 1278C - Berry Jam is O(n) overall.
•  » » 13 months ago, # ^ |   0 Ye-ye, hashmap, sure.
•  » » » 13 months ago, # ^ |   0 or list with size less than 15MB.
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   +1 Ok, I see now, that's smart.Wait, it's not. Counting sort is boring, the solution of tyoungs is smart.
•  » » » » » 13 months ago, # ^ |   0 oh, thx. )) And also thx for great contest.
 » 13 months ago, # |   +16 I solve Problem C O(n) 67228111
•  » » 13 months ago, # ^ |   +3
•  » » » 5 months ago, # ^ |   0
•  » » 13 months ago, # ^ |   0 Could you please explain your solution?
•  » » » 13 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » 4 months ago, # ^ |   0 Can you elaborate more tyoungs
 » 13 months ago, # | ← Rev. 3 →   0 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!!
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Because in tree, every vertexes are connected with one or more edges. and total number of edge is n-1.
•  » » 13 months ago, # ^ | ← Rev. 2 →   +3 Every tree have n-1 edges but not every graph with n-1 edges is a tree :)
 » 13 months ago, # | ← Rev. 3 →   +24 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
•  » » 13 months ago, # ^ |   0 Can you please elaborate a little on the dp recurrence ?Thanks in advance.
•  » » » 13 months ago, # ^ | ← Rev. 3 →   +6 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_2And, you can check thatM^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)$.
•  » » » » 13 months ago, # ^ |   0 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.
 » 13 months ago, # |   0 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?
•  » » 13 months ago, # ^ |   0 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.
•  » » » 13 months ago, # ^ |   0 Oh, I see. If cnt exceeds n, the algorithm stops. Thank you!
 » 13 months ago, # |   0 Can B be solved with bfs? I tried but got TLE. May be 2^n complexity. Can anyone help? submission. 67329205
 » 13 months ago, # |   0 Why cant C Berry Jam be solved using greedy?I will eat the reqd jars that are closest to meSuppose I have to eat blue jars, then I will go to the side which has a closest blue jar.
•  » » 13 months ago, # ^ |   0 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
 » 13 months ago, # | ← Rev. 2 →   0 For Problem E, A little simpler to understand implementation using linked-list, so that insertions in between is possible: HereIdea is the same. When in dfs, for a subtree, let : Ending position of current node = r Starting position of current node = l Some child to the current node = c Answer recursively from subtree of child c = SubAnswer We have to: Append c to the left of r (So that starting point of child is in between current node's segment) 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.
•  » » 8 months ago, # ^ |   +3 thanks a lot :)
•  » » » 8 months ago, # ^ |   0 Glad I could be of help :)
 » 13 months ago, # |   0 THANKS YOU FOR THIS CONTEST
 » 13 months ago, # |   0 Can C be solved by DP?If can,what'd be the dp state(s).
 » 13 months ago, # |   0 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?
•  » » 13 months ago, # ^ |   +3 inv() returns the modular inverse using fermat's little theorem
 » 13 months ago, # |   +18 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$.
 » 13 months ago, # | ← Rev. 2 →   0 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}}$.
 » 13 months ago, # |   0 How to solve D in python.
 » 13 months ago, # | ← Rev. 2 →   0 Problem C is actually a "two-sum" problem, so we can use: sort + two pointers: O(N^logN) hashmap: O(N)
 » 13 months ago, # |   0 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?
 » 13 months ago, # |   0 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
 » 13 months ago, # |   0 can anyone explain why in problem F number of time joker comes out != n/m.
 » 13 months ago, # | ← Rev. 7 →   0 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),otherwiseS[l, r] denotes the number of strawberry jars in a range - B[l,r] denotes the number of blueberry jars in rangeMemory 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?
 » 13 months ago, # | ← Rev. 3 →   0 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 graphhttps://codeforces.com/contest/1278/submission/67768254
 » 13 months ago, # |   0 problem F were one of the best problems that i have seen :). nice contest.
 » 12 months ago, # | ← Rev. 3 →   +10 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
 » 10 months ago, # | ← Rev. 2 →   0 Deleted [unsolvable]
 » 9 months ago, # | ← Rev. 2 →   0 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!
•  » » 4 months ago, # ^ |   0 hey have you got the reason i am also having same problem
 » 9 months ago, # |   0 Solution of Problem D seems to have a complexity of N^2...correct me please if I am wrong... Thanks in advance
 » 8 months ago, # |   0 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
 » 7 months ago, # |   0 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