TopCoder SRM 566 – Division I Level One – PenguinSledding

Penguin Sledding (link)

There are 3 different kinds of valid forms.

1. Single connection.
2. N connections as a star.
3. Triangles are valid (tree checkpoints connected).

The first and third can be find by simple cycles. The second one needs another way. In my case i use combination (binomial coefficient formula).

import java.math.BigInteger;

public class PenguinSledding {

    public BigInteger conFunc(int n, int r) {
        BigInteger a = BigInteger.ONE;
        BigInteger b = BigInteger.ONE;
        for(int i=1; i<=r ;i++) {
            BigInteger nn = BigInteger.valueOf(n-i+1);
            BigInteger xx = BigInteger.valueOf(i);
            a = a.multiply(nn);
            b = b.multiply(xx);
        }
        return a.divide(b);
    }

    public long countDesigns(int n, int[] che1, int[] che2) {
        int m = che1.length;
        int[] G = new int[52];
        boolean[][] W = new boolean[52][52];
        for(int i=0; i<=n ;i++){
            G[i] = 0;
            for(int j=0; j<=n ;j++){
                W[i][j] = false;
            }
        }
        for(int i=0; i<m ;i++){
            W[che2[i]][che1[i]] = true;
            W[che1[i]][che2[i]] = true;
            G[che2[i]]++;
            G[che1[i]]++;
        }
        BigInteger r = BigInteger.valueOf(1 + m);
        for(int i=1; i<=n ;i++) {
            int t = G[i];
            for(int j=2; j<=t ;j++) {
                r = r.add(conFunc(t, j));
            }
            for(int j=i+1; j<=n ;j++) {
                for(int k=j+1; k<=n ;k++) {
                    if(W[i][k] && W[i][j] && W[j][k]) {
                        r = r.add(BigInteger.ONE);
                    }
                }
            }
        }
        return r.longValue();
    }
}
Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

w

Conectando a %s