Google Code Jam 2010: File Fix-It

File Fix-It foi o primeiro problema da rodada 1B, e um dos mais simples da competição.

O enunciado completo está no site oficial, mas pode ser resumido da seguinte forma: o seu programa recebe duas listas de nomes de diretório (todos a partir da raiz e usando '/' como separador das partes), uma com os nomes dos diretórios que já existem e outra com os nomes dos diretórios que se deseja criar, e deve informar quantas operações de criação de diretório (mkdir) serão necessárias (considerando que cada operação cria somente a última parte do nome).

Usando o exemplo: se existe somente /home e você quer criar os diretórios /home/gcj/finals e /home/gcj/quals, você vai precisar de três operações (criando /home/gcj, /home/ccj/finals e /home/cgj/quals).

O problema pode ser resolvido mantendo uma lista com os nomes dos diretórios existentes. Inicialmente esta lista é preenchida com os nomes gerados a partir dos diretórios já existentes (tomando o cuidado de não incluir duplicatas). Depois é só gerar os nomes dos diretórios a partir dos que queremos criar e procurar na lista; se não achar incrementar o número de operações e colocar o diretório na lista.

Voltando ao meu exemplo. Inicialmente colocamos /home na lista. Para criar /home/gcj/finals é necessário ter /home, /home/gcj e /home/gcj/finals; o primeiro já existe mas os dois últimos não - são duas operações de criação. Para criar /home/gcj/quals é necessário ter /home, /home/gcj e /home/gcj/quals; os dois primeiros já existem (o segundo foi criado no passo anterior) - chegamos assim ao total de 3 operações.

A minha solução na competição foi meio estúpida, pois eu guardei as partes mantendo a estrutura de árvore e implementei esta árvore na raça, alocando e liberando manualmente memória.

A solução abaixo está feita em C# e aproveita a hashtable disponível no .Net Framework para otimizar as buscas.

using System;
using System.Collections;

namespace FileFixIt
{
  class Program
  {
      static void Main(string[] args)
      {
          int nCases = int.Parse(Console.ReadLine());
          for (int iCase = 1; iCase <= nCases; iCase++)
          {
              string[] part = Console.ReadLine().Split(null);
              int n = int.Parse(part[0]);
              int m = int.Parse(part[1]);
              int nCmd = 0;

              Hashtable ht = new Hashtable();
              for (int i = 0; i < n; i++)
                  CreateDir(ht, Console.ReadLine());
              for (int i = 0; i < m; i++)
                  nCmd += CreateDir(ht, Console.ReadLine());
              Console.WriteLine("Case #{0}: {1}", iCase, nCmd);
          }
      }

      static int CreateDir(Hashtable ht, string dir)
      {
          int nCmd = 0;
          int j = 0;
          while (j < dir.Length)
          {
              j = dir.IndexOf('/', j + 1);
              if (j == -1)
                  j = dir.Length;
              string dpart = dir.Substring(0, j);
              if (!ht.Contains(dpart))
              {
                  ht.Add(dpart, null);
                  nCmd++;
              }
          }
          return nCmd;
      }
  }
}