### rng_58's blog

By rng_58, history, 19 months ago,

We will hold AtCoder Regular Contest 106.

We are looking forward to your participation!

• +168

 » 19 months ago, # |   +33 Bump. ARC soon, fellow S.T.A.L.K.E.R. (Oh really, when? Now.)Come play if you're a pleb like me and it's still rated for you.
 » 19 months ago, # |   +17 I wish the word positive was in bold in problem A :)How do you solve D? Is there some nice result that comes straight from binomial expansion, or do I have to do some fancy math?
•  » » 19 months ago, # ^ | ← Rev. 10 →   +30 https://atcoder.jp/contests/arc106/submissions/17633994Depends on your definition of fancy, but I think both are needed.Solution: Swapping the order of summation, we first rewrite the sum as $\sum\limits_{i=0}^x \binom{x}{i} \sum\limits_{1\le L •  » » » 19 months ago, # ^ | +12 Consider using$\sum\limits_{i=1}^{k} something$notation.\sum\limits_{i=1}^{k} something •  » » » 19 months ago, # ^ | 0 sorry for silly question but i didn't understand the optimization can you please elaborate more or provide particular resource to learn this types of mathematics? •  » » » » 19 months ago, # ^ | ← Rev. 2 → 0 Here the topic is not related but you will have some idea on how to reduce this type of things. •  » » » » 19 months ago, # ^ | ← Rev. 2 → +2 $$\sum^N_{i=1}\sum^N_{j=i+1} (A_i+A_j)^X$$ $$=\frac{1}{2}\left(\sum^N_{i=1}\sum^N_{j=1} (A_i+A_j)^X — \sum_{i=1}^N(2A_i)^X\right)$$ $$=\frac{1}{2}\left(\sum^N_{i=1}\sum^N_{j=1} \sum^X_{p=0}\binom{X}{p}A_i^{X-p}A_j^p — \sum_{i=1}^N(2A_i)^X\right)$$ $$=\frac{1}{2}\left(\sum^X_{p=0}\binom{X}{p}\sum^N_{i=1}A_i^{X-p}\sum^N_{j=1} A_j^p — \sum_{i=1}^N(2A_i)^X\right)$$ If you pre-compute$\sum^N_{i=1} A_i^p$and$\sum_{i=1}^N(2A_i)^X$you can answer for each X in O(K). So the overall complexity of the final computation is O($K^2$).Submission •  » » » » » 19 months ago, # ^ | 0 thanks one last question we can separate the order of summation if i and j are both independent of each other? •  » » » » » » 19 months ago, # ^ | 0$\sum_{i=1}^N\sum_{j=1}^NA_iB_j=\left(A_1+A_2+....A_N\right)\left(B_1+B_2+....B_N\right)=\sum_{i=1}^NA_i\sum_{j=1}^NB_j$•  » » 19 months ago, # ^ | 0 Check this out https://www.geeksforgeeks.org/sum-of-absolute-difference-of-all-pairs-raised-to-power-k/ . Although its not exactly the same question, but by tweaking according to the constraints , you would get it .And yes, Binomial expansion :) •  » » » 19 months ago, # ^ | 0 thanks! •  » » 19 months ago, # ^ | 0 Can you please share your approach for C •  » » » 19 months ago, # ^ | +2 The only difference between the two approaches would happen is when one interval completely overlaps the other, as in$L_1,L_2,R_2,R_1$. If we have one "big interval" which contains$x$"small intervals", we can create a difference of$x-1$(draw and check, it'll be obvious). We can only create a positive difference, and at most a difference of$n-2$. Keep in mind the test case 1 0 •  » » » 19 months ago, # ^ | 0 Note$0\le M\le N-2$are achievable:Consider the construction$(1,2(M+2)),(2i,2i+1)_{i=1}^{M+1}$,$(2i-1,2i)_{i=M+3}^N$Now I claim$M\ge N-1$isn't. This would mean T can get$N$intervals but A can only get 1. This is impossible since this would imply all intervals are disjoint.I also claim$M\ge 0$. Assume the selection of T and A differs at some point. Then T has to be better because in the interval T and A choose to be different, the interval A chooses must contain the interval T chooses, so T's strategy is strictly better than A's. •  » » 19 months ago, # ^ | 0 Yes sir i did after 6 attempts thought it was overflow •  » » 19 months ago, # ^ | 0 only C(n,r)=C(n,n-r)is used  » 19 months ago, # | 0 What is wrong in my code for problem A..?https://atcoder.jp/contests/arc106/submissions/17622365 •  » » 19 months ago, # ^ | +2 It is unreadable. •  » » 19 months ago, # ^ | +8 Try n=6 =>answer is -1 but yours (0,1) •  » » » 19 months ago, # ^ | 0 vineetjai Thanks man...:)  » 19 months ago, # | +26 The curse of the testcase (1,0).  » 19 months ago, # | 0 How to solve B? •  » » 19 months ago, # ^ | ← Rev. 2 → +1 We break the graph into components. If in a connected component the sum of$a_i$s is the sum of$b_i$s, I can win by making$a_i=b_i$one by one.If the sum of$a_i$s is not the sum of$b_i$s, the answer is negative because the sum is an invariant.  » 19 months ago, # | +84 I think this is the first time I used Hall's theorem to successfully solve a problem. •  » » 19 months ago, # ^ | ← Rev. 5 → +16 Yeah you use it to solve E, where you consider$f(i)=$number of days worker$i$can work, and for any subset$T$of$[n]$, the number of days for which at least one worker in$T$works is$ \ge k|T|$.So we can binary search and find the answer. Unfortunately, I thought of this for E but ran out of time. •  » » » 19 months ago, # ^ | +6 The important thing is that the answer is at most$2KN+\mathrm{max}(A_i)$, which also follows from the theorem. This means we can bruteforce the exact set of workers on each day and checking the condition for binsearch becomes just doing subset sums on that. •  » » » » 19 months ago, # ^ | +6 2KN actually. After any time period T, every person will have worked at the very least T/2 time. You take all the times that at least a person in S has worked, which is at least T/2 and needs to be (according to hall) at least NK. I agree that one was the main observation, took me quite some time to get there. •  » » » » » 19 months ago, # ^ | 0 Very insignificant optimization, but$2KN-1$works by the same argument.  » 19 months ago, # | ← Rev. 2 → +14 Unofficial editorial for F (messy; is there a more elegant solution?)The sum of all degrees in a tree is$2n-2$. Therefore, if the total number of holes is less than$2n - 2$, the answer is clearly 0. From now on we assume that there are at least$2n-2$holes in total.Consider the Prüfer sequence of the tree. Observe that the degree of a node is equal to the number of times it occurs in the sequence, plus 1.Suppose we know what degree does each vertex have. Then, to count the number of ways, we first calculate the number of ways to put the nodes into a Prüfer sequence, then multiply that by the number of ways to match edges with holes.Call the degree of the$i$-th vertex$\mathrm{deg}_i$. The answer to the original problem can then be written as$\sum_{\mathrm{deg}_i \geq 1, \Sigma\mathrm{deg}_i = 2n-2} \frac{(n-2)!}{\prod_{i=1}^{n} (\mathrm{deg}_i - 1)!} \prod_{i=1}^{n} \frac{d_i!}{(d_i - \mathrm{deg}_i)!}$.Rearranging, we get$(n-2)!\sum_{\mathrm{deg}_i \geq 1, \Sigma\mathrm{deg}_i = 2n-2} \prod_{i=1}^{n} {d_i \choose \mathrm{deg}_i} \mathrm{deg}_i$.For each node$i$consider the generating function$\sum_{i=1}^{d_i} {d_i \choose i}ix^{i}$. It's not hard to see that the answer is the coefficient of$x^{2n-2}$when each of these generating functions are multiplied, times$(n-2)!$.It can be shown, that the generating function$\sum_{i=1}^{d_i} {d_i \choose i}ix^{i}$is equal to$d_{i}x(x+1)^{d_i - 1}$. Therefore, the product of these functions is equal to$x^n (x+1)^{\sum_{i=1}^{n} (d_i - 1)} \prod_{i=1}^{n} d_{i}$.We now remove the$x^n$factor, turning our problem to finding the coefficient of$x^{n-2}$in$(x+1)^{\sum_{i=1}^{n} (d_i - 1)} \prod_{i=1}^{n} d_{i}$. The product of all$d_i$is a constant, and we will remove it as well for now.The only remaining part is to find the coefficient of$x^{n-2}$in$(x+1)^{\sum_{i=1}^{n} (d_i - 1)}$. By the binomial theorem, it is equal to${{\sum_{i=1}^{n} (d_i - 1)} \choose {n-2}} = \frac{{\sum_{i=1}^{n} (d_i - 1)}!}{(n-2)!((\sum_{i=1}^{n} (d_i - 1)) - (n-2))!}$. The$(n-2)!$cancels with the factor that we need to multiply at the end, leaving us with$\frac{{\sum_{i=1}^{n} (d_i - 1)}!}{((\sum_{i=1}^{n} (d_i - 1)) - (n-2))!}$, which can easily be computed in$O(n)$time after finding$\sum_{i=1}^{n} (d_i - 1)$.Multiplying that by the product of all$d_i$(the constant that we previously removed), we get the answer. •  » » 19 months ago, # ^ | +37 Here's a combinatorial solution which only uses the fact that trees can be represented as Prufer sequences where degree of a node is equal to number of occurrences plus one:For a given tree, consider choosing holes for each edge one by one in arbitrary order. Each time we add an edge to a node$i$we must multiply the answer by$d_i - s_i$where$s_i$is the number of edges previously added to that node. All nodes have degree at least one so take$\prod(d_i)$of the initial values first and then decrement all$d_i$by one. This way we can simplify the problem to say that the final$s_i$is equal to the number of occurrences of$i$in the Prufer sequence exactly, and then multiply the original product of$d_i$into the answer,Now, we claim that the sum of this value across all Prufer sequences is equal to the number of permutations of$(\sum(d_i))$of length$(N-2)$(remember these$d_i$values are the decremented ones). It turns out that there's a nice bijection which shows that fact: imagine that we have balls of$N$colors where there are$d_i$balls of the$i$-th color. Then the Prufer sequence count is equivalent to repeatedly choosing a color, then choosing one of the balls of that color, and then removing it ($N-2$times total). But the step of choosing a color is irrelevant, so we can just phrase it as choosing$N-2$arbitrary balls in order from a set of$\sum(d_i)\$ balls total as desired.
•  » » 19 months ago, # ^ | ← Rev. 4 →   0 Here is my submission using Prufer code. What I had done is: Spoilerlet degree be D1,D2,....,Dn then c1,c2,c3,....,cn be times the vertexes appears in prufer codeso number of tree are for particular c1,c2,c3,....,cn => (n-2)!/(c1!c2!......cn!)select Di holes from di holes = (di)*(di-1)*.......*(di-ci)multiplying (di)*(di-1)*.......*(di-ci) for all i<=n and (n-2)!/(c1!c2!......cn!)gives ∏di * (n-2)! * for all ∑ci=n-2 ∑ Cr(d1-1,c1)* Cr(d2-1,c2)......... * Cr(dn-1,cn)let takesd1-1 d2-1 ....... dn-1 arrange in rows and we have to select ∑ci of them since ci>=0then it is eqauls to Cr(∑di-n,∑ci) => Cr(∑di-n,n-2)Total expression becomes:answer= ∏di * (n-2)! * Cr(∑di-n,n-2)answer= ∏di * (∑di-n)*(∑di-n-1).........(∑di-n-(n-3))
•  » » 19 months ago, # ^ |   0 Hi... I have heard of the prufer sequences for the first time .. And it seems gr8 , Do you have any other related questions using these type of techniques ? I want to learn them this time . Thanks..
 » 19 months ago, # |   0 how to solve c
•  » » 19 months ago, # ^ |   +3 Um_nik has a nice explanation in his screen cast here.
 » 19 months ago, # |   0 is there any editorial(official/unofficial) available for the contest?
 » 19 months ago, # |   +11 Will an editorial be uploaded anytime soon?
•  » » 19 months ago, # ^ |   +3 switch to Japanese version of atcoder and use google translator( until the official one comes out on english version.)
•  » » » 19 months ago, # ^ |   0 Thanks a lot. Really did not know that was possible.
 » 19 months ago, # |   0 Can anyone help me with the problem B, I am getting WA in some cases.This is my Code in Python https://atcoder.jp/contests/arc106/submissions/17717380