### hunter_of_alts's blog

By hunter_of_alts, 2 months ago,

You are given a number $n$, And we have two functions, We declare $P(S)$ for a set of numbers, product of all the numbers in the set, Also we declare $F(S)$ for a set of numbers, sum of all the numbers in the set, You have the set {$1, 2, 3, ... , n$} you have to calculate

$\sum_{i=1}^{2^{n}-1}(F(S_i)/P(S_i))$

for all non empty subsequences of {$1, 2, 3, ... , n$}, in the other words you have to provide a solution that calculates sum of $F(S)/P(S)$ for all non empty subsequences.

For example the answer for $n = 2$ is this :

• for {$1$} sum is $1$ and product of numbers in it is $1$ so $F(${$1$}$)/P(${$1$}$)$ is $1/1 = 1$

• for {$2$} sum is $2$ and product of numbers in it is $2$ so $F(${$2$}$)/P(${$2$}$)$ is $2/2 = 1$

• and for the last non empty subsequence {$1, 2$} sum is $3$ and product of the numbers in it is $2$ so $F(${$1, 2$}$)/P(${$1, 2$}$)$ is $3/2 = 1.5$

So the answer for $n = 2$ is $1 + 1 + 1.5 = 3.5$

# Constraints :

$1 \le n \le 10^6$

Solution

Hope you enjoy the problem, I'll share my approach's proof after $24$ hours!

• +39

 » 2 months ago, # |   +18 My solutionThe sum is equivalent to taking the sum of $\frac{x}{P(S_i)}$ over all $x$ and over all $S_i$ that contain $x$.For each $x$, the term is equivalent to summing the reciprocals of $P(X)$ over all $X$ that don't contain $x$, as the $x$-s will cancel out. This includes the empty set.It can be easily shown by induction that $\sum_{X \subseteq S} \frac{1}{P(X)} = \frac{\prod_{x \in S}{(x+1)}}{P(S)}$. So each term of the sum can be computed using this formula and prefix/suffix products.Complexity: $O(n)$ assuming $O(1)$ arithmetic.
•  » » 2 months ago, # ^ |   0 Thanks for the solution, Our solution's proof is almost the same but they're a bit different in total.
 » 2 months ago, # | ← Rev. 2 →   +12 Its pretty simple! I'll try to explain as simple as possible. First, for a set $S_i$ imagine splitting $F(S_i)/P(S_i)$. For example, if my set is $S = \{ 1,2,3 \}$. Then my splitting for $F(S)/P(S)$ will be: $1*(\frac{1}{1*2*3}) + 2*(\frac{1}{1*2*3}) + 3*(\frac{1}{1*2*3})$. Every such split has some coefficient of every number from $1$ to $n$. In this example coefficients are ($\frac{1}{6} , \frac{1}{6},\frac{1}{6},0,0..)$.What would be the coefficient of some number $i$ in my entire sum? It will be the in form $\sum(\frac{1}{P_j})$, where $P_j$ means the product of a subset having $i$. I sum this over all subsets containing $i$. So, imagine selecting some numbers from a bunch of $(\frac{1}{1},\frac{1}{2},\frac{1}{3},...\frac{1}{n})$ under the condition that $\frac{1}{i}$ must be selected, then adding them up. It is easy to see it will be $(1+\frac{1}{1})(1+\frac{1}{2})(1+\frac{1}{3})..(\frac{1}{i})..(1+\frac{1}{n})$. This is because while multiplying, every number $t$ (except $i$) has a choice of getting selected or rejected (hence, $1$ or $\frac{1}{t}$). However, we gotta select $\frac{1}{i}$, so I multiply my $\frac{1}{i}$.So, now we got the coefficient of number $i$. Final answer will be: $\sum i*Ci \text{ where,}$ $Ci = (1+\frac{1}{1})(1+\frac{1}{2})(1+\frac{1}{3})..(\frac{1}{i})..(1+\frac{1}{n})$Summing this up, everything will magically cancel out! (The Aha! moment) and you'll get the result :)
•  » » 2 months ago, # ^ |   -10 Nice! I wrote the title (Hard challenge) to encourage high rated people to open it :))
 » 2 months ago, # |   +3 After reading this type of blogs I always think that I am very bad at mathematics.How to be good. Anyone who can help?
•  » » 2 months ago, # ^ |   0 For such problems if you know some combinatorics, You will easily solve them, For example if you know what's Induction in this problem, You can easily solve it, Just learn basic mathematics subjects that are mostly used in the problems (At least in codeforces if you know what's ncr and (inclusion and exclusion), then you can solve half of the combinatorics problems!)
 » 2 months ago, # |   0 nice problem