Google Code Jam 2011: QR_D - GoroSort

O problema final da rodada da qualificação foi o mais difícil. Além disso, veio recheado de malvadezas, da descrição cheia de detalhes desnecessários ("Goro has 4 arms." - e daí?) a uma saída com seis casas decimais ("Answers with an absolute or relative error of at most 10-6 will be considered correct") para uma resultado que é sempre inteiro.

O Problema

Tirando os detalhes desnecessários, ficamos com uma entrada contendo números de 1 a N fora de ordem que precisa ser ordenada. A ordenação será feita fixando alguns dos números e embaralhando aleatóreamente os demais (na base da porrada do Goro na mesa). A saída é o número médio de embaralhamentos necessários, supondo que os números fixados sejam escolhidos de forma ideal.

Minha Solução (e como eu cheguei a ela)

É relativamente óbvio que os números as serem fixados são, no minimo, os que estiverem na posição correta e que a saída depende apenas de quantos números estão fora do lugar. A quantidade total de números e quais estão fora do lugar são irrelevantes.

Os exemplos dão duas dicas:

• Para dois números fora do lugar, o número médio de embaralhamentos é 2: "A probabilidade dos dois números ficarem na ordem corretá é 1/2 e a de ficaram na ordem errada é 1/2, portanto o número médio de embaralhamentos é dois" (friso meu no enigmático portanto).
• Para quatro números, uma estratégia é fixar dois, ordenar os outros dois (média de 2 embaralhamentos) e depois fixar os dois já ordenados e ordenar os dois primeiros, totalizando um média de 4 embaralhamentos.
  

Após a leitura do enunciado eu não estava muito animado a tentar resolver, mas raciocinei que uma tentativa simples não faria mal. Resolvi expandir o segundo caso e supor que para ordenar N números seria preciso 2*((N+1)/2) pancadas. Ou seja, duas pancadas para cada dois números (e duas para o número restante se N for impar). Deu errado (mal sabia eu que estava muito próximo do resultado), mas foi o suficiente para me levar a insistir um pouco.

No caso de dois números, temos duas possibilidades a cada pancada. No caso de três temos seis (3!) e assim por diante. Comecei a analisar as seis combinações, pensando em obter a média somando os produtos das probalilidades pelas quantidades de embaralhamentos para cada caso:

• 1 (probabilidade 1/6) está correta.
• 3 (probalilidade 3/6) estão com um número na posição correta, portanto iremos precisar de mais duas pancadas (para colocar no lugar os números na posição errada), totalizando três
• 2 (probabilidade 2/6) de continuar os três números fora de posição. E agora?

O fato de ser seis combinações, me levou a pesquisar no Google sobre quantas jogadas são necessárias em média para obter um determinado número em um dado. E achei um raciocínio interessante. Se E é o número médio desejado, no último caso acima vamos precisar em média de E+1. Com isto obtemos a equação

E = 1*1/6 + 3*3/6 + (E+1)*2/6

Resolvendo, dá E = 3.

Hum... eu poderia repetir a análise para 4, 5, etc mas eu estava sentindo cheiro de artimanha. Vejamos:

• Para ordenar 2 números precisa 2 pancadas
• Para ordenar 3 números precisa 3 pancadas
• Para ordenar 4 números precisa 4 pancadas

Esta sequência (2, 3, 4) tem alguma lógica? Que tal testar colocar na saída a quantidade de números fora do lugar? E não é que deu certo?

Para quem gostar de matemática, tem uma demostração rigorosa no site oficial. Esta demonstração prova a expressão acima para o caso genérico e que ela é a solução otimizada.

Para encerrar, aqui está o código:

void main (void)
{
 int iCase, nCases;
    int i, n, num, count;

 scanf ("%d\n", &nCases);
 for (iCase = 1; iCase <= nCases; iCase++)
 {
     scanf ("%d\n", &n);
        count = 0;
        for (i = 1; i <= n; i++)
        {
            scanf ("%d ", &num);
            if (num != i)
                count++;
        }
        printf ("Case #%d: %f\n", iCase, (double) count);
 }
}

Agora é esperar as malvadezas da primeira rodada.