Autor da análise: 
edauri
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
Discuta o problema
Algo adicional, yo trabaje que con los grados de cada elemento que iba ser analizado; asi descartaba si entraba o no al llamado del "backtracking":
Supongamos que tengo una solucion local de "m" elementos, entonces si queria ver si alguno siguiente pudiera entrar al
grupo de la solucion, entonces tenia que tener grado "m+1", como minimo.
Vou compartilhar uma coisa que talvez possa poupar uma boa dor de cabeça. Eu fiz usando bitmask, com long long. Estava dando errado, fiquei horas debuggando meu código sem achar o erro. Depois de criar alguns casos de teste, descobri que o erro estava no meu shift. Para construir um estado eu fazia:
Acontece que 1 NÃO é um long long, então (1«i) estourava o inteiro. O certo é (1LL«i) (ou qualquer outro cast).