1145 - Dice (I)

PDF (English)

Statistics

Forum

Time Limit: 2 second(s)

Memory Limit: 32 MB

You have N dices; each of them has K faces numbered from 1 to K. Now you have arranged the N dices in a line. You can rotate/flip any dice if you want. How many ways you can set the top faces such that the summation of all the top faces equals S?

Now you are given N, K, S; you have to calculate the total number of ways.

Input

Input starts with an integer T (≤ 25), denoting the number of test cases.

Each case contains three integers: N (1 ≤ N ≤ 1000), K (1 ≤ K ≤ 1000) and S (0 ≤ S ≤ 15000).

Output

For each case print the case number and the result modulo 100000007.

Input                                                                                 

5                               

1 6 3

Case 1: 1

2 9 8   

Case 2: 7

500 6 1000

Case 3: 57286574

800 800 10000 

Case 4: 72413502

2 100 10

Case 5: 9    

First of all let us observe few things

(1)  The normal approach is to memoize it using dp[position][sum] and at that position try to fit all the values from 1 to K and recursively call the function. This gives us a solution on 0(n*s*k) somplexity, which is not sufficeient to pass.

Now we can observe that suppose we want the sum at position p to be 

SUM then what all values the i-1 th dice have as sum i.e it can 

have all values from  sum-1 to sum-k obviously there are few cases 

where the sum cannot be less than 1 and the previous dies total sum has to be >=(diecount) till there. But the overall idea is for that we can maintain a prefix array whose sum we can query in o(1) time.

A normal 2d array showed memory limit hence it was optimised to 1d array.

               

See the code for detailed implementation                                                     

                            

               ****** My code goes here**************

#include<bits/stdc++.h>

using namespace std;

long long int  dp[15100];

#define mod 100000007

int n,k,s;

long long int pre[15100];

int main()

{

   int t;

   cin>>t;

   int tt=1;

   while(t--)

   {

              memset(dp,0,sizeof(dp));   

      scanf("%d %d %d",&n,&k,&s);

     //  cout<<"called "<<endl;

          for(int i=1;i<=k;i++)

          dp[i]=1;

         memset(pre,0,sizeof(pre));

          for(int i=1;i<=k;i++)

          {

              pre[i]=pre[i-1];

pre[i]+=dp[i];

// if(pre[i]>=mod)

// pre[i]%=mod;

  }

 // cout<<"pre "<<endl;

// for(int i=1;i<=k;i++)

// cout<<pre[i]<<" ";

  for(int dice=2;dice<=n;dice++)

  {

  // cout<<"dice "<<dice<<endl;

          for(int sum=dice;sum<=min(dice*k,s);sum++)

          {

           

            int right=min(sum-1,(dice-1)*k);

            int left=max(dice-1,sum-k);

  //          cout<<"sum "<<sum<<" l r "<<left<<" "<<right<<endl;

  dp[sum]=(pre[right]-pre[left-1]+mod)%mod;

  //           cout<<"dp "<<dice<<" "<<sum<<" "<<dp[dice][sum]<<endl;

            //dp[dice][sum];

           // dp[dice][sum]%=mod;

          }

memset(pre,0,sizeof(pre));

for(int i=dice;i<=min(dice*k,s);i++)

{

   pre[i]=pre[i-1];

   pre[i]+=dp[i];

    if(pre[i]>=mod)

   pre[i]%=mod;

}

 

// cout<<endl;

  }

//  for(int i=6;i<=11;i++)

 /// cout<<dp[2][i]<<endl;

  

       cout<<"Case "<<tt<<": "<<dp[s]<<endl;

    tt++;

}

return 0;

}                                  

Random Rudreshwar  Problem code: ANURRZ

MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

Read problems statements in Mandarin Chinese and Russian as well.

Problem description

Rudreshwar likes random numbers and random arrays. Today Rudreshwar started playing with a couple of Arrays A and B, each of size N.

Initially A is filled with zeros. Rudreshwar filled B with random numbers.

Rudreshwar visits each index i (1 <= i <= N) in random order. When at i, he selects another random index jsuch that j is greater or equal to i. He then increments A[i], A[i+1], A[i+2] ... A[j] by 1.

Finally if for any index i, A[i] is greater than B[i], he then throws away that array A

For a given B, calculate the number of different arrays A, that Rudreshwar can end up with. Two arrays are called different if there exists an index where the arrays have different values

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. First line of each test case contains an integer N. Second line contains N space separated integers representing the array B

Output

For each test case, output a single line containing the required answer modulo 1000000007.

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 1000
• 1 ≤ B[i] ≤ N

Example

Input:
2
2
2 2
3
1 1 1

Output:
2
1

Explanation

Test case 1

{1, 1} and {1, 2} are valid.

Test case 2

{1, 1, 1} is the only possible final array A.

Explanation

Here the DP state is quite unusual. First let us go with few observations

(1)   The maximum value of any index b[i] can be equal to i and not more.

(2)  The dp state is dp[i][j] which denotes that index i is chosen to be updated j times by indices before(including) it.

Standard explanation

In such kind of problems first thinking should be dynamic programming. Let's try to find answer for first i indexes. Can we relate the answer for i directly to answer for i-1. No! We need some additional information. Why don't we keep two states i and j denoting the number of different arrays of size i that can formed and number j is present at i'th position in such arrays. Basically dp(i, j) denotes number of arrays of size i such that j intervals end at i'th position. Note that for j > B_i, dp[i][j] would be zero, because it's not a valid array. Our answer will be dp(N, 1) + dp(N, 2) + ... + dp(N, B_N)

Now, let's try to form recurrences. What we should be thinking is for dp(i, j) which all are valid x such that dp(i-1, x)can be added to dp(i, j) ie. what valid numbers can come at position i-1 if j is present at index i?

Now, an interesting observation is that x can be any value greater than equal to j-1. It can be thought as: suppose xintervals were ending a index i-1, then we can choose to extend any number of them to index i to get any sum between 1 and x + 1(note that one interval starts and ends at i). So, we get that x can be any number greater than or equal to j-1.

So, here is our recurrence:

dp(i, j) = dp(i-1, N) + dp(i-1, N-1) + dp(i-1, N-2) ... dp(i-1, j-1)

So, if we calculate each state dp(i, j) in O(N), our total complexity will be O(N³).
But we can notice that dp(i, j) depends on a continuous sum in one dimensional array of dp(i-1).
So, if we calculate prefix sum array:
prefix[j] stores the sum dp(i-1, j) + dp(i-1, j+1) ... dp(i-1, N). So, prefix[j] = prefix[j+1] + dp[i-1][j]. We can calculate this prefix sum array in O(N).

Code

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

int dp[1010][1010];

int pre[1010];

int b[1010]; 

#define mod 1000000007

int main()

{

 int t;

 cin>>t;

 while(t--)

 {

  int n;

  cin>>n;

    memset(dp,0,sizeof(dp));

    for(int i=1;i<=n;i++)

    scanf("%d",&b[i]);

    for(int i=1;i<=n;i++)

    b[i]=min(b[i],i);

    dp[1][1]=1;

    pre[0]=0;

    memset(pre,0,sizeof(pre));

    for(int i=1;i<=n;i++)

    {

            pre[i]+=dp[1][i];

  pre[i]+=pre[i-1];

  }

    for(int i=2;i<=n;i++)

    {

          for(int j=1;j<=b[i];j++)

  {

        int lf=max(j-1,1);

int rt=n;

dp[i][j]=(pre[n]-pre[lf-1]+mod)%mod;

  }

  for(int kk=1;kk<=n;kk++)

  {

        pre[kk]=0;

pre[kk]+=pre[kk-1];

   if(pre[kk]>=mod)

   pre[kk]%=mod;

 

pre[kk]+=dp[i][kk];

if(pre[kk]>=mod)

   pre[kk]%=mod;

  }

  }

 int ans=0;

  for(int i=1;i<=b[n];i++)

  {

    ans=(ans+dp[n][i]);

    if(ans>=mod)

    ans%=mod;

  }

  printf("%d\n",ans);

 }

 return 0;

}