Topcoder: SRM 492

Topcoder é uma empresa que realiza diversos tipos de competições de programação. A mais famosa, de longe, é o SRM (Single Round Match), uma competição rápida de algoritmos. Além dessa, há competições de design e desenvolvimento de software, além das competições longas de algoritmos (Marathon Matches). Veja o site para mais informações.

O SRM é dividido em 3 fases: código, desafio e testes do sistema. A fase de código dura 75 minutos e consiste em resolver 3 problemas estilo maratona de programação. A diferença é que você submete no escuro, ou seja, sem saber se seu programa passou nos casos de testes do sistema. A fase de desafio te dá uma oportunidade de ganhar uns pontos extras fornecendo casos de teste que possivelmente quebre o código do oponente e dura 10 minutos. Depois disso, os programas de cada competidor são submetidos aos testes do sistema. Tem vários detalhes sobre pontuação que podem ser encontrados aqui .

Eu participo dos SRM’s desde 2007, mas sempre de maneira esporádica. Agora que me aposentei da maratona, decidi continuar praticando para não enferrujar (embora eu ainda programe bastante no meu mestrado). Uma coisa que eu deveria fazer mas nunca tive disciplina suficiente, é o post mortem da competição, ou seja, estudar os editoriais e aprender a fazer os problemas que não consegui durante a competição.

Minha ideia é tentar usar o blog para escrever sobre tais problemas. Sem mais delongas, vou apresentar uma breve descrição e a solução dos problemas que não consegui resolver.

Time Traveling Tour

Dado um grafo ponderado e não-orientado G e uma lista de cidades L, deseja-se encontrar um passeio iniciado no vértice 0, que visite as cidades na ordem em que aparecem em L (o passeio pode conter cidades intermediárias que não necessariamente são visitadas). Há um diferencial porém: nesse passeio você pode viajar no tempo e voltar a uma cidade pela qual já passou, com custo zero. Queremos o passeio de menor custo. Link para o problema.

Se não houvesse essa viagem do tempo o problema seria fácil: ache o menor caminho entre todos os pares de vértices e some a distância entre cidades consecutivas de L.

A solução do editorial, descreve um algoritmo de programação dinâmica. O estado é definido por uma tripla (C, i, j), que representa o menor custo de se sair da cidade C e visitar as cidades L[i], …, L[j]. A resposta do problema é dada por (0, 0, |L|-1).

A sacada dessa abordagem é que não importa qual o caminho feito até chegarmos em C. Vamos inverter o pensamento: podemos ir a uma cidade D e então voltar para a cidade C com custo zero. Logo, a partir de uma dada cidade C, iremos usar outras cidades para visitar trechos de i, … j.

Considere o exemplo abaixo, onde as cidades são identificadas por letras e os números indicam a ordem em que devem ser visitadas. A cidade de partida é ‘A’.

Exemplo: letras são rótulos do vértices; números sobre os vértices representam a ordem em que devem ser visitados; os números em azul sobre as arestas representam os custos.

Podemos ver que uma solução ótima é a seguinte: vai de A a B com custo 3 e visita B, vai então até D com custo 2. Volta no tempo para A e visita C com custo 3. Volta no tempo para A e vai até E com custo 8. O total fica 16.

Em termos da tripla, poderíamos representar (A, 0, 3) como {dist(A, B) + (B, 0, 1)} + {dist(A, C) + (C, 2, 2)} + {dist(A, B) + (B, 3, 3)}. Por sua vez, (B, 0, 1) = (B, 0, 0) + {dist(B, D) + (D, 1, 1)}. A base da recursão é quando i = j ou i > j. No primeiro caso, (C, i, j) = dist(C, L[i]). No segundo significa que já visitamos todas as cidades então (C, i, j) = 0.

Uma observação importante é que {dist(A, B) + (B, 0, 1)} + {dist(A, C) + (C, 2, 2)} + {dist(A, B) + (B, 3, 3)} pode ser reescrita como

(1) {dist(A, B) + (B, 0, 1)} + (A, 2, 3),

pois (A, 2, 3) será recursivamente decomposto até que eventualmente a primeira forma apareça.

Isso reduz nosso trabalho a encontrar uma cidade (no exemplo é B) e um índice k, tal que essa cidade vai visitar as cidades i, …, k. A recorrência então fica:

(C, i, j) = INF
Para cada cidade D :
  Para cada índice k = i ... j :
      (C, i, j) = min {(C, i, j), 
                    dist(C, D) + (D, i, k) + (C, k+1, j)

Há dois problemas: essa recorrência pode ser muito ineficiente para os limites do problema, já que o número de operações fica O(50^5). Outro problema é quando k = j. Nesse caso teremos uma recorrência cíclica, pois chamaremos (D, i, j) que por sua vez pode chamar (C, i, j) novamente.

A solução do competidor those trata esses dois problemas. Note que só precisamos considerar o caso k = j porque pode existir uma cidade para a qual não se volta com a máquina do tempo. Então definimos uma segunda tripla {C, i, j} que corresponde ao menor custo de se visitar as cidades i e j, só que necessariamente voltando no tempo para C pelo menos uma vez.

Como sabemos que {C, i, j} voltará ao menos uma vez usando a máquina do tempo, podemos quebrá-lo em duas partes (antes e depois dessa volta):

(2) {C, i, j} = min{(C, i, k) + (C, k + 1, j)} para algum k = i … j – 1

Agora (C, i, k) e (C, k + 1, j) podem ou “delegar” a tarefa de visitar as cidades i a j para outras cidades ou ele mesmo quebrar em mais pedaços (que seria o equivalente a delegar a tarefa para a própria cidade C).

A recorrência de (C, i, j) fica assim:

(3) (C, i, j) = min{ {D, i, j} + dist(C, D)} para alguma cidade D

Observe que essa abordagem elimina a recorrência cíclica e de quebra reduz a complexidade para O(50^4). O trecho que calcula essa recorrência é o seguinte:

i64 eval2(int C, int i, int j){ 
  if (pd2[C][i][j] != -1) return pd2[C][i][j]; 
  pd2[C][i][j] = INFLL; 
  for(int k=i; k<j; k++)
    pd2[C][i][j] = min(pd2[C][i][j], eval(C, i, k)+ 
                        eval(C,k+1, j));
  return pd2[C][i][j]; 
} 
i64 eval(int C, int i, int j){ 
  if (pd[C][i][j]!=-1) return pd[C][i][j]; 
  if (i == j) return dist[C][L[i]]; 
  pd[C][i][j] = INFINITY; 
  for(int D=0; D<n; D++) 
    pd[C][i][j] = min(pd[C][i][j], dist[C][D]+
                      eval2(D, i, j)); 
  return pd[C][i][j]; 
} 

Sendo que a resposta do problema é dada por eval(0, 0, |L|-1).

A minha ideia era postar uma explicação para o problema mais difícil também, o TimeTravellingGogo. Porém, achei tão difícil e levei tanto tempo para pegar a ideia do problema TimeTravellingTour que desanimei. O próprio autor dos problemas disse que eles estavam bem difíceis. Tanto que somente uma pessoa acertou o problema de 1000 pontos.

É incrível que 31 pessoas tenham acertado o problema TimeTravellingTour! Isso quer dizer que eles tiveram a ideia e implementaram corretamente em 75 minutos! Eu lendo o editorial levei umas 2 semanas só para entender a ideia :/

Os comentários estão fechados.

%d bloggers like this: