Tarefa 2: Bandex

Terça-feira foi o último dia para a submissão da tarefa 2 da disciplina de estruturas de dados.

O problema consistia em simular uma fila mais complexa, onde as pessoas saem pelo começo mas nem sempre entram no final. As pessoas nesse contexto são os alunos da Unicamp, e cada aluno é de um dado ano (2006 até 2010) e pertence a exatamente um grupo de amigos. A regra para entrar na fila é a seguinte: um aluno de um ano $a$, sempre entra na frente de um aluno do ano $b > a$ e atrás de um aluno do ano $c \le a$. A única exceção é que quando algum amigo do seu grupo está na fila, quando o aluno entra na frente deste amigo.

Uma restrição dada no enunciado garante que dois alunos são do mesmo grupo somente se pertencem ao mesmo ano. Essa é uma simplificação importante, pois desta forma garantimos que pessoas do mesmo grupo estão sempre juntas na fila e a ordenação em relação aos anos é mantida.

Minha ideia para esse problema envolvia estruturas de dados diferentes: vetor, lista ligada, pilha e fila de prioridades. Na raíz de tudo temos uma fila de prioridade onde cada elemento (representando os anos) é uma lista ligada. Cada elemento desta lista é uma pilha (representando os grupos). Além disso, mantemos um vetor indexado pelo identificador do grupo apontando para o lugar onde este grupo está na fila. Como os alunos não tinham aprendido fila de prioridades ainda, dei a dica de implementá-la usando 5 filas, uma para cada ano.

Para inserir um aluno, primeiramente verificamos o ano ao qual ele pertence e vamos inserir na lista correspondente. Agora precisamos inseri-lo na frente do seu grupo. Primeiro verificamos se seu grupo está na fila. Se sim, inserimos ele no topo da pilha correspondente ao grupo. Caso contrário, criamos uma pilha para este grupo e colocamos no final da lista ligada.

Para remover um aluno, consideramos a fila com maior prioridade, no caso 2006. Se ela estiver vazia, verificamos a próxima fila. Caso contrário, removemos o topo da primeira pilha. Se a pilha esvaziar, removemos ela da lista ligada.

A complexidade esperada é O(1) para inserção e para remoção. Porém devido a restrições no SuSy, o sistema de avaliação dos programas, não consegui colocar instâncias muito grandes, de forma que algoritmos com inserção O(n), que consiste em procurar o grupo na lista percorrendo-a elemento a elemento, passavam nos testes.

Porém, deixei um teste grande para rodar localmente no meu computador e bonifiquei com 1 ponto as pessoas que passaram nesse teste.

2 respostas a Tarefa 2: Bandex

  1. Caramba!! Então é uma fila de prioridades de filas de pilhas? xDAh, eu fui clicar no enunciado e o link está errado. Tem um h a mais no http!E… Pô, não pode declarar variável global? Eu usei uma vez num lab de MC202! Mas foi só uma vez! =P

  2. kunigas diz:

    Isso mesmo! Nada de variável global, aqui não é maratona não rapá! Huheuhaeuh. Arrumei lá, valeu!

%d bloggers like this: