UVa 410: Station Balance

Leiam primeiro o enunciado do problema.

Em cada caixa (chamber) podemos guardar até dois valores (specimens).

Vamos ter C caixas e S valores representados por um conjunto M. O S pode variar entre 1 e 2C.

Uma forma de simplificar o problema é assumir um número constante de 2C valores, usado zeros para preencher o resto.

Por exemplo, se C = 3 e M = {3,6,8,10}, ampliamos M para ter 2*C=6 valores, ie, M = {0,0,3,6,8,10}.

A técnica gananciosa neste caso é emparelhar o menor valor com o maior valor, o 2º menor com o 2º maior, e assim sucessivamente. Isto só funciona porque estamos a guardar no máximo dois valores por caixa.

Qualquer troca de valores iria aumentar as diferenças entre caixas e assim aumentar o factor de imbalance que pretendemos ser mínimo.

Uma solução possível do problema:

public class UVa_410_StationBalance {

    static double computeImbalance(int[] chambers) {

        double avg = 0.0;  // compute masses' average
        for(int i=0; i<chambers.length; i++)
            avg += chambers[i];
        avg /= chambers.length;

        double imbalance = 0.0;  // compute imbalance = \sum_i | chamber_i - avg |
        for(int i=0; i<chambers.length; i++)
            imbalance += Math.abs(chambers[i] - avg);
        return imbalance;
    }

Este primeiro método calcula o factor de imbalance descrito no enunciado, ie, a soma dos módulos das diferenças entre cada caixa e a média de valores armazenados nas caixas.

O restante código lê os dados, e para cada problem set, calcula a partição com a solução gananciosa e imprime o relatório pedido:

   public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int count_set = 0;
        while (sc.hasNext()) {
            count_set++;

            // read data for each input set
            int C = sc.nextInt();
            int[] chambers = new int[C];
            int[] masses   = new int[2*C]; // already leaving the extra zeros

            int S = sc.nextInt();
            for(int i=0;i<S; i++)
                masses[i] = sc.nextInt();

            Arrays.sort(masses);

            // the greedy solution
            for(int i=0; i<masses.length/2; i++)
                chambers[i] = masses[i] + masses[masses.length-i-1];

            // print report
            if (count_set>1) System.out.println();
            System.out.println("Set #" + count_set);
            for(int i=0; i<C; i++) {
                System.out.print(" " + i + ":");
                if (masses[i] != 0)
                    System.out.print(" " + masses[i]);
                if (masses[masses.length-i-1] != 0)
                    System.out.print(" " + masses[masses.length-i-1]);
                System.out.println();
            }
            System.out.println(
                    String.format("IMBALANCE = %1.5f", computeImbalance(chambers)));
        }

        System.out.println();
        sc.close();
  }
}

Um último detalhe: a especificação do output do enunciado é ambigua. Não se diz exactamente qual a ordem pela qual os valores devem ser colocados nas caixas, e não há informação suficiente nos exemplos para perceber essa ordem. Deste modo, esta solução não passa no UVa. Mas isto é resultado de um enunciado mal concebido, dado que os imbalances estão a ser corretamente calculados.