### peti1234's blog

By peti1234, 2 years ago,

Hope you enjoyed the problems.

Direction Change
Social Distance
Make it Increasing
Optimal Partition
Half Queen Cover
Edge Elimination
Centroid Probabilities
Yin Yang
• +146

| Write comment?
 » 2 years ago, # |   -23 Great contest and lighting fast editorial l.thora to rukoo( wait a bit) , d was good almost did it in contest
•  » » 2 years ago, # ^ |   -6 what's there to downvote?
 » 2 years ago, # |   0 thanks for superfast editorial
 » 2 years ago, # | ← Rev. 3 →   0 Fastest editorial ?I'm happy that I actually had some approach for problem D instead of being totally clueless, which is a huge improvement
 » 2 years ago, # | ← Rev. 3 →   +99 Please, add option “VERY bad problem” to C
•  » » 2 years ago, # ^ |   -15 E is a lot worse
 » 2 years ago, # |   +59 How would one come up with the solution of div1C? I can't get even remotely close to it
•  » » 2 years ago, # ^ |   +64 You think "how can I save k queens from the trivial solutions of n queens?". Then you note that the issue in doing so is that you have kxk region that is not covered by horizontal and vertical lines (determined by not necessarily consecutive rows and columns). The path of least resistance is to hope for arrangements when that region is simply a kxk square. You need to cover it by diagonals and you play a lil bit on paper with construction. Moving in knight's move fashion is an often trick when you are covering consecutive diagonals.
 » 2 years ago, # |   +75 FFT in E? I believe I solved it in much easier way (15 seconds after the contest end though...)big[i] is the probability that subtree of vertex i has at least (n+1)/2 vertices, cent[i] is the probability that i-th vertex is the answer
•  » » 2 years ago, # ^ |   0 What is Newt()? Quick_Power?
•  » » » 2 years ago, # ^ |   0 int Newt(int n, int k) { if (n < k) { return 0; } return fact[n] * inv_fact[k] % P * inv_fact[n - k] % P; } https://mirror.codeforces.com/contest/1667/submission/154135370
•  » » 2 years ago, # ^ |   +6 For the big[] part, is it simply doing algebra or does it imply a prettier combinatorial explanation?
•  » » » 2 years ago, # ^ |   0 There is a nice combinatorial explanation. Note that there is an easy bijection between all permutations of n numbers, where numbers 1..i are in order and 1 has to be the first number of whole permutation and ways of how do you connect guys i+1..n — you start from 1,2,...,i and you insert next numbers one by one into some place in this permutation, but not at the beginning. The number before new number is the one it connects to. (We don't care how guys 1..i are connected between themselves in order to determine whether subtree of i is big). Let's remove that 1 from our permutation. In this bijection, the subtree of i is big if and only if all numbers 2..i are in the first half of that permutation, so the formula from my code follows.
•  » » » » 2 years ago, # ^ |   0 Nice idea, Thanks!
 » 2 years ago, # |   +16 What is the meaning of "If we store the prefix sums, and assign a permutation according to the prefix sums,..."?
•  » » 2 years ago, # ^ |   +6 Greter prefix sum — greater value in the permutation.For example: array: $[1, 3, -5, 4, 2]$, prefix sums: $[1, 4, -1, 3, 5]$, permutation: $[2, 4, 1, 3, 5]$
•  » » » 2 years ago, # ^ |   +13 Ok...But still, "So there is an optimal solution when only winning segments might be longer than 1. It is easy to handle the 1 long segments. For each i (1≤i≤n) we have to find j, 0<=j0, and dpj+v(j+1,i) is maximal (dp0=0)."Why $v(j+1,i)$ has to be positive? Is this somehow different from the initial, $n^2$ solution? And how/why does this prefix-sum ordered permutation help finding $j$ ?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +25 Why v(j+1,i) has to be positive? The paragraphs at the beginning of the editorial explain why it's optimal to only consider indexes $j < i$ such that $v(j+1, i)$ is positive or the case when the last element is in a segment by itself (that is $j = i-1$).case 0:The case when the last element is in a segment by itself, is covered by $dp_i = dp_{i-1} + v(i,i)$.case 1:If $v(j+1,i)$ is negative, then we can split the segment $[j+1,i]$ into $i-j$ segments of length $1$, and the sum of values over these segments of size 1 can't be less than $v(j+1,i)$. However, the scenario when $[j+1,i]$ is split into segments of size 1 is already covered in case 0.case 2:If $v(j+1,i) = 0$, we can also split $[j+1,i]$ into two or three segments, the last of which (ending at $i$) either has positive value, or is of size 1, and moreover the sum of values over these (two or three) segments is not less than $v(j+1,i)$. (Look at the editorial to understand how).This means we don't have to worry about $j$ when $v(j+1,i)$ is not positive. And how/why does this prefix-sum ordered permutation help finding j ? By the previous observation, $dp_i$ is either equal to:$dp_i = dp_{i-1} + v(i,i)$ (last element is in a segment by itself), or$dp_i = max_{v(j+1,i) >0} (dp_j + v(j+1,i))$ -- the maximum over all $j$ such that $v(j+1, i)$ is positive. By definition, if $v(j+1,i)$ is positive, then $v(j+1,i) = i-j$. But $v(j+1,i)$ is positive if and only if $pref(j) < pref(i)$.So we can rewrite the second equality as:$dp_i = max_{pref(j) < pref(i)}(dp_j + i - j)$.How do we quickly find maximum of $dp_j-j$ over the interval $(-\infty, pref(i))$ ? We could use Segment Tree (or Fenwick Tree), but the values of $pref(i)$ can get very large. But we only need the relative order of $pref(i)$, so we can normalize the array $pref$ and replace it with values from $0$ to $N$.
•  » » » » » 2 years ago, # ^ |   0 Thanks for this detailed explanation!
•  » » » 2 years ago, # ^ |   0 How does one compute the permutation? I can think of O(nlogn) way but is there better?
•  » » » » 23 months ago, # ^ |   0 I'm not sure if there is better, but O(n log n) is good enough for the bounds of this problem.
 » 2 years ago, # |   0 In the editorial of problem F of div1, Did the author know that no one will solve it because it's so hard, Or he has removed the editorial of it now?
•  » » 2 years ago, # ^ |   +20 I removed before the last minute.
 » 2 years ago, # |   +43 Another optimal construction for C that's different from the editorial looks like alternating knights moves from the bottom left like this: .........X ........X. .......... .......X.. .....X.... .......... ....X..... ..X....... .......... .X........ 
•  » » 2 years ago, # ^ |   +13 Yup. The motivation for me was to put one half-queen on an infinite board. Then try to repeatedly cover some of the closest uncovered squares, hence the knight move. All the while trying to keep the construction as square as possible, hence the alternating knight moves. text pictures of the solving process.*..*... .*..*+.. .*%.*+.. .*%.*+.. ..*.*... ++*+*W++ ++*+*W++ ++*+*W++ ...**... ...**++. %.%**++. %^%**++. ****V*** ****V*** ****V*** ****V*** ....**.. ....**.+ %%U%**%+ %%U%**%+ ....*.*. ....*+*. ..%%*+*. ^^%%*+*. ....*..* ....*+.* ..%.*+.* ^X%^*+^* ....*... ....*+.. ..%.*+.. .^%.*+.. Additionally, this approach doesn't have special cases for $n = 1$ or $n = 2$.
 » 2 years ago, # |   +247 $\sum_{j=S-1}^{n-i} \frac{(n-j-2)!}{(n-i-j)!}=(i-2)!\sum_{j=S-1}^{n-i} \binom{n-j-2}{i-2}=(i-2)!\binom{n-S}{i-1}$
•  » » 2 years ago, # ^ |   +60 But intentionally, we can use NTT! So it will fit the Div. 1 E place! KAN, have you really reviewed these problems carefully?
 » 2 years ago, # | ← Rev. 2 →   +52 My solution for Div2D/Div1B uses a map instead of segment/Fenwick trees: 154120734 (hope it passes system tests :D UPD it did!).Let $dp_i$ be the answer for the array $a_1, a_2, \dots, a_i$. Then$dp_i = \max_{j < i} dp_j + (i - j) * sign(a_{j + 1} + ... + a_{i})$.Since, as proven in the editoral, losing and drawing segments can always be of length 1, we can account for them just by initializing $dp_i$ as $dp_{i - 1} + sign(a_i)$. Now in our maximum we only have to consider segments which have a positive sum, because only they can improve $dp_i$. If the segment from $j + 1$ to $i$ has a positive sum, then $p_i > p_j$, where $p$ are the prefix sums. We can rewrite$dp_i = \max(dp_{i - 1} + sign(a_i), \max_{j < i, p_j < p_i} dp_j + (i - j))$.We can store pairs $(p_j, dp_j - j)$ in a map and find our maximum using lower/upper_bound on that map. We have to keep it sorted by $dp_j - j$. This is a known trick where on every insert we remove all the pairs which have larger $p_j$ but smaller $dp_j - j$. In total there will be at most $O(n)$ removals.The final complexity is $O(n \log n)$.
•  » » 2 years ago, # ^ |   +3 Looks like a cool trick. Thanks for sharing.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Thank you! I wonder if your solution can be considered forward-style dp as opposed to the editorial's backward style dp.
•  » » » 2 years ago, # ^ |   +1 I think by adapting the solution to more of a forward style, you get the one from the editorial. :)
•  » » » 2 years ago, # ^ |   +1 If you manually update all of the relevant states every time, the solution will be $O(n^2)$, which is impossible to fit under the constraints. However, you can think of Fenwick/segment tree as a way of updating all the states at once. This is where you arrive at the editorial solution.
 » 2 years ago, # |   +18 If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.Divison 2 Divison 1 If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
 » 2 years ago, # |   0 Overall great contest. But I have a problem. I implemented the solution to div 2. C (make it increasing) which is same as the official one. The complexity is O(n^2). The problem is it is in Python and it gets timed out on pretest 4. Is there any better solution to the problem or is the solution to just code in C++?
•  » » 2 years ago, # ^ |   0 Try pypy 3 64-bit.Otherwise you have to switch to big int I think which is too slow.I TLE'd too with pypy 2 once before resending with pypy 3 64-bit (the second submission AC'd).
•  » » » 2 years ago, # ^ |   +1 Oh. That hurts even more. I didn't change anything and submitted and it got accepte. Kinda sucks that i was correct but not really...
•  » » » 2 years ago, # ^ |   +3 Thank you for this information, I had the same issue. Why does this make it faster, though?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +4 If the integers you work with get too large python switch to big int (something like an array of ints) which tends to be very slow. Using regular (32-bit) python or pypy, this happens when n>2^31 (somewhat more than 2*10^9). With 64-bit pypy you can go up to 2^63 (like a c++ long long).For example, if you multiply two numbers mod 10^9+7 in a loop you should use 64-bit pypy because otherwise it can be slow (you'll go above 32-bits with big ints). Modular addition and subtraction stay within 32-bit so they're not an issue. In problem C, the numbers could be as large as 5000*10^9 (or as low as -5000*10^9) so they wouldn't necessarily fit a 32-bit int and therefore you need to use 64-bit pypy.
•  » » » » » 2 years ago, # ^ |   +3 It didn't even occur to me that the sum might exceed a 32-bit int! Thanks for explaining.
•  » » 2 years ago, # ^ |   0 :( I did equivalent O(N^2) in C#. Stress tested it at ~950ms. Just in case decided to tune my code: removing silly stuff like getting value of an array too often, adding early terminations, moving from Int64 to Int32. Resulted in ~550ms on my stress test. Probably a good thing I did it.
 » 2 years ago, # |   +32 Judge ver. of D1C is good (educational?) problem!Step 1 First, if the output doesn't satisfy the minimum number of half-queen, return WA.Next, let's define$A$ := the set of rows that don't have any half-queen$B$ := the set of columns that don't have any half-queen(For example, $A=\{2,3\}$ and $B=\{3\}$ for the sample output 3)If half-queens were rooks, just check whether at least one of $A$ or $B$ is empty. How to deal with the diagonal line? Step 2 From $A$ and $B$, find the set $C$ := (the set of possible values of $c-d$ such that there are no half-queens on the row $c$ and column $d$).If $A=\{4,6\}$ and $B=\{3,5\}$, $C$ is $\{-1,1,3\}$ .This set can be found by using FFT or bitset (memo: in the previous example, use FFT like $(x^4+x^6)$ $\times$ $(x^{k-5}+x^{k-3})$ $=$ $(x^{k-1}+2x^{k+1}+x^{k+3})$).Finally, for each element $x$ of $C$, if there are no half-queens at $(p+x,p)$, return WA. Otherwise, return AC.
•  » » 2 years ago, # ^ |   +119 First, if the output doesn't satisfy the minimum number of half-queen, return WA. Not exactly sure what you mean here, but this sounds as a bad checker design practice, so I want to comment on this. In general checkers should be as independed from the solution as possible; in this case it should first check that the queens indeed cover the board in both the model and the participant's solutions, and only after that compare the number of half-queens used, and return one of ok, wa, or fail verdicts.
•  » » » 2 years ago, # ^ |   -21 But i don't consider your judging method an efficient and easy one...
 » 2 years ago, # | ← Rev. 2 →   +13 peti1234 Thanks for the fast editorial. Problem 1668B - Social Distance is an interesting problem. Nonetheless, only the Note section shows that it is possible to permute the order of the $n$ people. It would have been better to clarify in the problem statement that it is required to find if there exists a permutation of the $n$ people that satisfies the given social distance constraints.
 » 2 years ago, # |   +45 Here is my solution to C, with no casework, and very simple to implement.For some arrangement of $k$ queens, if we only consider the row and column moves, there is a $(n - k) \times (n - k)$ subgrid that we must additionally cover. Notice that the cells in the bottom edge and left most edge of the subgrid must be covered by different diagonals. Therefore we get the condition $2(n - k) - 1 \le k$. Let's now try constructing it. If we try to use the top right $(n-k) \times (n-k)$ grid, as our subgrid, we must place the queens on $(i, p[i])$ for $1 \le i \le k$, where $p$ is some permutation of ${1\ldots k}$. Then we notice that we need all different values between $[-n+k+1, n-k-1]$ to be taken by $i - p[i]$ for some $i$. If we reverse we get all even differences for an odd length array, and all odd differences for a even length array. So we just reverse the first $\lceil n/2 \rceil$ elements of the identity permutation, then the next $\lceil n / 2 \rceil - 1$ of the new permutation. This gives us all odd and even differences needed. Codevoid solve(){ int n; cin>>n; int k = 0; while(2 * (n - k) - 1 > k){ ++k; } vector p(k); iota(p.begin(), p.end(), 0); int hk = (k + 1) / 2; reverse(p.begin(), p.begin() + hk); reverse(p.begin() + hk, p.end() - (k % 2 == 0)); cout<
 » 2 years ago, # |   0 Thanks for a nice contest!Regarding Div1C/Div2E: How do you guys approach such problems? I went in a completely wrong direction:(. Can you perhaps recommend some problems(in a similar spirit) or resources?
 » 2 years ago, # | ← Rev. 2 →   0 I want to share a formal and more "maths-ish" proof for observation in div2B LemmaGiven an increasing array $a[1\dots n]$, and $p[1\dots n]$ is a permutation of $a$. Then:$P=\sum_{i=1}^{n} max(p[i],p[i + 1]) \ge 2a[n]+a[n-1]+\dots + a[2]$To prove it we need lemma 1: Lemma 1With every $a$,$b$,$c$, we have the inequality: $max(a,b)+max(b,c)\ge b + max(a,c)$ProofConsider 2 cases: $b$ is the largest of all, and $b$ is not. In the first case the lemma is obvious. In the second case, we can assume $a$ is the largest number. Then we can check cases of $c$ (Q.E.D).The inequality holds if and only if $b$ is between $c$ and $a$ in real axis.This lemma can be extended to $\sum_{i=1}^{m}max(x[i],x[i+1])\ge max(x[1],x[m+1])+\sum_{i=2}^{m}x[i]$. ProofNotice that if we do some cyclic shift to $p$, $P$ remains. Then we can assume $p[1]=a[1]$. Also let $p[k] = a[n]$. Now according to lemma 1 we have:$P=\sum_{i=1}^{k-1}max(p[i],p[i+1])+\sum_{i=k}^{n}max(p[i],p[i+1])$$\ge max(p[1],p[k])+\sum_{i=2}^{k-1}p[i]+max(p[k],p[n+1])+\sum_{i=k+1}^{n}p[i]$$=2a[n]+\sum_{i=2}^{n-1}a[i]$. (Q.E.D) InterestingThe equality holds if and only if two subsequences of $p$ from $1$ to $k$ is monovariate. Which means the sitting order along the circle does not necessarily need to be increasing. For example if we get $a[1\dots 7] = {1;2;3;4;5;6;7;8;9}$ we can arrange them as $1-3-4-6-9-8-7-5-2-1$.
 » 2 years ago, # |   +4 So when we calculate $dp_i$, we should update with $dp_i−i$. This way, finding the optimal $j$ for each $i$ is just a prefix maximum. One can solve the problem with Fenwick tree or segment tree.Can someone explain why should we update $dp_i - i$
•  » » 2 years ago, # ^ |   +20 Because our dp transition is: $dp_i = max(dp_j + i - j)$, since $i$ is independent, we can rewrite it as follows: $dp_i = i + max(dp_j - j)$. As you can see, we always need $dp_j - j$ and what's why we update with this value.
 » 2 years ago, # |   +8 Can you please attach this editorial to the contest attachments? Currently we just have the announcement attached.
 » 2 years ago, # |   +24 MikeMirzayanov, I believe there are some violations of the rules in div2. kirya_molodec1, kirya_molodec2, kirya_molodec3, kirya_molodec4, kirya_molodec7 and kirya_molodec6's code are really confusing and similar, and they submitted each problem almost at the same time.
 » 2 years ago, # |   -13 There is a spellling error in the solution of D, can you find it?
 » 2 years ago, # |   +1 In solution of D optimal partition, in case of drawing segment. I don't understand how "For a drawing segment with length k if k is even than the answer is the same if we split it into two segments with length k/2". I have tried proving this, but I could not. Can someone share a proof for this please?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Say your initial segment has size $2*k$ and is drawing (the sum is $0$), so it contributes $0$ to the answer. If you split it into two halves of size $k$, then either both halves are also drawing, or one half is winning and the other is losing. In either case, the combined contribution of the two halves is also $0$.
 » 2 years ago, # |   +10 I Made Video Solutions for div2 A-D in Case someone is Interested.
 » 2 years ago, # |   0 Can anybody suggest me some online blogs or youtube channels or any sites from where I can learn about "parity". In the Problem A, the knowledge about parity is must needed, so from where I can learn that well for CP?
•  » » 2 years ago, # ^ |   0 If the number is odd then the parity is 1, if even then 0. In on word, parity is the remainder of any number divided by 2.
 » 2 years ago, # | ← Rev. 2 →   +3 consruction in the end of the solution of E
 » 2 years ago, # |   0 C is a nice problem!
 » 2 years ago, # |   0 Div1E is a nice problem, btw, An O(n) solution without NTT exists.
 » 2 years ago, # |   0 Solution to Div2C which would have given wrong answer 154180260 passed system tests. (Here I checked for 0 position only till n-1th position.) So, in main tests, there is no testcase in which answer ends with 0.
•  » » 2 years ago, # ^ |   +5 Your solution is correct. There is no test, where the answer ends with 0. In that case you can set the n-1-th position to 0, and make 1 move on the last element. The answer will be the same.
•  » » 2 years ago, # ^ |   0 The answer ending in 0 must be smaller than that ending in the penultimate 0, because the first penultimate 0 does not move, then all the previous ones must become negative. In other words, the second penultimate one will become negative at least once, but the first penultimate one will remain unchanged. Considering that the second penultimate one remains unchanged, it will be better if the first penultimate one becomes positive, because the second penultimate one becomes 0,0 > negative.
 » 2 years ago, # |   +10 Let me pen down a Div1F draft solution outline. I have been thinking of this problem for the day. Might be wrong.Consider the colored points in the parameter and put them in a circular array. Remove consecutive duplicates in the circular array. If the length if the array is more than 2, there is no solution.One side of the parameter will be white and another side will be black (The parameter might be all of the same color, we need to resolve that case as well). Build a black tree from a black point on the parameter.
 » 2 years ago, # |   +1 problme Bsort it is easier
 » 2 years ago, # |   0 The problem C have a faster solution ? I wrongly calculate 5000 * 5000 equals 2.5e8 , so at first I think the O(n^2) solution will TLE.
 » 2 years ago, # |   0 NICE ROUND.
 » 2 years ago, # | ← Rev. 2 →   +10 I try to solve div1 E by using some math solutions. I get the expression of this:we set $k = \frac{n - 1}{2}$, then for a point id $1 < u \le k + 1$, the answer is: $(2k - u + 1)! (u - 1)! (C^{u-1}_k - \sum\limits_{x=0}^{k-1}\frac{1}{2k-x}C^{u-1}_x)$($C^a_b$ means combination number $\frac{b!}{a!(b-a)!}$, and when $a > b$ we set $C^a_b = 0$)I judged this expression is right. However, I don't know how to deal with the expression $\sum\limits_{x=0}^{k-1}\frac{1}{2k-x}C^{u-1}_x$, since that's an $O(n^2)$ implementation for all $1 •  » » 2 years ago, # ^ | ← Rev. 8 → +18 Thanks to newbin or playf, with her help, I solved div1 E with solve combinatorial math skills. Maybe it looks a bit long, but it's easy to think(Especially for anyone who are bad at DP like me) Here are my solutions:We set$k = \frac{n-1}{2}$. Consider a point$u (1 < u\le k + 1)$, let$c$be the number of point$v$such that$v > u$and$u$is not an ancestor of$v$. And$t$be the number of$u$'s son. So$u$has son$v_1,...,v_t$. The size of subtree rooted by$v_i$is$n_i$($1\le i\le t$. So the answer of$u$is:$(u-1)!\sum\limits_{c=0}^{k-u+1}C_{n-u}^c(u-1)u...(u-2+c)\sum\limits_{t=0}^{\infty}\frac{1}{t!}\sum\limits_{n_1+n_2+...+n_t=n-u-c,1\le n_i\le k}\frac{(n-u-c)!}{n_1!...n_t!}(n_1-1)!...(n_t-1)!$Let$f(x) = x+\frac{1}{2}x^2+...+\frac{1}{k}x^k$, the expressions equals to:$(n-u)!(u-1)!\sum\limits_{c=0}^{k-u+1}C_{u-2+c}^c\sum\limits_{t=0}^{\infty}\frac{1}{t!}\sum\limits_{n_1+n_2+...+n_t=n-u-c,1\le n_i\le k}\frac{1}{n_1...n_t}$$=(n-u)!(u-1)!\sum\limits_{c=0}^{k-u+1}C_{u-2+c}^c\sum\limits_{t=0}^{\infty}\frac{1}{t!}[x^{n-u-c}]f^t(x)$$=(n-u)!(u-1)!\sum\limits_{c=0}^{k-u+1}C_{u-2+c}^c[x^{n-u-c}]e^{f(x)}$Note that$f(x)=\ln(\frac{1}{1-x})-\frac{1}{k+1}x^{k+1}-\frac{1}{k+2}x^{k+2}-...$, we have:$e^{f(x)}=\frac{1}{1-x}e^{-\frac{1}{k+1}x^{k+1}-\frac{1}{k+2}x^{k+2}...}=(1+x+...+x^{2k})(1-\frac{1}{k+1}x^{k+1}-\frac{1}{k+2}x^{k+2}-...-\frac{1}{k+k}x^{k+k})(mod\ x^n)$so$[x^{k+d}]e^{f(x)}=1-(\frac{1}{k+1}+...+\frac{1}{k+d})$for$1\le d \le k$.Let$d = k - u + 1 - c$, the expression is:$(n-u)!(u-1)!\sum\limits_{d=0}^{k-u+1}C_{k-1-d}^{u-2}[x^{k+d}]e^{f(x)}=(n-u)!(u-1)!(\sum\limits_{d=0}^{k-u+1}C_{k-1-d}^{u-2} - \sum\limits_{d=1}^{k-u+1}\frac{1}{k+d}\sum\limits_{y=d}^{k-u+1}C_{k-1-y}^{u-2})$$=(n-u)!(u-1)!(C_{k}^{u-1} - \sum\limits_{d=1}^{k-u+1}\frac{1}{k+d}C_{k-d}^{u-1})=(n-u)!(u-1)!(C_{k}^{u-1} - \sum\limits_{x=0}^{k-1}\frac{1}{2k-x}C_{x}^{u-1})$$=(n-u)!(u-1)!(C_{k}^{u-1} - \frac{1}{(u-1)!}\sum\limits_{x=u-1}^{k-1}\frac{x!}{(x-u+1)!(2k-x)})$Consider$F(x)=\frac{(k-1)!}{k+1}+\frac{(k-2)!}{k+2}x+...+\frac{(k-k)!}{k+k}x^{k-1}$,$G(x)=\frac{1}{0!}+\frac{1}{1!}x+...+\frac{1}{(k-1)!}x^{k-1}$We can calculate$\sum\limits_{x=0}^{k-1}\frac{x!}{(x-u+1)!(2k-x)}$for all$1
 » 2 years ago, # |   +19 For div.1 E, we need to calculate $\sum\limits_{j=S-1}^{n-i}\dfrac{(n-j-2)!}{(n-i-j)!}$. But if we multiply it with $\dfrac{1}{(i-2)!}$, it turns to $\sum\limits_{j=S-1}^{n-i}\dfrac{(n-j-2)!}{(n-i-j)!(i-2)!}=\sum\limits_{j=S-1}^{n-i}\dbinom{n-j-2}{i-2}=\dbinom{n-S}{i-1}$, which can be calculated in $O(1)$ time without NTT. And total time complexity is $O(n)$.
 » 2 years ago, # |   0 What is the reason that ratings are temporarily rolled back? I have this a few times. I am curious about the reason.
•  » » 2 years ago, # ^ |   0 To remove cheater and calculate rating again.
 » 2 years ago, # |   0 Could someone clarify on (D)Optimal Partitions?: "There is an optimal solution if the length of the drawing and losing segments are 1. Proof: For a losing segment in the worst case we can get two losing segments with the same total length (the same value)." I get the first sentence, don't quite get the proof tho.
•  » » 2 years ago, # ^ |   +3 If the sum is negative in a segment then each element counts as -1. It can't lessen if you split it into shorter segments. Exapmle: [-3, 0, -1, -2] (the value is -4) -> [-3, 0], [-1, -2] (the value is -2+(-2)=-4)
•  » » » 2 years ago, # ^ |   0 Ah, got it now. Thanks for the clarification
 » 2 years ago, # | ← Rev. 2 →   0 Can someone please explain why this solution is not working for Div2 — Problem C https://mirror.codeforces.com/contest/1667/submission/154462818I am fixing the first element of array in some range as of now but can be fixed by binary search exactly and then trying to figure out minimum value for all possible values.
•  » » 2 years ago, # ^ |   0 Hello, peti1234, in editorial of Div.1-C problem, can you please tell how you came up with the inequality (a+b-1 <= k), I spent a lot of time on it but did not get it. And can you elaborate on "Let's assume that there is a solution for k queens" line ?? (Does it mean the k queens for whole grid satisfying the given condition) and if it is true then how there will be left uncovered rows and columns and use of variables (a,b) ?? Sorry for tagging but couldn't understand after spending quite a time on it.
•  » » » 2 years ago, # ^ |   0 Each cell is covered if there is a half-queen in the same row, same column, or same diagonal. A cell in the intersection of a non-covered row and column must be covered diagonally.I showed that there are a+b-1 cells (on different diagonals) which must be covered diagonally. A half-queen can only cover 1, so we get the a+b-1 <= k inequality.
 » 2 years ago, # |   +3 Can somebody explain " Any order is good, when it always changes parity, and ends with an odd edge. " in Div1 D? I cannot fully understand.
•  » » 2 years ago, # ^ |   0 For each vertex we care about the order of the removed edges. There are two good orders: odd-even-odd-even......-odd or even-odd-even-odd.... even-odd.
•  » » » 2 years ago, # ^ |   0 Could you elaborate a bit more on this part? Consider the directed graph with these conditions. One can see, that this graph is acyclic, so there is a topological order of that graph which will satisfy all the conditions. i.e. how does finding that there are no contradictions when labeling each edge as odd/even guarantee we can ultimately remove all the edges in some order (in particular, according to the way it's done in the editorial's implementation)
•  » » » » 2 years ago, # ^ |   +3 Each edge has a parity, and each vertex has the same number of odd and even edges (or one more odd). For example, the edges are o_1, o_2, ... o_k, and e_1, e_2.. e_k, then a good removing order can be e_1, o_1, e_2, o_2..... e_k, o_k around this vertex.In the directed graph (where each vertex is an edge in the normal graph) we add the following directed edges: e_1->o_1->e_2->o_2....... e_k->o_k.And we do the same for each vertex. One can see that this directed graph will be acyclic, because it is a tree. So there is a topological order. This topological order will satisfy all the removing conditions described above.
•  » » » 2 years ago, # ^ |   0 Thanks. But what's the principle to assign the directions of an edge?
•  » » » » 2 years ago, # ^ |   0 Assign parity to each edge.This is a pretty easy tree dp problem. For each vertex (x) calculate the parity of all edges in its subtree. Than it is easy to calculate the parity, between x and the parent of x. Because x will have the same number of odd and even edges (or one more odd).
•  » » » » » 2 years ago, # ^ |   +10 Got it. Many thanks.
 » 2 years ago, # |   0 in question 2 it was given sum of n dont exceed 10^5 but i got correct only after using ll sum.i got wrong when i used int sum . am i correct or wrong
•  » » 2 years ago, # ^ |   0 Sum of n will not exceed 10^5, because it is the size of the input. Sum of a[i] can be larger, than 2^31.
 » 2 years ago, # |   0 For div1B/div2D, I'm new to Fenwich tree I have some questions All the top solutions use Fenwich tree, is there any advantage of it compare to segment tree, or it's just easier to implement ? Is Fenwich tree used only in prefix sum or does it have other use ?
•  » » 2 years ago, # ^ |   0 Little bit faster, and easier to implement. There are other applications, but that's more complicated.
 » 2 years ago, # |   0 In div1E part where we calculate answer $ans[i] = dp[i] - \sum_{j=i+1}^{n} \frac{ans[j]}{i}$Why $\frac{ans[j]}{i}$
•  » » 2 years ago, # ^ |   +8 $j$ is the centroid, and there is a decreasing path from $j$ to $1$. If this path crosses $i$, than $i$ is not the centroid, but we counted this case in $dp[i]$.On the path there is a unique vertex $k$, where $k>i$ and $p[k]<=i$ (the next vertex on the path). $p[k]$ can be anything, between $1$ and $i$ equiprobable, so there is a $1/i$ chance, that the path will go through $i$.
 » 2 years ago, # |   0 Hello can someone please help with my program for div1 B. It is giving WA on test 5 and I am not sure why. It is here: https://mirror.codeforces.com/contest/1667/submission/157232098
 » 2 years ago, # | ← Rev. 2 →   0 In Social Distance can we try the approach in which instead of assuming it as the circular geometry of chairs can we consider it as a linear geometry of chairs. If the person i want a[i] person should not sit on the right and left side of him then there should be a count of the sum which adds 2*a[i] and if that sum> n.o of chairs then it means then the arrangement is not possible otherwise it is possible. 1668B - Social Distance
•  » » 2 years ago, # ^ |   0 No, we can't add 2*a[i]. With that approach you are using more chairs than needed. Imagine two people, one of them wants three empty chairs around them and other one wants two chairs. They sit next to each other. It would mean that there are ten empty chairs between them, but it's optimal to put only three chairs and both of them will be satisfied. You can think about it this way: we will use empty chairs for person who needs more chairs, but the person who needs less chairs is also satisfied because it needs at least a[i] number of chairs so it can use those chairs as well.
 » 2 years ago, # |   0 Easier implementation of B: 162562808.
 » 6 months ago, # |   -8 I wasn't able to understand the implementation of "Make it increasing" problem. So, implemented in my own way, using the same concept as provided by editorial. Link