Topcoder: SRM 495

O post era pra ter saído na Sexta, mas acabou atrasando :/ Bom, hoje vou comentar sobre os problemas não resolvidos durante o SRM 495. Consegui fazer o fácil de 300 pontos, mas demorei bastante tempo e tive que ressubmeter. Aí meu rating acabou caindo.

Carrot Boxes

Descrição. Há N caixas numeradas de 0 a N-1. Todas as caixas, exceto uma, possuem uma cenoura. Deseja-se descobrir a caixa vazia sem abri-la.

Algumas caixas possuem informações sobre o conteúdo de outras caixas e essa informações são conhecidas a priori. É dado um vetor<string> information, onde o j-ésimo caractere da i-ésima string é ‘Y’ se abrir a i-ésima vai revelar se a j-ésima caixa contém ou não uma cenoura, ou ‘N’ caso contrário.

Retornar a maior probabilidade para descobrir a caixa vazia sem ter que abri-la. (Texto original)

O autor do editorial descreveu a solução desse problema de forma tão bem detalhada e exemplificada que nem vale a pena explicar do meu jeito. Implementei a solução descrita em C++. Uma coisa que achei legal da solução é que se você pode se dar ao luxo de rodar um Floyd-Warshall O(n^3), depois fica bem simples determinar componentes fortemente conexas.

Strange Elevator

Descrição resumida. Considere um prédio de H andares e um elevador formado por N compartimentos (não necessariamente consecutivos). Quando parado, cada parte fica em um andar distinto e quando o elevador se move, todas as partes movem junto. Cada andar deve ser coberto por exatamente um compartimento do elevador. (Texto original)

Podemos representar um elevador pelos andares em que cada compartimento está, quando o compartimento mais baixo está no primeiro andar (denotado aqui por nível 0). Por exemplo, se H = 6 e N = 3, os elevadores (0, 2, 4) e (1, 3, 5) são respectivamente:

O problema pede para, dados N e H, encontrar quantos elevadores válidos podem ser formados. Para H = 6 e N = 3, há duas possibilidades, (0, 2, 4) e (0, 1, 2). Observe que (0, 2, 3) não é válido, pois o elevador, ao subir um andar, irá para os andares (1, 3, 4) e o andar 3 terá sido coberto por dois compartimentos diferentes.

Solução. Está bem detalhada no editorial, então vou tentar resumir aqui.

Proposição 1: Definimos como bloco um conjunto contínuo de compartimentos. Em um dado elevador, todos os blocos têm mesmo tamanho L.

Proposição 2: O espaço de separação entre dois blocos consecutivos é múltiplo de L.

A ideia básica das provas das duas proposições acima é que se elas não forem verdade, então necessariamente algum andar será coberto por mais de um compartimento ou algum andar não será coberto.

Problemas de contagem geralmente envolvem algum tipo de programação dinâmica (exceto quando existe uma fórmula fechada). De fato, a solução apresentada divide a matriz de PD em duas partes: C1(H, N) e Cn(H, N) a primeira corresponde ao número de elevadores válidos para um prédio de H andares e N caixas quando os blocos têm tamanho L = 1, enquanto a segunda quando os blocos têm tamanho L > 1.

A sacada do problema consiste em definir a relação de recorrência. A primeira observação é um corolário das Proposições 1 e 2: Como os blocos têm tamanho L e os espaços têm tamanho múltiplos de L, então H deve ser múltiplo de L. Dado isso, podemos “escalar” o problema dividindo todas as dimensões por L. Ou seja, o número de elevadores válidos para H andares, N caixas e blocos de tamanho L, é o mesmo para H/L andares, N/L caixas e blocos unitários. Logo, podemos definir a recorrência de Cn(H, N) da seguinte forma:

(1)

Para definir a recorrência de C1(H, N) é mais complicado. Considere o vetor offbox que representa o offset dos compartimentos (boxes), ou seja, é o andar que cada compartimento ocupa quando o compartimento mais embaixo está no primeiro andar. Esse vetor tem tamanho N. Seja offlift o offset do elevador, ou seja, é o andar ocupado pelo compartimento mais embaixo. Esse vetor tem tamanho H/N que é o número de vezes que um elevador com N caixas pára.

Observe que se o elevador é válido, então para todo andar a, existe exatamente um par (i, j) tal que a = offbox[i] + offlift[j] e que esses dois vetores caracterizam unicamente um dado elevador. É fácil ver que se offbox e offlift representam um elevador válido para H andares e N caixas, trocando os papéis deles, vai gerar um elevador, denotado por dual, válido com H andares e H/N caixas.

Considere então um elevador com blocos de tamanho 1. Temos que offbox[0] = 0 e offbox[1] > 1, já que a primeira e a segunda caixa não podem estar contíguas. Além do mais, o primeiro compartimento é o único capaz de visitar o segundo andar, ou seja o elevador deve parar também no primeiro andar e offlift[1] = 1. Trocando os papeis dos vetores, temos offbox[0] = 0 e offbox[1] = 1, ou seja, é um elevedor com L > 1. Assim, todo elevador para H andares, com N caixas e L = 1, corresponde a um elevador para H andares, H/N caixas e L > 1.

Exemplo de configurações duais. O primeiro é offbox = {0, 2, 4} e offlift = {0, 1}. O segundo é offbox = {0, 1} e offlift = {0, 2, 4}.

Por outro lado, é fácil ver que todo elevador para H andares, H/N caixas e L > 1, corresponde a um elevador para H andares, N caixas e L = 1. Lembrando que cada um desses vetores caracteriza unicamente um elevador, não é difícil de acreditar que há uma bijeção entre essas duas configurações, o que equivale a afirmar que o número de elevadores válidos em cada uma delas é exatamente o mesmo, permitindo finalmente que escrevamos a recorrência de C1(H, N)

(2)

Como H e N sempre diminuem, as recorrências em (1) e (2) são suficientes para resolver o problema que é simplesmente C1(H, N) + Cn(H, N).

Ainda está faltando o caso base. Como H começa maior do que N e nunca diminuímos H mais do que N, fica claro que H não chegará em 1 antes de N. Logo, basta tratar o caso em que N = 1. Só há um possível elevador para N = 1 com blocos de tamanho 1 e claramente não existem elevadores com N = 1 para blocos de tamanho maior do que 1.

Outro cuidado que devemos tomar é que só existe solução se N dividir H, então precisamos fazer essa verificação antes de rodar o algoritmo.

Finalmente, um detalhe sobre a implementação. A princípio a complexidade parece ser O(HN*div(N)), onde div(N) são os divisores de N, que é essencialmente O(sqrt(N)). Porém, como H e N são da ordem de 1000000000 (10^9), essa abordagem parece impraticável.

Por outro lado, note que quando chamamos Cn(H, N), apenas os O(sqrt(N)) divisores de N serão chamados e serão divididos por pelo menos um fator de 2. Sinceramente, não sei calcular uma complexidade mais justa, mas olhando por cima, parece que não serão chamadas muitas combinações de H e N.

Além do mais, podemos otimizar o algoritmo usando memoização. No caso usual usaríamos os valores de H e N para indexar uma matriz. Aqui, entretanto, não é possível devido à magnitude dos valores. Supondo um número pequeno de combinações H e N, podemos usar um mapa usando como chave o par (H, N) (map<pair<int, int> > da STL).

Minha implementação em C++ está disponível aqui.

Os comentários estão fechados.

%d bloggers like this: