big fan sir

excited to participate CFBR

Intimidation power of a person is at most 3. If $$$dp_i$$$ denotes maximum power for suffix starting from $$$i$$$, it is always in form $$$2^a3^b$$$. So, for each index, try all 3 ways and update correspoding dp value.

Thank you providing feedback for each problem. It really helps when preparing future contests.

Here is my take on CAPATHS :

Lets consider simple problem where we have to find a path having maximum sum. That is standard dp on trees.

Now we can formulate the original problem as :

Given a tree where each node has a pair {x,y} where x is 0/1. Find a path having maximum sum of y values such that xor of x values is 0. We can use standard dp on trees while maintaining maximum sum for xor 0 and 1.(+ve and -ve)

Will it be possible for you to give cf ratings to these problems?

For DLTNODE, I think the idea was nice, but the problem was made unecessarily hard for people who don't know segment trees/ sparse tables. Moreover it didn't actually contribute to the problem in any way.

maximal => If you have 000111, you cant take the substring [1, 2] or similar. Formally, you have to take an entire block $$$[l, r]$$$ such that

• $$$s_l = s_{l + 1} = \ldots = s_{r}$$$
• $$$l = 1$$$ or $$$s_{l - 1} \ne s_{l}$$$
• $$$r = |S|$$$ or $$$s_{r} \ne s_{r + 1}$$$

Prereq — Euler tours, sparse table/seg tree

Root the tree at Node 1. Do an euler tour of the tree. Now when your destroy a node, the components that will be formed are subtrees of its children, and the part of the tree that remains after removing the subtree of the current node. With the help of euler tours, subtrees are transformed into ranges and GCD can be calculate with sparse table.

I used dp+ prefix and suffix arrays.

Ok wow that is pretty cool. Its unfortunate that the sparse table / segtree approach exists, the intended approach is pretty nice.

It can be proved using multinomial theorem, Let's say you have r numbers whose sum is less than n $$$y1+y2+y3+\dots+yr<=n$$$

Now we can add one more number which will always have the difference between sum of first r numbers and n. $$$y1+y2+y3+\dots+y(r+1)=n$$$.

Let's say $$$k = r+1$$$

Now we're going to express all the options available for first group as powers of x.

So for first group -> $$$x^{0}+x^{1}+x^{2}+x^{3}+x^{4}+\dots+x^{n}$$$.

You can read this as either it can have value 0 or 1 or 2 or 3 or 4 or $$$\dots$$$ or n Now similarily you can write this for all k groups and multiply them. $$$((x^{0}+\dots+x^{n})\times(x^{0}+\dots+x^{n})\times \dots \times(x^{0}+\dots+x^{n}))$$$.

When multiplying these expressions what we do manually is we select some power of x from first group some power of x from second and so on and find out the resulting power of x and add that term in the final answer, right?

That's what you will be doing in this questions as well right choosing some power of x for first group, some power of 2nd, some power for 3rd and so on and take the sum of all powers to find out the resulting power and add it to the final answer. Each multiplication will add 1 to the $$$x^{sum of all powers}$$$ i.e. 1 number of way to make sum equal to this power.

So the above expression can be written as $$$(x^{0}+\dots+x^{n})^{k}$$$.

We have to find the coefficient of $$$x^{n}$$$ in this expression and that will be the resulting answer.

$$$x^{0}+x^{1}+\dots+x^{n}$$$ forms a G.P. So it will be equal to $$$\dfrac{1-x^{n+1}}{1-x}$$$. We have to find $$$x^{n}$$$ in $$$(\dfrac{1-x^{n+1}}{1-x})^{k}$$$. Now from numerator we will only need $$$x^{0}$$$ as all other powers will not be useful to us because all of them will be greater than n.

Coefficient of $$$x^{0}$$$ is 1 in numerator.

Expanding $$$(1-x)^{-k}$$$,

$$$(1-x)^{-k}=1+\dfrac{k}{1!}\times x^{1}+\dfrac{k*(k+1)}{2!} \times x^{2}+\dfrac{k*(k+1)*(k+2)}{3!} \times x^{3} +\dots$$$

Now you can easily observe that power of $$$x^{p}$$$ is $$$\binom{p+k-1}{k-1}$$$ and therefore the resulting coefficient of x^{n} will be

$$$\binom{n+k-1}{k-1}$$$

After putting $$$k = r+1$$$ we get $$$\binom{n+r}{r}$$$

For contest you just have to remember the formula for number of ways to choose r numbers to have sum equal to n. That is $$$\binom{n+r-1}{r-1}$$$. Now you just have to think about taking difference in the sum as well to make sum equal to n and not less than n.Then you will have r+1 numbers whose sum will be equal to n.