3
\$\begingroup\$

I'm trying to solve this question on a contest programming judge.

Description of the problem:

There are N birds in a forest, each in their respective tree. There are N tired crows in this forest, and they wish to land in different trees as soon as possible (crows are extremely quarrelsome and they can't share the same tree). Every Pi minutes, the i-th bird leaves the tree to fly a little bit, and you can consider that it returns immediately. Every Ci minutes, the i-th crow can try to land in a tree which there's no bird or can just keep flying. You can consider that crows are faster than birds and if the bird leaves the tree at the same minute that a crow tries to land in it, the crow will land faster. Given an optimal strategy between the crows, what is the earliest time in which every crow will be relaxing, each one in a different tree?

Description of the input:

The first line contains an integer T (1 ≤ T ≤ 100), the number of test cases. Each test case starts with an integer N (1 ≤ N ≤ 9), the number of birds and crows. The second line contains N integers Pi (1 ≤ Pi ≤ 10⁴), as described in the problem statement. The third and last line of each test case contains N integers Ci (1 ≤ Ci ≤ 10⁴), as also described in the problem statement.

Description of the output:

For each test case print “Caso #X: Y”, where X is the number of the current case, starting at 1, and Y is the answer to the problem.

Example of Input:

2
2
1 3
2 2
1
1
1

Example of output:

Caso #1: 6
Caso #2: 1

To solve this problem, I observed that the minimum time of waiting can be obtained with a combination of the birds array with the crows array in which the LCM (least common multiple) would be the minimum one.

My solution generates all permutations of the birds array and compare with the crows array and from all the combinations takes the maximum LCM and for all the maximum LCM choose the minimum one. The limit of this problem is small. This made me think that the solution must be a brute force like this. But my solution is exceeding the time limit.

#include <stdio.h>
#include <math.h>
#include <limits.h>

typedef long long lld;

lld gcd(lld a, lld b)
{
    return (b ==  0) ? a : gcd(b, a % b);
}

lld lcm(lld a, lld b){
    return a*b/gcd(a,b);
}

lld permute(lld *birds, lld *crows, lld n, lld index){
    if(index == n){
        //choose the maximum lcm and return it
        lld aux = 1;
        for (int i = 0; i <= n; ++i)
            aux = fmax(aux,lcm(birds[i], crows[i]));
        return aux;
    }

    lld t,ret = LONG_LONG_MAX;
    for (lld i = index; i <= n; ++i) {
        t = birds[index];
        birds[index] = birds[i];
        birds[i] = t;

        //from all combinations ... select the one which has the lowest maximum lcm
        ret = fmin(ret,permute(birds, crows, n, index+1));

        t = birds[index];
        birds[index] = birds[i];
        birds[i] = t;
    }

    return ret;
}


int main(){
    lld t,n,birds[10],crows[10];
    scanf("%lld",&t);
    for (int i = 1; i <= t; ++i) {
        scanf("%lld",&n);
        for (int i = 0; i < n; ++i)
            scanf("%lld",birds+i);

        for (int i = 0; i < n; ++i)
            scanf("%lld",crows+i);

        lld ret = permute(birds, crows, n-1, 0);
        printf("Caso #%d: %lld\n",i,ret);

    }
}

Some people just made it on 0 secs. Is there some way to optimize this?

\$\endgroup\$
  • 2
    \$\begingroup\$ That's a variant of the assignment problem, which can be solved in polynomial (\$O(n^3)\$) time, rather than your factorial approach, using the Hungarian algorithm. \$\endgroup\$ – Jaime Jul 26 '15 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy