hunter_of_alts's blog

By hunter_of_alts, 2 months ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +39
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +18 Vote: I do not like it
My solution
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it +12 Vote: I do not like it

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, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Nice! I wrote the title (Hard challenge) to encourage high rated people to open it :))

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

nice problem