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
Auto comment: topic has been updated by __fn__ (previous revision, new revision, compare).
Is there any link to the problem?
Unfortunately the link the contest is broken. It was a contest organised back to November 2022 on codechef.
I think this is DP
O(n)DP?
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.
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
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?
If I’m right then your formula is incorrect, the answer when n=10 should be 6.
yeah it is i amm sure
Your formula seems incorrect. For $$$n = 10$$$ the answer is $$$6$$$
no need for dp just formula as i said in the comment below
Dp with an upper bound of n that is 1e9 and time limit 1s i think you will get MLE or TLE
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.
What’s GF? And is a $$$O(nlogn)$$$ solution possible to pass when n is $$$5\times 10^8$$$?
Generating function. It can't pass the tests :(
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.
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.
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.
A partition is pretty much what the problem asks, by definition. From Wikipedia:
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.
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.
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.
Thanks a lot. I fully understand now
Do you also think that the algorithm which run in $$$O(\sqrt{n})$$$ can be implemented for cp use?
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).
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 !!$$$
Auto comment: topic has been updated by __fn__ (previous revision, new revision, compare).
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
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=1
Please inform me if my solution is not correct thanks..
They don't follow the Fibonacci sequence, because why would they? For n = 14 the answer is 14 not 16:
Auto comment: topic has been updated by __fn__ (previous revision, new revision, compare).