Thursday, 1 August 2013

Sticky Sticks Hexagon Game in C#

Problem Statement

Rajesh is playing a very interesting mathematical game. He has collection of sticks of length 1,2,3,....,N. He is making hexagon out of his collection by using 6 sticks for each hexagon. He considers a hexagon "good" if the biggest stick has length at least L and lengths of all the other sticks are not more than X.A "good" hexagon does not have sticks of the same length more than K times. 
How many ways he can make a "Good" hexagon?

Input/Output Specs

Input Specification:Input contains four integers-
N( 2 <= N <= 10^9)
L ( 2 <= L <= N
 and N-L<=100)
X( 1<=X< L )
K ( 1 <= K <= 5)


Output Specification:

Output the number of different ways to make a "Good" hexagon% 1000000007

Examples

Example:1 when N=8, L=7, X=5, K=3: { 1,2,2,5,5,7 } is a good hexagon but {1,2,2,2,2,7}, { 1,2,3,4,5,6},{1,2,3,4,6,7} are not.Two hexagons are considered different if their side length sets are different.

For example
 {1,2,3,4,5,6} , {1,1,1,2,2,3} and {1,1,2,2,2,3} are all different hexagons. But {1,2,3,4,5,6} and { 2,4,6,1,3,5} are not different.

Example:2 When N=10, L=8, X=6, K=2
Output:       Total hexagons= 374

Note: Please return -1 for invalid cases.

One point we need to understand, in irregular hexagon sum of all other sides must be greater than the bigger side stick length then only it is consider as Good Hexagon

using System.IO;
using System;
using LL = System.Int64;
using System.Collections.Generic;

public class CandidateCode
{

    static LL MOD = 1000000007;
    static LL N, K, L, X;



    static LL gcd(LL a, LL b)
    {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    static LL[] arr = new LL[10];


    static LL nck(LL n, LL k)
    {
        LL i, j, d;
        LL ret = 1;
        if (k > n) return 0;
        for (i = 0; i < k; i++) arr[i] = n - i;
        for (i = 2; i <= k; i++)
            for (d = i, j = 0; j < k; j++)
            {
                LL g = gcd(arr[j], d);
                arr[j] /= g; d /= g;
            }
        for (i = 0; i < k; i++) ret = (((LL)ret * arr[i]) % MOD);
        return ret;
    }



    static LL calcAll(LL n, LL x, LL k)
    {
        LL ret = 0;
        LL i;
        if (x == 0) return nck(n, k);
        for (i = 1; i <= x && i <= K; i++)
            ret = ((ret + calcAll(n, x - i, k + 1)) % MOD);

        return ret;
    }



    static void gen(LL pos, LL carry, LL pattern, LL c, LL sum, LL val, LL idx)
    {
        LL i;

        if (pos == 5)
        {
            if ((sum / 10) != carry) return;
            LL x = carry * total + pattern, y = c * total + ids[val], d = sum % 10;
            cnt1[(vals[0] % 10), d, x, y, 0]++;
            if ((vals[4] % 10) == 0) cnt1[(vals[0] % 10), d, x, y, 1]++;
            return;
        }

        for (i = 0; i <= 9; i++)
        {
            if ((sum + i) / 10 > carry) break;
            vals[pos] = pat[pos] * 10 + i;
            if ((pos != 0) && (vals[pos] > vals[pos - 1]))
                break;
            LL nidx = ((pos == 0) || (vals[pos] == vals[pos - 1])) ? idx : idx - 1;
            gen(pos + 1, carry, pattern, c, sum + i, (val * 10 + nidx), nidx);
        }
    }


    static List<Int64> now = new List<Int64>();
    static LL[][] states = new LL[20][];
    static LL[] ids = new LL[100000];
    static LL[] valid = new LL[80];
    static LL total;
    static LL[, ,] next = new LL[2, 85, 85];
    static LL[,] size = new LL[2, 85];

    static void genStates(LL pos, LL val, LL last) // generates all possible encodings
    {
        if (pos == 5)
        {
            ids[val] = total;

            states[total++] = now.ToArray();

            return;
        }
        now[(int)pos] = last;
        genStates(pos + 1, val * 10 + last, last);
        if (pos != 0) { now[(int)pos] = last - 1; genStates(pos + 1, val * 10 + last - 1, last - 1); }
    }


    static LL[, , , ,] cnt1 = new LL[10, 10, 85, 85, 2];
    static LL[, , , ,] cnt2 = new LL[10, 10, 85, 85, 2];
    static LL[, , , ,] cnt3 = new LL[10, 10, 85, 85, 2];
    static LL[, , , ,] cnt4 = new LL[10, 10, 85, 85, 2];
    static LL[] vals = new LL[10];
    static LL[] pat = new LL[10];


    static LL preCalc(LL i, LL j, LL k, LL l, LL x)
    {
        LL cc = cnt1[k, l, i, j, x];
        LL cd = ((k != 0) && (l != 0)) ? cnt4[k - 1, l - 1, i, j, x] : 0;
        LL ca = (l != 0) ? cnt2[k, l - 1, i, j, x] : 0;
        LL cb = (k != 0) ? cnt3[k - 1, l, i, j, x] : 0;

        cnt2[k, l, i, j, x] = ca + cc;
        cnt3[k, l, i, j, x] = cb + cc;
        cnt4[k, l, i, j, x] = ca + cb + cc + cd;

        return ca + cb + cc + cd;
    }

    static void make(LL carry, LL pattern) // compute the edges
    {
        LL i, j, k, l, x = carry * total + pattern;

        for (i = 0; i < 5; i++)
        {


            pat[i] = states[pattern][i];
        }

        for (i = 0; i < 5; i++)
            gen(0, carry, pattern, i, i, 0, 9);

        for (i = x, j = 0; j < 80; j++)
        {
            LL ok1 = 0, ok2 = 0;
            for (k = 0; k <= 9; k++)
                for (l = 0; l <= 9; l++)
                {
                    if (preCalc(i, j, k, l, 0) != 0) ok1 = 1;
                    if (preCalc(i, j, k, l, 1) != 0) ok2 = 1;
                }
            if (ok1 != 0) next[0, x, (size[0, x]++)] = j;
            if (ok2 != 0) next[1, x, (size[1, x]++)] = j;
        }
    }


    static LL[, , ,] memo = new LL[12, 2, 2, 85];
    static LL[, , ,] seen = new LL[12, 2, 2, 85];
    static LL length, cnt;
    static LL[] MM = new LL[15];
    static LL[] XX = new LL[15];

    static LL solve(LL pos, LL prefixX, LL prefixM, LL x, LL z)
    {
        LL i, ret = 0;

        if (pos == length) return valid[x];
        if (seen[pos, prefixX, prefixM, x] == cnt) return memo[pos, prefixX, prefixM, x];

        LL a = XX[pos], b = MM[pos];

        for (i = 0; i < size[z, x]; i++)
        {
            LL y = next[z, x, i];

            if ((prefixX != 0) && (prefixM != 0))
            {
                if (cnt1[a, b, x, y, z] != 0)
                    ret = ((ret + (LL)cnt1[a, b, x, y, z] * solve(pos + 1, 1, 1, y, z)) % MOD);
                if ((b != 0) && (cnt2[a, b - 1, x, y, z] != 0))
                    ret = ((ret + (LL)cnt2[a, b - 1, x, y, z] * solve(pos + 1, 1, 0, y, z)) % MOD);
                if ((a != 0) && (cnt3[a - 1, b, x, y, z] != 0))
                    ret = ((ret + (LL)cnt3[a - 1, b, x, y, z] * solve(pos + 1, 0, 1, y, z)) % MOD);
                if ((a != 0) && (b != 0) && (cnt4[a - 1, b - 1, x, y, z] != 0))
                    ret = ((ret + (LL)cnt4[a - 1, b - 1, x, y, z] * solve(pos + 1, 0, 0, y, z)) % MOD);
            }

            if ((prefixX != 0) && (prefixM == 0))
            {
                if (cnt2[a, 9, x, y, z] != 0)
                    ret = ((ret + (LL)cnt2[a, 9, x, y, z] * solve(pos + 1, 1, 0, y, z)) % MOD);
                if ((a != 0) && (cnt4[a - 1, 9, x, y, z] != 0))
                    ret = ((ret + (LL)cnt4[a - 1, 9, x, y, z] * solve(pos + 1, 0, 0, y, z)) % MOD);
            }

            if ((prefixX == 0) && (prefixM != 0))
            {
                if (cnt3[9, b, x, y, z] != 0)
                    ret = ((ret + (LL)cnt3[9, b, x, y, z] * solve(pos + 1, 0, 1, y, z)) % MOD);
                if ((b != 0) && cnt4[9, b - 1, x, y, z] != 0)
                    ret = ((ret + (LL)cnt4[9, b - 1, x, y, z] * solve(pos + 1, 0, 0, y, z)) % MOD);
            }

            if ((prefixX == 0) && (prefixM == 0))
            {
                if (cnt4[9, 9, x, y, z] != 0)
                    ret = ((ret + (LL)cnt4[9, 9, x, y, z] * solve(pos + 1, 0, 0, y, z)) % MOD);
            }
        }

        seen[pos, prefixX, prefixM, x] = cnt;
        return memo[pos, prefixX, prefixM, x] = ret;
    }




    static LL calc(LL X, LL M, LL z)
    {
        LL ret = 0;

        ++cnt;
        length = 0;

        while ((X != 0) || (M != 0))
        {
            XX[length] = X % 10;
            MM[length] = M % 10;
            X /= 10; M /= 10;
            length++;
        }

        if (length > 1)
        {
            for (LL i = 0; i < length / 2; i++)
            {
                LL temp = XX[i];
                XX[i] = XX[(length - 1) - i];
                XX[(length - 1) - i] = temp;

            }

            for (LL i = 0; i < length / 2; i++)
            {
                LL temp = MM[i];
                MM[i] = MM[(length - 1) - i];
                MM[(length - 1) - i] = temp;

            }   
        }

        ret = (solve(0, 1, 1, 0, z));
        return ret;
    }



    static LL calc()
    {
        LL ret = 0;
        LL i;
        LL p = ((calcAll(X, 5, 0)) % MOD);
        for (i = L; i <= N; i++)
        {
            LL q = ((calc(X, i, 0) - calc(X, i, 1)) % MOD);
            ret = (ret + (p - q) % MOD) % MOD;
        }
        if (ret < 0) ret += MOD;
        return ret;
    }





    public static int goodHexa(Int64 input1, Int64 input2, Int64 input3, Int64 input4)
    {
        N = input1; L = input2; X = input3; K = input4;
        LL ans;


        if (N >= 2 && N <= (Math.Pow(10, 9)) && (N - L <= 100) && L >= 2 && L <= N && X >= 1 && X < L && K >= 1 && K <= 5)
        {  
            now.Add(0); now.Add(0); now.Add(0); now.Add(0); now.Add(0);
            LL i, j, a;
            genStates(0, 0, 9);
            for (i = 0; i < 5; i++)
                for (j = 0; j < 16; j++)
                    make(i, j);



            for (i = 0; i < total; i++)
            {
                LL cnt = 0, ok = 1;
                for (j = 0; j < 5; j++)
                {

                    if (j == 0)
                    {
                        a = 0;
                    }
                    else
                        a = states[i][j - 1];

                    if ((j == 0) || (states[i][j] != a))
                        cnt = 1;
                    else
                        cnt++;

                    if (cnt > K) ok = 0;
                }
                if (ok != 0)
                    valid[i] = 1;
            }

            ans = calc();
        }
        else
        {
            ans = -1;

        }

        return (int)ans; 
    }

}