Nome: Achando os assentos
Link: http://br.spoj.pl/problems/ASSENTOS/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 2.11
Memória usada: 3.1M
Colocação alcançada: 36
Tentativas: 4
Comentário:
Esse é um exercício interessante.
Trata-se de encontrar não a submatriz com maior soma, porém a submatriz com uma soma de resultado X de menor tamanho.
Eu estudei um algoritmo chamado Kadane 2D e Kadane 1D, porém a aplicação e o objetivo do mesmo é outro. De qualquer maneira dá pra tirar proveito da ideia utilizada.
O tutorial que segui do Kadane eu encontrei aqui:
http://marathoncode.blogspot.com.br/2012/09/algoritmo-de-kadane-2d.html
Repito: O objetivo do Kadane é outro, porém dá para adaptar a esse exercício.
Dicas:
- Procurem transformar os caracteres em valores, são mais manipuláveis.
- Uma boa ideia é transformar a matriz bidimensional em unidimensional, fazendo assim uma verificação linear. Vale notar que será preciso verificar cada linha, e cada linha somada com cada linha adjacente.
- Para uma maior precisão na procura pelo tamanho certo serão necessários dois índices, um para manipular o começo da submatriz e outro para manipular o final. Apenas um índice não será suficiente.
Nenhum comentário:
Postar um comentário