Feed de notícias

URL

https://www.thehuxley.com/problem/412

Comentários

Nesse problema, iremos receber uma lista de relacionamento com os amigos. Depois receberemos uma lista de postagens. Nossa missão é ordenar essa lista de postagens de acordo com a fórmula dada no problema:

prioridade = relação *0.8 + tempo*0.2

Logo, para cada postagem, precisaremos saber a relação de amizade entre quem fez a postagem e o usuário. Isso significa que precisaremos fazer muitas buscas na primeira lista de relacionamentos que iremos receber.

Além disso, precisaremos construir uma lista com os feeds que iremos dar como resposta.

Como vamos fazer muitas buscas, optei por escolher uma estrutura eficiente para buscas. O ideal seria utilizar um dicionário com uma função de hash. Assim, teríamos buscas esperadas em O(1). Depois disso, a gente calcula a fórmula e colocaria em uma fila de prioridades, assim, a inserção seria em O(log(n)) e já teríamos a nossa resposta ao final de todas as inserções.

Logo, o algoritmo ficaria assim:

• Receber todos os relacionamentos e colocá-los em dicionário
• Para cada postagem recebida, usar o dicionário para recuperar o valor do relacionamento e então calcular a fórmula. O resultado deve ser o critério utilizado para a fila de prioridades.
• Inserir a postagem na fila de prioridades
• Quando terminar de receber todas as postagens, fazer um loop e imprimir as n primeiras postagens da fila de prioridades.

Sobre o map em C++:

Em C++ padrão, só existe a implementação de uma hashtable no C++11. Entretanto, a maratona de programação não suporta essa versão da linguagem. Ou seja, nada de hashtable com tempos de O(1). Uma alternativa é utilizar o map. Em C++, um map é implementado como uma árvore de busca binária balanceada. Mais especificamente, como uma árvore vermelha e preta. Logo, embora ela forneça a abstração de uma estrutura de dados do tipo dicionário, a ordem de complexidade de suas operações respeitam a ordem de complexidade de uma árvore vermelha e preta. Ou seja:

Insertion: O(log n)

Lookup: O(log n)

Deletion: O(log n)

http://stackoverflow.com/questions/222658/multiset-map-and-hash-map-complexity

Sendo assim, para obter a complexidade de uma hashtable, precisaríamos utilizar a classe do C++11: unordered_map. Essa classe é uma implementação de uma hashtable e, portanto, respeita as ordens de complexidade esperadas:

Insertion: O(1) expected, O(n) worst case

Lookup: O(1) expected, O(n) worst case

Deletion: O(1) expected, O(n) worst case

http://www.cplusplus.com/reference/unordered_map/unordered_map/

Entretanto, como nas maratonas, não temos disponível o C++11, optamos por manter a solução utilizando o map.

No Huxley, os casos de testes são pequenos. Mas para testar o seu programa, criei um arquivo de teste que está disponível em https://github.com/r0drigopaes/pa/raw/master/feed_2.in.txt.

A reposta esperada para esse caso é: https://raw.githubusercontent.com/r0drigopaes/pa/master/feed_2.out.txt

O vídeo abaixo, mostra que usando a estratégia acima, você conseguirá rodar esse caso em menos de 2 segundos. (considerando a minha máquina no momento: core i7 2630qm, 8Gb ram. benchmark link )