How to reduce execution time in this program

Question

I would be really grateful to you guys if you could let me know of some method to reduce the execution time.

limit time : 0.5sec

Algorithm Question : I want to bridge the site in the west to the site in the east. (At this point, only one bridge can be connected to one site.) Because I try to build as many bridges as possible, I try to build as many (N) bridges as possible as the number of sites in the west. bridges cannot overlap each other. At this point, write a program to figure out how many cases you can build a bridge.

Input : The first line of the input is given the number of test cases, 'T'. From the next line, each test case is given an integer (0 < N ≤ M < 30) for the number of sites west and east of the river.

Output : For each test case, print the number of cases in which the bridge can be built under the given conditions.

Example :

Input           Output
3                   
2 2             1
1 5             5
13 29           67863915

Here is my code :

#include <stdio.h>

int combination(int n, int r) {
    if (n == r || r == 0) return 1;
    else return combination(n - 1, r - 1) + combination(n - 1, r);
}

int main(void)
{
    int Tcase;
    int N, M;

    scanf("%d", &Tcase);

    for (int i = 0; i < Tcase; i++) {

        int total;
        scanf("%d %d", &N, &M);

        if (M - N == 0) 
            total = 1;
        else 
            total = combination(M, N);

        printf("%d\n", total);
    }

    return 0;
}

The two most common "tricks" for competition assignments like this, is to either figure out an equation which makes it possible to calculate values without the use of loops or recursion; And the second one is to use something called *dynamic programming* (commonly implemented by caching calculated values so they don't have to be calculated again). — Some programmer dude, Apr 14 '21 at 06:01
N choose R can be calculated as shown in [this answer](https://stackoverflow.com/questions/28058019/pascals-triangle-in-c/28058811#28058811) — user3386109, Apr 14 '21 at 06:26
Drop the stdio.h function calls, thats some 99% of your execution time there. — Lundin, Apr 14 '21 at 07:05
@AKSingh Because there's only one way to choose 2 items from a collection of 2 items. The other examples show that there are five ways to choose 1 item from a collection of 5 items, and lots of ways to select 13 items from a collection of 29 items. — user3386109, Apr 15 '21 at 22:49

Aaron Stanek · Answer 1 · 2021-04-14T18:19:09.700

Function calls can add a bit of overhead. Redundant function calls add A LOT of overhead. Because all the base case function calls return 1, you can just count the number of function calls that will result in the base case.

You can flatten the entire recursive call stack into an array of ints where you count the number of times that a state occurs. Here mem[i] represents the number of times that combination(n, i) will be called in your version of the program. (Please note that this statement is only strictly true at the end of each iteration of the while loop)

int combination(int n, int r) {
    int* mem = malloc(sizeof(int)*(r+1));
    // the largest index in mem is r
    if (mem == NULL) return -1;
    for (int i = 0; i < r; ++i) {
        mem[i] = 0;
    }
    mem[r] = 1;
    // here we have mem = 0,0,0,...,1
    int total = 0;
    // total is the number of function
    // calls in the original program that
    // will result in the base case
    while (n > 0) {
        // if (r == 0) return 1;
        total += mem[0];
        mem[0] = 0;
        // if (n == r) return 1;
        if (n <= r) {
            total += mem[n];
            mem[n] = 0;
        }
        // else return combination(n - 1, r - 1) + combination(n - 1, r);
        for (int i = 0; i < r; ++i) {
            mem[i] += mem[i+1];
        }
        --n;
    }
    free(mem);
    return total;
}

Even this is suboptimal; there are memory accesses to mem[0] that probably aren't needed, and the bounds on the second for loop can definitely be reduced.

How to reduce execution time in this program

1 Answers1