__fn__'s blog

By __fn__, history, 3 months ago, In English

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

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

Auto comment: topic has been updated by __fn__ (previous revision, new revision, compare).

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

Is there any link to the problem?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Unfortunately the link the contest is broken. It was a contest organised back to November 2022 on codechef.

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

I think this is DP

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    O(n)DP?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

          If I’m right then your formula is incorrect, the answer when n=10 should be 6.

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            yeah it is i amm sure

            • »
              »
              »
              »
              »
              »
              »
              3 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Your formula seems incorrect. For $$$n = 10$$$ the answer is $$$6$$$

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        no need for dp just formula as i said in the comment below

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

    What’s GF? And is a $$$O(nlogn)$$$ solution possible to pass when n is $$$5\times 10^8$$$?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Generating function. It can't pass the tests :(

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

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

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

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

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

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

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

              Thanks a lot. I fully understand now

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Do you also think that the algorithm which run in $$$O(\sqrt{n})$$$ can be implemented for cp use?

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

Auto comment: topic has been updated by __fn__ (previous revision, new revision, compare).

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

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

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..

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    They don't follow the Fibonacci sequence, because why would they? For n = 14 the answer is 14 not 16:

    1. 14 = 12 + 2
    2. 14 = 10 + 4
    3. 14 = 10 + 2 + 2
    4. 14 = 8 + 6
    5. 14 = 8 + 4 + 2
    6. 14 = 8 + 2 + 2 + 2
    7. 14 = 6 + 6 + 2
    8. 14 = 6 + 4 + 4
    9. 14 = 6 + 4 + 2 + 2
    10. 14 = 6 + 2 + 2 + 2
    11. 14 = 4 + 4 + 4 + 2
    12. 14 = 4 + 4 + 2 + 2 + 2
    13. 14 = 4 + 2 + 2 + 2 + 2 + 2
    14. 14 = 2 + 2 + 2 + 2 + 2 + 2 + 2
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by __fn__ (previous revision, new revision, compare).