We will hold AtCoder Regular Contest 106.
- Contest URL: https://atcoder.jp/contests/arc106
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20201024T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: beet, tempura0224, heno239, kort0n
- Rated range: ~ 2799
- The point values will be 300-400-500-600-700-800.
We are looking forward to your participation!
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.
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?
https://atcoder.jp/contests/arc106/submissions/17633994
Depends on your definition of fancy, but I think both are needed.
Solution: Swapping the order of summation, we first rewrite the sum as
Now observe $$$\binom{x}{i}=\binom{x}{x-i}$$$ and
For each
we precompute
in $O(NK)$ and do the final computation in $$$O(K^2)$$$.
Consider using $$$\sum\limits_{i=1}^{k} something$$$ notation.
\sum\limits_{i=1}^{k} somethingsorry 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?
Here the topic is not related but you will have some idea on how to reduce this type of things.
\begin{equation} \sum^N_{i=1}\sum^N_{j=i+1} (A_i+A_j)^X \end{equation} \begin{equation} =\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) \end{equation} \begin{equation} =\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) \end{equation} \begin{equation} =\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) \end{equation} 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
thanks one last question we can separate the order of summation if i and j are both independent of each other?
$$$\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$$$
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 :)
thanks!
Can you please share your approach for C
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 0Note $$$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.
only
C(n,r)=C(n,n-r)is usedWhat is wrong in my code for problem A..?
https://atcoder.jp/contests/arc106/submissions/17622365
It is unreadable.
Try n=6 =>answer is -1 but yours (0,1)
The curse of the testcase (1,0).
How to solve B?
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.
I think this is the first time I used Hall's theorem to successfully solve a problem.
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.
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.
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.
Very insignificant optimization, but $$$2KN-1$$$ works by the same argument.
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.
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.
Here is my submission using Prufer code. What I had done is:
let degree be D1,D2,....,Dn then c1,c2,c3,....,cn be times the vertexes appears in prufer code
so 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 takes
d1-1 d2-1 ....... dn-1 arrange in rows and we have to select ∑ci of them since ci>=0
then 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))
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..
how to solve c
Um_nik has a nice explanation in his screen cast here.
is there any editorial(official/unofficial) available for the contest?
Will an editorial be uploaded anytime soon?
switch to Japanese version of atcoder and use google translator( until the official one comes out on english version.)
Thanks a lot. Really did not know that was possible.
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