__fn__'s blog

By __fn__, history, 3 months ago,

You are given an integer $n \leq 10^9$. Your task is to compute the number of ways $n$ can be expressed as the sum of even numbers. Since the answer could be very large, compute it modulo $10^9 + 7$.

Time limit : 1s

Sample : $n = 8$

$8 = 6 + 2$

$8 = 4 + 4$

$8 = 4 + 2 + 2$

$8 = 2 + 2 + 2 + 2$

Therefore for $n = 8$ the answer would be $4$

Do anyone know how to solve this problem? Comment on the solution

UPDATE Thanks to Wielomian and estoy-re-sebado for sharing some ways to solve this problem

Solution
• +4

 » 3 months ago, # |   0 Auto comment: topic has been updated by __fn__ (previous revision, new revision, compare).
 » 3 months ago, # |   0 Is there any link to the problem?
•  » » 3 months ago, # ^ |   0 Unfortunately the link the contest is broken. It was a contest organised back to November 2022 on codechef.
 » 3 months ago, # |   0 I think this is DP
•  » » 3 months ago, # ^ |   0 O(n)DP?
•  » » » 3 months ago, # ^ |   0 To be honest, I just read this problem. I am sure that this problem can be solved using DP, or combinatorics, depending on time constraints.
•  » » » » 3 months ago, # ^ | ← Rev. 6 →   0 well i think it is just $2^\frac{n-4}{2}$ kind of obvious the formula and then divide by two to avoid double counting for sure the answer for 2 is one
•  » » » » » 3 months ago, # ^ | ← Rev. 3 →   0 The answer for 2 should be 0 since only n itself is not consider as an answer as shown in sample.By the way is there any proof of the formula?
•  » » » » » 3 months ago, # ^ |   0 If I’m right then your formula is incorrect, the answer when n=10 should be 6.
•  » » » » » » 3 months ago, # ^ |   0 yeah it is i amm sure
•  » » » » » » » 3 months ago, # ^ |   0 Your formula seems incorrect. For $n = 10$ the answer is $6$
•  » » » » 3 months ago, # ^ |   0 no need for dp just formula as i said in the comment below
•  » » » » 3 months ago, # ^ |   0 Dp with an upper bound of n that is 1e9 and time limit 1s i think you will get MLE or TLE
 » 3 months ago, # |   +11 If $n$ is odd, the answer is $0$. Else you can divide $n$ by $2$, so we can rewrite the problem as:Compute the number of ways $n$ can be expressed as the sum of positive numbers which are strictly less than $n$.This is a classical problem. You could solve it with GF in $\mathcal O(n \log n)$. I don't know if a better solution exists.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 What’s GF? And is a $O(nlogn)$ solution possible to pass when n is $5\times 10^8$?
•  » » » 3 months ago, # ^ |   +1 Generating function. It can't pass the tests :(
•  » » » 3 months ago, # ^ |   -7 What's GF? This is one of the most difficult problems in competitive programming. I don't think that anyone on Codeforces has been able to solve it yet.
•  » » 3 months ago, # ^ |   0 After division by $2$, what remains from the right-hand side are exactly the partitions, so the answer is $p(n / 2) - 1$. The Wikipedia article even shows the same example as in the problem statement, after the division by $2$.The computation of $p(n)$ can be done roughly in $O(\sqrt{n})$ complexity, by a somehow convoluted combinatorial argument, see this stackexchange thread.
•  » » » 3 months ago, # ^ |   0 Can you explain why this problem is equal to the partition one? I generated answers up to $150$ for my problem and I was able to see that the terms of those two series are different just by 1 but I still don't know why.
•  » » » » 3 months ago, # ^ |   0 A partition is pretty much what the problem asks, by definition. From Wikipedia: In number theory and combinatorics, a partition of a non-negative integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. The one leftover is when you express $n$ as $n$ and not as a sum, which the definition of partition allows but the problem doesn't.
•  » » » » » 3 months ago, # ^ |   0 Ok but in standard when doing a partition we can use all numbers that are less than the number that is being partitioned. But in this problem, we are only allowed to use even number so how do you do the transition from general case to this restriction.
•  » » » » » » 3 months ago, # ^ |   0 Consider a partition of $m$. So we have $m = a + b + c$ for example. Now multiply both sides by two. Then we have $2m = 2a + 2b + 2c$. If we let $n = 2m$ (in other words let n be an even number) then we have $n = 2a + 2b + 2c$, and we have expressed $n$ as a sum of even numbers. QED.
•  » » » » » » » 3 months ago, # ^ |   0 Thanks a lot. I fully understand now
•  » » » 3 months ago, # ^ |   0 Do you also think that the algorithm which run in $O(\sqrt{n})$ can be implemented for cp use?
•  » » » » 3 months ago, # ^ |   0 I don't think that this algorithm is usable for any problem with rating below 3000. It's rather a technical, mathematical curiosity. If you want to know something about computing the partition number function, the usual way is a dp by direct application of Euler's Pentagonal Number Theorem. This allows to compute all $p(n)$s up to some $N$ in time $O(N \sqrt{N})$ (as pentagonal numers grow quadratically).
•  » » » » » 3 months ago, # ^ |   0 Ok. I finally managed to implement the one with $dp$ using $\sum{p_{k}(n)}$ in $O(N^2)$ yesterday. I have just checked about the pentagonal number and we can achieve that time complexity of $O(N\sqrt{N})$ you have mentioned. $Thanks !!$
 » 3 months ago, # |   0 Auto comment: topic has been updated by __fn__ (previous revision, new revision, compare).
 » 3 months ago, # |   0 Maybe there's something that can be done by first writing it as a sum of n/2 2s, then computing the ways you can group them together? Not sure though
 » 3 months ago, # | ← Rev. 6 →   -16 Basically the answers form a fibonacci sequence ,, for: n= 6 ans=2, n=8 ans=4, n=10 ans=6, n=12 ans=10, n=14 ans=16, n=16 ans=26,you can find the ans using optimize fibonacci function .Complexity of optimize fibonacci function for this problem is log(n/2) but you have to handle corner case for n=2,n=4 for n=2 ans=0 for n=4 ans=1Please inform me if my solution is not correct thanks..
•  » » 3 months ago, # ^ |   +10 They don't follow the Fibonacci sequence, because why would they? For n = 14 the answer is 14 not 16: 14 = 12 + 2 14 = 10 + 4 14 = 10 + 2 + 2 14 = 8 + 6 14 = 8 + 4 + 2 14 = 8 + 2 + 2 + 2 14 = 6 + 6 + 2 14 = 6 + 4 + 4 14 = 6 + 4 + 2 + 2 14 = 6 + 2 + 2 + 2 14 = 4 + 4 + 4 + 2 14 = 4 + 4 + 2 + 2 + 2 14 = 4 + 2 + 2 + 2 + 2 + 2 14 = 2 + 2 + 2 + 2 + 2 + 2 + 2
 » 3 months ago, # |   0 Auto comment: topic has been updated by __fn__ (previous revision, new revision, compare).