PKU 1632 - Vase collection

Autor da análise: edauriedauri

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1632

Resumo

Dado m elementos ( N<=100 ) e cada um com 2 propriedades, formato e decoração, e cada propriedade tendo valores 0 < P1,P2 <= 36, é pedido para achar o maior K, sendo K um subconjunto desses elementos tal que existam K propriedades P1 e K propriedades P2, ou seja, nesse subconjunto há K*K elementos.

Solução

Podemos modelar o problema da seguinte forma: temos 2 conjuntos de propriedades e vejamos eles como vértices em um grafo e os elementos vemos como arestas ligando as propriedades nesse grafo. Agora o problema tornou-se um problema um pouco mais conhecido, precisamos achar um subgrafo bipartido completo maximal. Porém o problema é NP-completo.

Para achar a solução do problema precisamos,basicamente, testar todos os subconjuntos de elementos e pegar o maior grafo bipartido completo com o mesmo numero de elementos em cada lado. Para fazer isso a solução é muito custosa é O(2^N), Porém com backtracking isso pode diminuir bastante.

Olharemos para outra peculariedade do problema. Cada propriedade tem um valor de 1 a 36, ou seja, Para deixar a solução um pouco mais rápida, podemos representá-la em uma bitmask em um inteiro de 64 bits.

Com isso, podemos chegar em uma solução mais rápida. Envés de testar os 2^N subconjuntos, testamos 2^36 conjuntos, que são de uma propriedade do elemento e para cada subconjunto desse, verificamos se o grafo induzido por esse conjunto satisfaz a nossa condição do problema. Agora vemos um pouco mais de perto e vemos que não precisamos ver todos os 2^36 subconjuntos, pois são poucos que realmente satisfazem uma possível solução para o nosso problema. Daí vem a idéia de um backtracking: à medidade que é testado os subconjuntos da propriedade P1, se num determinado momento temos k elementos, verificar se existem k elementos de P2 que são ligados com todos os k de P1. Para isso, podemos ter uma bitmask de ajacência para P1 e no backtracking, guardamos uma bitmask de P2 que representa os elementos de P2 que ligam com todos de P1. Daí para testar se aquela é uma das soluções (talvez não a ótima) é só ver se o número de elementos de P1 for menor ou igual ao número de elementos de P2 que estão na bitmask.

Cuidado para contar os bits de um inteiro de 64 bits. No PKU se usar o __builtin_popcount, para o C++ não funciona, porém para o G++ funciona.
A entrada abaixo cuida justamente disso.

Testes

Entrada

1
2
33 34
34 33

Saída

1

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License