|
|
Problema A - Cartas Colecionáveis |
Tipo de problema: Árvores/Ordenação
Autor do Problema: Pedro Ribeiro (DCC/FCUP)
O Problema
Dado um conjunto de N operações, que podem ser de
inserção (adicionar uma carta de valor V), remoção
(retirar uma carta de valor V) ou de pergunta (saber qual
a K-ésima carta de maior valor) a tua tarefa é responder
a todas as perguntas, indicando a respectiva carta com número de
ordem K naquele momento.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 1 ≤ N ≤ 200 000 | Número de operações a considerar | |
| 1 ≤ V ≤ 1 000 000 | Valores das cartas |
Solução Base:
A parte mais importante deste problema era perceber como manter
o conjunto de cartas ordenado. Uma primeira hipótese de solução
seria manter o conjunto de cartas num array e sempre que
inseríssemos, removêssemos ou quando fossemos questionados de
qual é a K-ésima carta, ordenaríamos a sequência sempre (antes
de efetuar a devida operação). Assim, para cada operação de
inserção basta colocar o novo valor no final da array e
seguidamente ordenar a array (como a array inicial
está parcialmente ordenada era até possível fazer esta operação
de maneira análoga ao que é feito num insertion-sort
sendo assim a ordenação mais eficiente do que ordenar
completamente a array usando um método de ordenação
tipicamente melhor). Para cada remoção, de maneira semelhante
basta encontrar o valor a remover e seguidamente removê-lo (na
prática implicaria mover todos os elementos seguintes uma
posição para trás na array). Finalmente, o K-ésimo
elemento estará na K-ésima posição da array.
Analisar a complexidade de uma solução destas não é fácil, mas se assumirmos que há no máximo N cartas de cada vez na coleção e que por cada operação gastamos um tempo de O(N) (ou O(N * log(N)) caso seja usado um método diferente para ordenação).
Esta seria uma solução O(N^2) que daria aproximadamente 40 pontos.
Melhorar a Base:
Para poder ter um pouco mais que os 40 pontos basta reparar que
não é necessário estar sempre a ordenar. Apenas precisamos de
ordenar quando tivermos que responder a uma pergunta, enquanto
que na inserção apenas pomos a nova carta no fim da coleção e no
caso da remoção apenas tiramos a carta respetiva. Notem, porém,
que esta solução assume que se vai fazer mais operações de
inserção do que perguntas, caso contrário faz mais sentido
apenas ordenar quando se insere. Em ambos os casos o resultado é
semelhante.
Esta seria uma solução O(N^2) que daria aproximadamente 40 pontos.
Solução Melhor:
A primeira etapa para os 100 pontos passa por perceber que este
problema é um ótimo problema para aplicar o conceito de
árvores. Neste caso, podemos usar uma árvore como uma árvore
binária de pesquisa, onde as inserções e remoções funcionam como
na estrutura de dados clássica. Para responder a perguntas uma
ideia base seria de percorrer a árvore de modo ordenado (do
valor mais pequeno para o maior) até chegar ao K-ésimo
elemento. Notem que com esta solução tanto a inserção como
remoção têm complexidade O(log(N)), mas responder a
perguntas continua a ser O(N), embora seja muito mais
eficiente do que a solução anterior pois não teremos que
percorrer a árvore toda a não ser que se peça o último elemento.
Antes de avançarmos duas notas importantes: A primeira é que podem haver valores repetidos, logo é necessário ter algum cuidado na implementação de uma árvore para poder admitir valores repetidos. Uma possível solução que vamos admitir para o resto deste texto é guardar para cada nó além do seu valor, a quantidade de vezes que esse valor aparece, ou seja, quantas cartas há com o mesmo valor que esse nó na coleção. Assim, quando formos remover um certo valor podemos apenas decrementar este número e caso ele passe a zero retiramos mesmo o nó. Para a inserção fazemos algo análogo incrementando a quantidade caso o valor a inserir já exista. A segunda nota é que com este tipo de solução era possível usar uma estrutura de dados da STL de C++ chamada set (neste caso em específico teria de ser um multiset graças aos valores repetidos). Com esta estrutura temos todas operações implementadas com a mesma complexidade da descrita.
Apesar de tudo ainda temos o fator linear no caso das perguntas, logo a complexidade vai ser a mesma que a anterior ainda que a solução seja melhor.
Esta seria uma solução O(N^2) que daria aproximadamente 60 pontos.
Nota sobre Balanceamento:
Sempre que falamos de árvores binárias de pesquisa também temos
de falar de balancear a árvore. Balancear significa manter a
altura da árvore da ordem do logaritmo do seu número de
elementos para manter as complexidades de inserção e remoção em
tempos logarítmicos (proporcional à altura da árvore). Apesar de
não termos referido isto, anteriormente, há casos onde não
executar este balanceamento pode ser demasiado lento, logo é uma
questão que pode fazer perder alguns pontos
Para efetuar o balanceamento em si basta usar uma variante de uma AVL-tree, por exemplo (esta é das árvores balanceadas mais simples), para se poder adaptar à solução seguinte. Uma alternativa mais viável de ser feita em tempo de concurso (e para quem não souber de cor como implementar uma AVL) passa por uma reconstrução da árvore (dividindo os nós de modo a que a árvore fique balanceada) sempre que a altura da árvore for maior que um certo valor (como um terço do número de elementos na árvore, por exemplo).
Solução Ótima:
Para conseguir chegar aos tão cobiçados 100 pontos é necessário
então melhorar o passo de responder às perguntas para que tenha
uma complexidade de O(log(N)).
Antes de mais vamos assumir que para cada nó sabemos quantas cartas há na subárvore direita e na subárvore esquerda, ou seja, quantas há em todos os nós que são filhos ou filhos de filhos ou ... do filho esquerdo/direito de cada nó. Assim temos
Com este resultado conseguimos "navegar" pela árvore até chegar ao valor pedido. Se estivermos num nó e quisermos encontrar o K-ésimo valor a partir desse nó (onde para responder à pergunta estamos a procurar o K-ésimo valor a partir da raiz) vamos ver primeiro quantas cartas há na subárvore direita. Se forem mais que K, significa que o valor pretendido estará nessa subárvore, pois os valores de todos esses nós são superiores ao valor do nó em questão e de todos os nós na subárvore esquerda. Caso esse número seja menor que K, mas sendo K maior que o número de ocorrências do valor do nó em questão (ou seja o número de cartas com o mesmo valor que o valor do nó) mais o número de cartas na subárvore direita, então o valor deste nó é o valor que pretendemos. Finalmente, caso K seja maior que o número de cartas na subárvore direita mais o número de ocorrências do valor, então estará na subárvore esquerda. Porém, não basta procurar pelo K-ésimo elemento na subárvore esquerda, porque ao pesquisarmos nesta subárvore estamos a "descartar" os elementos da subárvore direita assim como o próprio nó. Logo temos de pesquisar na subárvore esquerda pelo valor K menos o número de cartas na subárvore direita menos o número de ocorrências do valor.
Para tornar um pouco mais claro o que foi explicado no parágrafo anterior, notem que o que estamos a fazer é simplesmente dividir a coleção de cromos em três conjuntos ordenados (idealizando isto a árvore de pesquisa) e de cada vez descobrir se o cromo que procuramos está no primeiro, segundo ou terceiro conjunto. Seguidamente, continuamos a nossa procura pelo conjunto. Assim, conseguimos perceber porque é que no último caso descrito não procuramos K mas sim K menos o número de cartas na subárvore direita menos o número de ocorrências do valor. Isto é então visto que ordem que estamos a considerar é da direita para a esquerda (que equivale a decrescente numa árvore binária de pesquisa), ao considerarmos a subárvore esquerda estamos a ignorar valores tanto do próprio nó como da subárvore direita que aparecem primeiro. Em termos dos três conjuntos descritos atrás, significa que o valor que procuramos está no nosso terceiro conjunto, e por isso queremos procurar la o valor K menos o número de elementos no primeiro e segundo conjuntos.
Com esta solução cada operação de pesquisa tem como complexidade a altura máxima da árvore (porque estamos sempre a descer na árvore de pesquisa). Sendo esta altura da ordem do logaritmo temos então uma solução melhor que a anterior.
Esta seria uma solução O(N * log(N)) que daria aproximadamente 100 pontos.
Solução Alternativa:
A beleza de resolver problemas está também no facto que cada
problema admite várias soluções. Este não é exceção e admite uma
solução muito curiosa. Seguindo um tema que já apareceu em
problemas anteriores de qualificações (mas também como uma se
várias soluções) são os chamados buckets. Buckets,
ou em português "baldes", correspondem a dividir o conjunto de
números em vários pequenos conjuntos de tamanho mais
pequeno.
Como o valor máximo de qualquer carta era de 1,000,000 isto permitia-nos considerar uma array de 1,000,000 inteiros e contar assim quantas cartas existem de cada valor marcando esse valor na array. Apesar de isto ser muito eficiente para inserções e remoções, para responder a perguntas temos o mesmo problema que tínhamos na solução anterior para 60 pontos usando árvores. Logo temos de melhorar a resposta a perguntas. Por outro lado se apenas mantivéssemos a lista de cromos e fossemos ordenando quando necessário como na Solução Base apesar de termos respostas a perguntas eficientes, a inserção e remoção obrigam-nos (mais tarde ou mais cedo) a ordenar o conjunto. Logo também não é opção para os 100 pontos (como já vimos, claro).
É aqui que entram os buckets como um "melhor entre dois mundos", ou seja que combina as duas ideias anteriores. A ideia é dividir a array anterior em várias mais pequenas. Um valor que normalmente se utiliza é a raiz quadrada do número total de elementos (ou seja, vamos ter sqrt(V) baldes cada um com sqrt(V) elementos, excetuando talvez o último balde de todos, mas vamos ignorar este pormenor nesta descrição, onde V é o valor máximo de um elemento). Assim temos um primeiro balde que vai admitir os cromos com valores entre 1 e sqrt(V), um segundo balde que admite os cromos com valores entre sqrt(V) e 2 * sqrt(V) e por ai fora. Para cada balde vamos guardar quantos elementos tem e uma lista ordenada de elementos.
Agora a ideia é atualizar cada balde separadamente. Ou seja, para inserir um novo elemento basta calcular em que balde se incluirá (o que pode ser feito com algumas contas, mas caso sejam preguiçosos, percorrer os vários baldes começando do primeiro para o último também é eficiente o suficiente) e finalmente incrementar o número de elementos e inserir o novo cromo na lista ordenada de elementos (como se fazia na Solução Base). Para remover, novamente encontra-se o balde e finalmente decrementa-se o número de elementos e remove-se o valor a retirar da lista ordenada. Nesta altura podem levantar a questão: mas isto não é basicamente equivalente à Solução Base? O que mudou? O que muda aqui, e é um pormenor importante, é que só estamos a atualizar no máximo sqrt(V) elementos de cada vez e não N. Assim, a complexidade é muito menor. Finalmente, para respondermos a perguntas vamos fazer uma "navegação" semelhante à da Solução Ótima. Começando no primeiro balde, se o número de elementos neste balde for maior que K, então a resposta estará dentro deste balde e por isso basta pesquisar na lista ordenada. Caso contrário, vamos "descartar" estes elementos como fizemos anteriormente, ou seja, vamos procurar pelo valor K menos o número de elementos neste balde, no balde seguinte. Seguindo este raciocínio eventualmente chegamos ao balde que contém o valor pretendido.
Três pequenas notas antes de terminarmos: Primeiro, que apesar de não o ter referido, é necessário ter atenção a vários cromos com o mesmo valor na implementação anterior. Por exemplo, se guardarmos valores repetidos nas listas ordenadas dos baldes, podemos ter mais que sqrt(V) elementos num balde. Segundo, a última operação descrita pode ser ainda mais otimizada seguindo um "padrão de navegação" semelhante ao da Solução Ótima, mas esta implementação é um pouco mais trabalhosa e requer algum cuidado. Última nota, assim como esta solução, temos várias outras com conceitos semelhantes que se podiam aplicar aqui: segment trees, fenwick trees, são exemplos de estruturas um pouco mais complexas mas que também poderiam ser usadas para resolver o problema com uma abordagem semelhante ao dos buckets.
Esta seria uma solução O(N * sqrt(V)) que daria aproximadamente 100 pontos.
Ligações interessantes: