Eu deveria saber estatística?

Não faço ideia do que isso quer dizer, talvez nem tenha a ver com estatística.

Nessa semana começou uma nova “season” no Hacker Earth, e o primeiro problema trata sobre razões entre distribuições. O enunciado:

Existem dois tipos de entrada denotados por A e B. As entradas estão organizadas em uma fila e devem ser distribuídas em sequência para o maior número possível de saídas de maneira que a razão entre o número de entradas A e B seja a mesma em todas elas.

Em outras palavras você deve achar o maior número de saídas possíveis.

Exemplo:

Entrada: [A, A, B, B, A, A, B, A, A]
Saída: [A, A, B], [B, A, A], [B, A, A] (razão 2:1)

Logo o número máximo de saídas com a mesma razão é 3.

Entrada: [A, A, A, A]
Saída: [A], [A], [A], [A] (razão 1:0)

E o número máximo de saídas com a mesma razão é 4.

Analisando o problema

Quando se trata de razões iguais, a soma de partes individuais mantém o mesmo valor da razão total:

2:1 + 4:2 = 6:3 = 2:1

Assim o primeiro passo para determinarmos a razão em cada distribuição é determinar a razão total da entrada.

const arr = ['A', 'B', 'A', 'B'];
const aNumber = 0;
const bNumber = 0;
while (count < arr.length) {
       
  if (arr[count] === 'A') aNumber ++;
  if (arr[count] === 'B') bNumber ++;
            
  count++;
}

Em sequência, podemos percorrer a entrada para fazer a contagem do numero de vezes em que essa razão aparece, o que é equivalente ao número de saídas que podemos produzir. Na primeira implementação, todas as vezes em que a razão era atingida o meu algoritmo zerava as flags de contagem, mas por razões de otimização (explicadas abaixo), eu retirei esta parte do código, afinal como dito acima, ao somar razões iguais o valor permanece o mesmo para todas elas. Além disso, devido ao fato de JS passar variáveis com referencia, este modo elimina a necessidade manipular a fila e retirar dados após encontrar uma distribuição que satisfaça a condição.

const ratio = aNumber / bNumber;
const localA = 0;
const localB = 0;
const result = 0;
while (count < arr.length) {
  if (arr[count] === 'A') localA ++;
  if (arr[count] === 'B') localB++;
  if ((localA / localB) === ratio) result ++;
  count++;
}

Vale lembrar que no problema original a entrada é um pouco diferente e deve ser manipulada pelo programa, deste modo temos acesso ao número de A’s ou B’s em sequência.

O algoritmo funciona para todos os casos, porém ao submeter os testes eu tive uma surpresa, meu algoritmo roda em tempo O(n) em todos os casos, no entanto o sistema de checking automático do Hacker Earth tem uma limitação para o tempo máximo em que um algoritmo deve terminar sua execução, neste caso 5 segundos, e para entradas grandes (da ordem de 10¹⁸), ele é interrompido antes de terminar sua execução.

E é aqui que meus problemas de verdade com a estatística começam.

Depois de muitas tentativas, eu cheguei a uma maneira de reduzir o tempo de execução no caso médio. Levando a conta a informação que tenho sobre o tamanho da próxima sequência de entrada, é possível determinar qual o numero mínimo de entradas de outro tipo necessárias para que a razão seja satisfeita.

Por exemplo, na fila [A, A, B, A, A, B, B, B, A, B] a razão é 1:1, assim ao ler a sequência [A, A], eu posso dizer que devo ler pelo menos duas vezes uma entrada do tipo B para satisfazer localmente a minha razão. Dando sequência com a entrada [B], posso dizer que a minha condição não foi satisfeita, portanto estes elementos não podem conter ainda uma distribuição do tipo 1:1.

// Apenas um snapshot, para a entradas do tipo B a lógica é a mesma
if (description[1] === 'A') {
    localA += number;
                    
    if (lastChar === 'A' || !lastChar) {
        minimalB = ((localA * bNumber) / aNumber) - localB;
    } else {
        if (minimalA <= number && minimalA > 0)  {
            friends++;
        }
                        
        minimalB = ((localA * bNumber) / aNumber) - localB;
    }
                    
    lastChar = 'A';
}

Mas temos um problema. A nova solução funciona para todos os casos simples e resolve todas os problemas que antes não eram executados devido ao tempo, porém não funciona para os testes em que a primeira versão passa.

De algum modo, a nova solução valida casos estranhos para problemas menores! E porque eu deveria saber estatística? De acordo com um colega que teve essa matéria na graduação, este tipo de problema pode ser resolvido por meio de funções!

Existe um modo logarítmico no pior caso para calcular a distribuição de razões em qualquer conjunto de dados, porém eu não sei ler e portanto implementar o algoritmo.

Infelizmente o prazo para pontuação máxima já passou, ainda assim na parte 2 deste texto eu vou mostrar como ficou a implementação dessa função, junto com um benchmark para mostrar sua eficiência. Até lá!

Código completo para utilizar no Hacker Earth:

// Sample code to perform I/O:
process.stdin.resume();
process.stdin.setEncoding("utf-8");
var stdin_input = "";
process.stdin.on("data", function (input) {
    stdin_input += input     // Reading input from STDIN
});
process.stdin.on("end", function () {
    solve();
});
// Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
// Write your code here
solve = () => {
    const splited = stdin_input.split("\n");
    const testCases = parseInt(splited[0]);
    
    let line = 1;
    for (let i = 0; i < testCases; i++) {
        const descriptionLength = parseInt(splited[line]);
        const stopLine = descriptionLength + line;
        
        line++; // start on next line after read descriptionLength
        let supportLine = line;
        
        let aNumber = 0;
        let bNumber = 0;
        while (line <= stopLine) {
            const readLine = splited[line];
            const description = readLine.split(" ");
            
            const number = parseInt(description[0]);
            
            if (description[1] === 'A') aNumber += number;
            if (description[1] === 'B') bNumber += number;
            
            line++;
        }
        
        if (aNumber === 0 || bNumber === 0) {
            process.stdout.write(Math.max(aNumber, bNumber) + '\n');
        } else {
            const ratio = aNumber/bNumber;
            let friends = 0;
            let localA = 0;
            let localB = 0;
            let minimalA = 0;
            let minimalB = 0;
            let lastChar;
            
            while (supportLine <= stopLine) {
                const readLine = splited[supportLine];
                const description = readLine.split(" ");
                
                const number = parseInt(description[0]);
                
                if (description[1] === 'A') {
                    localA += number;
                    
                    if (lastChar === 'A' || !lastChar) {
                        minimalB = ((localA * bNumber) / aNumber) - localB;
                    } else {
                        if (minimalA <= number && minimalA > 0)  {
                            friends++;
                        }
                        
                        minimalB = ((localA * bNumber) / aNumber) - localB;
                    }
                    
                    lastChar = 'A';
                }
                if (description[1] === 'B') {
                    localB += number;
                    
                    if (lastChar === 'B' || !lastChar) {
                        minimalA = ((localB * aNumber) / bNumber) - localA;
                    } else {
                        if (minimalB <= number && minimalB > 0) {
                            friends++;
                        }
                        
                        minimalA = ((localB * aNumber) / bNumber) - localA;
                    }
                    
                    lastChar = 'B';
                }
                
                supportLine++;
            }
        process.stdout.write(friends + '\n');
        }
    }
}