quinta-feira, junho 10, 2010

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

Nenhum comentário: