PKU 2798 - Hardwood Cutting

Autor da análise: AtolAtol

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

Resumo

É dada uma matriz n por m, que deve ser "dividida" em "pedaços" de forma a maximizar a quantidade desses "pedaços", onde n e m estão entre 1 e 20.

Pedaço:
A matriz é constituída de caracteres "A" a "Z" , "a" a "Z" , "0" a "9". Um pedaço contém todas as ocorrências dos caracteres
contidos no pedaço, ou seja, dois pedaços distintos não podem conter um mesmo caractere.

Divisão (Corte):
Porém, temos uma regra para efetuar as divisões em um pedaço (que inicialmente é uma matriz). Uma divisão só pode ser feita com cortes horizontais e verticais iniciados nas bordas de um pedaço.

É mais fácil visualizar isso em um desenho que está no enunciado do problema.

Uma outra informação importante é que os caracteres na matriz inicial sempre formam pedaços "conexos", ou seja, caracteres iguais estão sempre em um bloco conexo, vizinhos horizontal ou verticalmente.

====

Genéricamente, temos 6 tipos de cortes a serem realizados, para cada linha e coluna escolhidas.
Vamos considerar a matriz a seguir (indexada de 1 a 3).

1 2 3
4 6 7
8 9 10

Considerando um corte que passa pela linha 2, coluna 1, temos:

1 | 2 3
4 | 6 7
- | - -
8 | 9 10

Agora veja que dado esse corte, podemos separar o pedaço inicial de 6 maneiras:

(Consideram apenas a linha horizontal ou vertical)
1.Cima - Baixo
2.Esquerda - Direita

(Consideram ambas as linhas)
(CSD = Canto superior direito, CSE = Canto superior esquerdo, CID = Canto inferior direito, DIE = Canto inferior direito)
3.CSD + CSE + CID - CIE
4.CSD + CSE + CIE - CID
5.CID + CIE + CSD - CSE
6.CID + CIE + CSE - CSD, exemplo para este caso :

1 |
4 |
- | - -
8 | 9 10
| 2 3
| 6 7
- | - -
|

Para cada um dos cortes, basta verificar se ambos "pedaços" gerados são realmente pedaços, ou seja, respeitam a propriedade dada no enunciado. Se algum corte respeitar a propriedade, basta realizá-lo, e tentar efetuar cortes nos pedaços gerados.

Dica 1: Na verdade só é necessário verificar se um dos lados cortados é um pedaço, pois isso implica que o outro também é, se não for um pedaço vazio (que não contém nenhum caractere).

Dica 2: Tal verificação pode ser realizada percorrendo apenas as bordas do corte, olhando para os caracteres na fronteira do corte.

Assim, para cada corte que vamos tentar realizar, fazemos O(n+m) operações.
Para um dado pedaço, precisamos tentar fazer O(n*m) cortes.
O número de pedaços formados é no máximo 26+26+10 ( Maiúsculas + Minúsculas + Dígitos ).
Portanto, o algoritmo custa O ( (n*m)*(n+m) * (62) ).
Algo em torno do O( n^4 ), porém, tive que fazer bastante limpeza de código para conseguir passar esse problema.

Solução

Testes

Entrada

Saída

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