2
\$\begingroup\$

I'm trying to solve the following problem:

You have a k-dice. A k-dice is a dice which have k-faces and each face have value written from 1 to k. Eg. A 6-dice is the normal dice we use while playing games. For a given N, you have to calculate the number of ways you can throw this dice so that we get sum equal to N. Since number of ways can be large you have to calculate ways mod 998244353 Refer to samples for better understanding. (Use long long data type instead of int to avoid overflow errors)

Input Format

T 
N1 K1 
N2 K2 
N3 K3 
. 
. 
. 
NT KT

Constraints

N, K and T are integers 
1<=T<=100 
1<=N<=100 (20% points) 
1<=N<=10^18 (100% points) 
2<=k<=20

Output Format

ans1 
ans2 
ans3 
. 
. 
ansT

Sample Input 0

3
5 3
7 4
8 10

Sample Output 0

13
56
128

Explanation 0

In first test case

1+1+1+1+1=5 
1+1+1+2=5 
1+1+2+1=5 
1+2+1+1=5 
2+1+1+1=5 
2+2+1=5 
2+1+2=5 
1+2+2=5 
3+1+1=5 
1+3+1=5 
1+1+3=5 
3+2=5 
2+3=5 

So there are 13 ways.

Here we can only use the iostream library, so all the other functions needs to be written by me. In that case, for the T iterations in a while loop, we are first taking in a an array followed by merge sorting the algorithm before proceeding to the helper function.

In the helper function we are trying to introduce recursion with the fact that as long as N is greater than the total sum, we find a way to add different numbers among the K possible numbers on the dice.

As a base case if N turns 0, there happens to be just one way to return it, thus we define it as our base case. Finally to make our code efficient, we ended up memoizing our code in order to store the earlier values, and in case the value is already stored, it'll directly return that without passing the entire recursion.

My code is:

#include <iostream>
using namespace std;

long long countWays(int N, int K, long long dp[]) {
    if (N == 0) return 1;
    if (dp[N] != 0) return dp[N]; 
    
    long long ways = 0;
    for (int j = 1; j <= min(N, K); j++) {
        ways = (ways + countWays(N - j, K, dp)) % 998244353;
    }
    
    return dp[N] = ways;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int N, K;
        cin >> N >> K;
        long long dp[N + 1] = {0};
        long long ways = countWays(N, K, dp);
        cout << ways << endl;
    }

    return 0;
}

While the code works find for 3/6 test cases, the other 3 test cases end up giving a segmentation fault. I believe the segmentation fault is because of the constraints as the value which is coming as an input is of the order 10^18.

One such example of the segmentation fault is: enter image description here

This is precisely the case of space complexity error. The code works precisely fine, but the segmentation fault is cause of exceeding the space complexity. Secondly, I performed another approach as suggested by @JustinChang in the answers:

#include <iostream>
using namespace std;

long long countWays(const long long N, const int K) {
    // for convenience
    //const int K1 = (K + 1);

    // the number of ways for a sum of i is stored in dp[i % K1]
    // initialize from 0 to K inclusive: 1, 1, 2, 4, ...
    long long dp[21] = {1, 1};
    for (int i = 2; i < (K + 1); ++i) 
        dp[i] = 2 * dp[i - 1];

    // cycle, filling each slot with the sum of the other slots
    for (long long i = (K + 1); i <= N; ++i) {
        // int curr_i = i % (K + 1);
        // int prev_i = (i - 1) % (K + 1);
        dp[i % (K + 1)] = (2 * dp[(i - 1) % (K + 1)] - dp[i % (K + 1)]) % 998244353;
    }
    
    // because C++ can have negative remainders
    return (dp[N % (K + 1)] + 998244353) % 998244353;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int N, K;
        cin >> N >> K;
        //long long dp[N + 1] = {0};
        long long ways = countWays(N, K);
        cout << ways << endl;
    }

    return 0;
}

Here the code works fine in terms of space complexity, but exceeds the time complexity for larger inputs (of the order 10^18). The allowed time limit is just 2 seconds as it always is.

Your code did not pass this test case. Input (stdin)

100000000 10
705702493 12
27395703283 5

Your Output (stdout)

362391665

Expected Output

362391665
837869791
564958105

Compiler Message

Terminated due to timeout
\$\endgroup\$
7
  • \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ If time limit exceeded is acceptable, would space limit exceeded be acceptable? It is my belief that the failing test cases actually would pass if 8 exabytes of RAM were available on the testing suite. \$\endgroup\$ Aug 21, 2023 at 4:50
  • \$\begingroup\$ @driver I also think the question could be more approachable if you provided the test cases / error messages in text rather than screenshot form. \$\endgroup\$ Aug 21, 2023 at 4:57
  • \$\begingroup\$ @JustinChang sure I will keep this in mind while posting the questions in future again \$\endgroup\$
    – driver
    Aug 21, 2023 at 5:03
  • \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ thank you so much. this is the case of space complexity exceeded as it is updated in the question \$\endgroup\$
    – driver
    Aug 21, 2023 at 5:04
  • 2
    \$\begingroup\$ @driver I've reopened the question- it appears that time-limit and space limits are considered closely related. It appears you have more than one account (as evidenced by the suggested edit in revision 6), which can be merged with your other account. You can use the contact SE page and request the accounts be merged. \$\endgroup\$ Aug 21, 2023 at 21:41

1 Answer 1

3
\$\begingroup\$

Note that % can be negative in C++. The recurrence relation can also be simplified:

// only works for i >= K + 1
dp[i] = 2 * dp[i - 1] - dp[i - K - 1]

Other than that, I agree the main issue is that dp can exceed available memory, as it can be up to 8 * 10^18 bytes, or 8 exabytes. Additionally, the recursive calls create a lot of stack frames. Instead, you can iteratively work your way up, keeping only the last K+1 numbers at any given moment. Since K <= 20, you can declare a fixed-size array of length 21 (but if the sizes were more variable, I would use malloc):

long long countWays(long long N, int K) {
    // for convenience
    int K1 = (K + 1);

    // the number of ways for a sum of i is stored in dp[i % K1]
    // initialize from 0 to K inclusive: 1, 1, 2, 4, ...
    long long dp[21] = { 1, 1 };
    for (int i = 2; i < K1; ++i)
        dp[i] = 2 * dp[i - 1];

    // cycle, filling each slot with the sum of the other slots
    for (long long i = K1; i <= N; ++i) {
         int curr_i = i % K1;
         int prev_i = (i - 1) % K1;
        dp[curr_i] = (2 * dp[prev_i] - dp[curr_i]) % 998244353;
    }

    // because C++ can have negative remainders
    return (dp[N % K1] + 998244353) % 998244353;
}

I was able to compute the provided cases in less than 5 minutes. Hope that helps.

EDIT: Let dp[0], dp[1], ... dp[K-1] be the first K terms. If you treat this like a column matrix and multiply by a matrix Q, you can turn it into dp[1], dp[2], ..., dp[K]. By repeating this multiplication N - K + 1 times, you get the final answer. So now the question is: how do you quickly compute Q^(N - K + 1)? The solution is a dynamic programming technique called exponentiation by squares. You will need to put it all together:

#include <iostream>
using namespace std;

// malloc but (q)uit on errors
void *malloc_q(size_t s)
{
    void *p = malloc(s);
    if (p == NULL) exit(EXIT_FAILURE);
    return p;
}

// matrix of long longs
class MatrixLL
{
public:
    int m, n; // rows, cols
    long long **v; // values

    // returns an uninitialized matrix
    MatrixLL(int m, int n)
    {
        long long **v = (long long **) malloc_q(m * sizeof(long long *));
        for (int i = 0; i < m; ++i)
            v[i] = (long long *) malloc_q(n * sizeof(long long));

        this->m = m;
        this->n = n;
        this->v = v;
    }

    // copy constructor
    MatrixLL(const MatrixLL &mat) : MatrixLL(mat.m, mat.n)
    {
        for (int i = 0; i < mat.m; ++i)
            for (int j = 0; j < mat.n; ++j)
                v[i][j] = mat.v[i][j];
    }
};

// computes (a * b mod M), assuming a.n == b.m
MatrixLL timesMod(const MatrixLL &a, const MatrixLL &b, long long M)
{
    MatrixLL dst(a.m, b.n);

    for (int i = 0; i < a.m; ++i)
    {
        for (int j = 0; j < b.n; ++j)
        {
            long long inner = 0; // sum(a[i][.] * b[.][j])
            for (int k = 0; k < a.n; ++k)
                inner = (inner + a.v[i][k] * b.v[k][j]) % M;
            dst.v[i][j] = inner;
        }
    }
        
    return dst;
}

// computes (base^exp mod M), assuming exp > 0
MatrixLL powerMod(const MatrixLL &base, long long exp, long long M)
{
    MatrixLL result(base);
    --exp; // result already has 1 power of base
    MatrixLL term(base); // answer is (result * term^exp)
  
    while (exp > 0)
    {
        if (exp % 2 == 1)
            result = timesMod(term, result, M);
        term = timesMod(term, term, M);
        exp /= 2;
    }

    return result;
}

// countWays but O(K^3 * log(N)) time, O(K^2) space
long long countWaysFancy(long long N, int K, long long M)
{
    // initialize starting matrix
    MatrixLL start(K, 1);
    start.v[0][0] = 1;
    start.v[1][0] = 1;
    for (int i = 2; i < K; ++i)
        start.v[i][0] = (2 * start.v[i-1][0]) % M;

    // if no transformations are needed, you're done
    if (N < K)
        return start.v[N][0];

    // initialize transform matrix Q
    MatrixLL transform(K, K);
    for (int i = 0; i < K - 1; ++i)
        for (int j = 0; j < K; ++j)
            transform.v[i][j] = 0;
    for (int i = 0; i < K; ++i)
        transform.v[K - 1][i] = 1;
    for (int i = 0; i < K - 1; ++i)
        transform.v[i][i + 1] = 1;

    // compute the final transform with quick exponentiation
    MatrixLL finalform = powerMod(transform, N - K + 1, M);
    MatrixLL resultMat = timesMod(finalform, start, M);
    return resultMat.v[K - 1][0];
}

// test all provided cases
int main() 
{
    cout << countWaysFancy(5, 3, 998244353) << "\n";
    cout << countWaysFancy(7, 4, 998244353) << "\n";
    cout << countWaysFancy(8, 10, 998244353) << "\n";
    cout << countWaysFancy(100000000, 10, 998244353) << "\n";
    cout << countWaysFancy(705702493, 12, 998244353) << "\n";
    cout << countWaysFancy(27395703283, 5, 998244353) << "\n";
    return 0;
}

This completes the cases in < 1 second. If you are wondering what Q looks like:

// Q(K = 3)
0 1 0
0 0 1
1 1 1 

// Q(K = 5)
0, 1, 0, 0, 0
0, 0, 1, 0, 0
0, 0, 0, 1, 0
0, 0, 0, 0, 1
1, 1, 1, 1, 1
\$\endgroup\$
11
  • 1
    \$\begingroup\$ I agree the current approach can work. but here we end up working out the details with the space complexity, but create an issue with the time complexity. this takes a lot more time than the allowed 2 second time limit. The aim is to write a code which is both space and time efficient \$\endgroup\$
    – driver
    Aug 21, 2023 at 5:01
  • 1
    \$\begingroup\$ Why and how do you think it will be something to do with power of 2? \$\endgroup\$
    – driver
    Aug 21, 2023 at 5:15
  • 1
    \$\begingroup\$ those edits aren't visible in the answers \$\endgroup\$
    – driver
    Aug 21, 2023 at 18:12
  • 1
    \$\begingroup\$ What is long long M in the CountWaysFancy() function? \$\endgroup\$
    – driver
    Aug 21, 2023 at 19:18
  • 1
    \$\begingroup\$ I am still unable to infer from the code what is M doing here. I tried dry running the code for custom inputs, but the code just fails. Please help me understand what should be passed as an argument in the main function to call the CountWaysFancy() function? \$\endgroup\$
    – driver
    Aug 22, 2023 at 0:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.