Google Code Jam 2008 - Train Timetable

Continuando a minha apresentação dos problemas do Google Code Jam 2008, discuto agora o segundo problema. Este era o problema mais simples e teve a taxa mais alta de acertos.

Descrição do Problema

A descrição do problema é bastante clara:

• Trens circulam entre duas estações
• Após chegar uma estação, um trem precisa de T minutos para poder seguir no sentido contrário
• Fornecidos todos os horários de partida e chegada dos trens, determinar o número inicial de trens de cada lado para não faltem trens para cumprir os horários.

Um detalhe que complica um pouco é o formato da entrada: para cada estação é fornecida uma lista dos trens que partem dela, com o horário de partida e o horário de chegada na outra estação.

Resolvendo o Problema

Minha solução para o problema consistiu em montar para cada estação uma tabela dos trens partindo e dos trens prontos para partir (levando em conta o horário de chegada e o tempo de virada). Esta tabela é ordenada em primeiro lugar pelo tempo, quando mais de um evento ocorrer no mesmo tempo as partidas devem vir depois (para aproveitar os trens que ficaram prontos no mesmo minuto).

Feitas as tabelas, é só percorrer verificando onde falta trem.

Implementando a Solução

Para facilitar a ordenação, converti os horários para minutos, múltipliquei por 10 e coloquei na unidade um dígito para colocar as partidas depois.

#define MAX_TRIPS       100
#define TRAIN_READY     1
#define TRAIN_DEPARTURE 2

int StationA [2*MAX_TRIPS];
int StationB [2*MAX_TRIPS];
int nSA, nSB;

A conversão de HH:MM para os décimos de minuto é trivial:

int EncodeTime (char *s)
{
  return (s[0]-'0')*10*600 + (s[1]-'0')*600 +
         (s[3]-'0')*100 + (s[4]-'0')*10;
}

Para cada trem na lista de entrada de uma estação é preciso colocar uma entrada na tabela desta estação (com a partida) e uma entrada na tabela da outra estação (com o horário em que o trem poderá ser reutilizado):

scanf ("%d", &t);
t *= 10;
scanf ("%d %d", &nA, &nB);
nSA = nSB = 0;
for (i = 0; i < nA; i++)
{
   scanf ("%s %s", depart, arrive);
   Register (StationA, nSA, EncodeTime(depart)+TRAIN_DEPARTURE);
   nSA++;
   Register (StationB, nSB, EncodeTime(arrive)+t+TRAIN_READY);
   nSB++;
}
for (i = 0; i < nB; i++)
{
   scanf ("%s %s", depart, arrive);
   Register (StationB, nSB, EncodeTime(depart)+TRAIN_DEPARTURE);
   nSB++;
   Register (StationA, nSA, EncodeTime(arrive)+t+TRAIN_READY);
   nSA++;
} 

O registro de um evento em uma tabela é feito por inserção simples:

void Register (int *tabEvt, int nEvt, int event)
{
  int i;

  for (i = nEvt; i > 0; i--)
      if (tabEvt[i-1] <= event)
          break;
  if (i < nEvt)
      memmove (tabEvt+i+1, tabEvt+i, (nEvt-i)*sizeof(int));
  tabEvt[i] = event;
} 

Por último temos a contagem dos trens:

int Trains (int *Station, int nEvt)
{
  int i, need, cur;

  for (i = need = cur = 0; i < nEvt; i++)
  {
      if ((Station[i] % 10) == TRAIN_READY)
          cur++;
      else if (cur == 0)
          need++;
      else
          cur--;
  }
  return need;
}