brave-kid's blog

Little Nikita — Hard Version
By brave-kid, 5 months ago, In English

Original Problem

Same problem but I will ask how many valid ways to build $$$M$$$ cubes after $$$N$$$ moves mod $$$10^9 + 7$$$ and $$$N \le 10^5$$$.I know how to solve it when $$$N \le 10^3$$$ , that is through DP but how when $$$10^5$$$ ? Is it related with Catalan numbers??

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

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

Isn't it number of permutations of $$$\frac{n+m}2$$$ of +1's and $$$\frac{n-m}2$$$ -1's where current sum doesn't go $$$<0$$$?

→ Reply
  • »
    »
    5 months ago, # ^ |
    ← Rev. 7   Vote: I like it 0 Vote: I do not like it

    you are right , how to calculate that? oh cool I have just found out how to calculate I will just calculate for each index $$$x$$$ which is even and $$$x/2 \ge both:{(n+m)/2} , {(n-m)/2}$$$ : $$$C(x) * {N(max(n-(x+1),0),(n+m-x}/2))$$$ and sum them up , then total number of permutations — sum is my answer

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Turned out not so trivial as it seemed at first sight. Have you proved your formula/checked against bruteforce count?

      Because I have different formula by using Bertrand's ballot theorem: 

      let plus = (n + m) / 2;
let minus = (n - m) / 2;
let ans = ckn(minus, plus + minus) * (plus + 1 - minus) / (plus + 1);
      → Reply
      • »
        »
        »
        »
        5 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Ok so my solution :

        I am trying to find number of invalid rearrangements and then will deduct it from total rearrangements.So let's get into how to find count of invalid rearrangements :

        A rearrangement is invalid if at some index prefix sum becomes $$$< 0$$$ in other words exact $$$-1$$$ for the first time , so we will count for invalid rearrangements for each index in which its' prefix sum becomes -1 for the first time and then obviously sum them up , so now how to calculate for each index : let's index is $$$x$$$ then upto index $$$x-1$$$ we can apply the formula of Catalan numbers as end result is 0 and equal count of $$$1$$$ and $$$-1$$$.And obviously in index $$$x$$$ we put a $$$-1$$$ if it's still available and then however we arrange the rest of the numbers doesn't matter.So I think this solution should be correct.You have any counter statement?

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

          Idea to exclude invalid permutations is reasonable, but I'm not sure how to logically evaluate your way to count it.

          Check against some random example n=20 m=12 ans=3705

          → Reply
    • »
      »
      »
      5 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      you can calculate using same logic as for calculating catalan numbers. I guess it will be something like $$$\binom{n}{\frac{n-m}{2}} - \binom{n}{\frac{n-m}{2} - 1}$$$.

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

        can you please explain how you derived it?

        → Reply
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          as was mentioned in comments earlier you need to calculate number of permutations $$$\frac{n+m}{2}$$$ 1 and $$$\frac{n - m}{2}$$$ -1 where doesn't exist prefix with negative sum. How many permutations of 1 and -1 exist? $$$\binom{n}{\frac{n - m}{2}}$$$. But some of them are bad.

          Now we need to count bad permutations. Any bad permutation will have prefix with sum -1 (because should exist prefix with negative sum, and every number is either 1 or -1). Let's replace every -1 with 1 and every 1 to -1 in this prefix. What happened? Number of -1 decreased by 1. So number of bad permutations is same as number of permutations with $$$\frac{n+m}{2} - 1$$$ 1 and $$$\frac{n - m}{2}$$$ -1, which is $$$\binom{n}{\frac{n - m}{2} - 1}$$$.

          Now we have answer: $$$\binom{n}{\frac{n - m}{2}} - \binom{n}{\frac{n - m}{2} - 1}$$$

          → Reply
»
5 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This can be interpreted as number of valid parentheses of length $$$n-m$$$, which equals to $$$\frac{(n-m)}{2}^{th}$$$ Catalan number

→ Reply