Olá meus amigos nerds. Hoje vamos tentar descobrir qual é o maior número que podemos formar apagando D dígitos de um número de N dígitos. Já que é isso que o problema 3237. Apagando e ganhando nos pede para fazer.
Eu tenho uma história engraçada com esse problema. Em uma regional da maratona de programação do ICPC eu consegui resolver-lo, mas meu colega de time me convenceu que minha solução estava errada (mesmo estando certa). No final, faltou justamente esse problema para passarmos de fase. Quem mandou eu ser burro kkk.
Eu tenho uma história engraçada com esse problema. Em uma regional da maratona de programação do ICPC eu consegui resolver-lo, mas meu colega de time me convenceu que minha solução estava errada (mesmo estando certa). No final, faltou justamente esse problema para passarmos de fase. Quem mandou eu ser burro kkk.
Solução
Existe uma solução trivial para esse problema:
Seja num o número de N digitos dado
max = 0
while d > 0
d--
m = 0
for i in len(num)
Seja x o número obtido apagando o i-ésimo digito de num
m = maximo(x, m)
max = maximo (m, max)
Obviamente ela não passa no tempo! Isso porque a comparação entre x e m tem complexidade N (o número de bits de x), sendo a complexidade do algoritmo O(d*N^2), o que é muito ineficiente para o problema.
Pense comigo, dados dois números com a mesma quantidade de dígitos, qual deles é maior? Aquele que tem o digito mais a esquerda maior, oras. Essa simples observação nos fornece um algoritmo guloso capaz de responder o problema. Se o primeiro dígito da esquerda for menor que o segundo, a decisão de apagar o primeiro dígito é ótima. Assim:
Seja num uma lista com os N digitos dados
i = num.begin()
j = i++
while i != num.end()
if == 0
pare
if num[i] < num[j]
apaga(num[i])
else
i++
Se conseguirmos apagar os d dígitos usando a observação do parágrafo anterior o problema está resolvido. Pode ocorrer que não consigamos fazer isso, nesse caso, os dígitos do início do número estaram em ordem estritamente decrescente. Basta então repetir o processo acima do fim para o inicio do número para apagar os dígitos que faltam.
Observe que o algoritmo acima é muito mais rápido, tendo complexidade O(N).
Seja num o número de N digitos dado
max = 0
while d > 0
d--
m = 0
for i in len(num)
Seja x o número obtido apagando o i-ésimo digito de num
m = maximo(x, m)
max = maximo (m, max)
Obviamente ela não passa no tempo! Isso porque a comparação entre x e m tem complexidade N (o número de bits de x), sendo a complexidade do algoritmo O(d*N^2), o que é muito ineficiente para o problema.
Pense comigo, dados dois números com a mesma quantidade de dígitos, qual deles é maior? Aquele que tem o digito mais a esquerda maior, oras. Essa simples observação nos fornece um algoritmo guloso capaz de responder o problema. Se o primeiro dígito da esquerda for menor que o segundo, a decisão de apagar o primeiro dígito é ótima. Assim:
Seja num uma lista com os N digitos dados
i = num.begin()
j = i++
while i != num.end()
if == 0
pare
if num[i] < num[j]
apaga(num[i])
else
i++
Se conseguirmos apagar os d dígitos usando a observação do parágrafo anterior o problema está resolvido. Pode ocorrer que não consigamos fazer isso, nesse caso, os dígitos do início do número estaram em ordem estritamente decrescente. Basta então repetir o processo acima do fim para o inicio do número para apagar os dígitos que faltam.
Observe que o algoritmo acima é muito mais rápido, tendo complexidade O(N).
Implementação
Observe que em c++ list.erase(it) apaga e invalida o iterador o que nos força a função apaga para evitar problemas.
Nenhum comentário:
Postar um comentário