Treino T04: Comprar Informação

Os Artigos 9, 10 e 11 trataram a busca e a ordenação como compra de informação. A busca binária compra um bit por comparação, a ordenação paga $O(n\log n)$ uma vez para que muitas perguntas futuras fiquem baratas, a seleção paga só pela posição que interessa, e a contagem usa uma informação que a comparação desperdiça, o tamanho do universo das chaves. Este treino cobra essas compras com o relógio correndo. Antes de escolher a ferramenta, a leitora precisa decidir qual garantia o problema exige: a ordem completa, uma única posição, a estabilidade entre empates ou apenas a fronteira entre um sim e um não.

Vários enunciados escondem a mesma pergunta com roupas diferentes. Onde, exatamente, fica a fronteira? Encontrar a resposta certa depende de saber se a fronteira procurada é o primeiro verdadeiro ou o último verdadeiro, e de arredondar o meio para o lado que garante progresso.

1. Como o treino e a avaliação funcionam

As sessões seguem o formato do Artigo 3: S1 é um aquecimento de uma hora com um problema, S2 é uma hora com um problema médio, S3 é uma hora com dois problemas curtos, e S4 são duas horas com três problemas, um dos quais resiste. Cronômetro ligado antes do primeiro enunciado, apenas os artigos de estudo correspondentes e o próprio código abertos, compilador à vontade, problema resolvido quando o programa passa no exemplo e nos casos-limite construídos pela leitora, sessão encerrada quando o tempo acaba.

A avaliação A2 é mais longa e mais larga que a A1 do Artigo 6: