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.

view plaincopy to clipboardprint?

1. using System;  
2. using System.Collections;  
3.   
4. namespace FileFixIt  
5. {  
6.   class Program  
7.   {  
8.       static void Main(string[] args)  
9.       {  
10.           int nCases = int.Parse(Console.ReadLine());  
11.           for (int iCase = 1; iCase <= nCases; iCase++)  
12.           {  
13.               string[] part = Console.ReadLine().Split(null);  
14.               int n = int.Parse(part[0]);  
15.               int m = int.Parse(part[1]);  
16.               int nCmd = 0;  
17.   
18.               Hashtable ht = new Hashtable();  
19.               for (int i = 0; i < n; i++)  
20.                   CreateDir(ht, Console.ReadLine());  
21.               for (int i = 0; i < m; i++)  
22.                   nCmd += CreateDir(ht, Console.ReadLine());  
23.               Console.WriteLine("Case #{0}: {1}", iCase, nCmd);  
24.           }  
25.       }  
26.   
27.       static int CreateDir(Hashtable ht, string dir)  
28.       {  
29.           int nCmd = 0;  
30.           int j = 0;  
31.           while (j < dir.Length)  
32.           {  
33.               j = dir.IndexOf('/', j + 1);  
34.               if (j == -1)  
35.                   j = dir.Length;  
36.               string dpart = dir.Substring(0, j);  
37.               if (!ht.Contains(dpart))  
38.               {  
39.                   ht.Add(dpart, null);  
40.                   nCmd++;  
41.               }  
42.           }  
43.           return nCmd;  
44.       }  
45.   }  
46. }  

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;
      }
  }
}