quarta-feira, setembro 30, 2009

A Importância das Continuidade nos Descontos e Acréscimos

Ao fazer o post de ontem sobre o engano da Soldafria nas suas promoções, eu acabei lembrando de algo mais sério e conceitual.

Como muitas empresas, a Soldafria pratica descontos por quantidade (algo louvável) mas, conscientemente ou não, acaba incorrendo em uma situação clássica. Vou tomar como exemplo os preços do transistor 2N2222 (um transistor de uso geral em aplicações de amplificação de baixa potência e chaveamento):



terça-feira, setembro 29, 2009

Promoções Insólitas

Parece que a Soldafria está oferecendo promoções dignas do The Daily WTF:


Seminário: C & C++ Para Sistemas Embarcados 2009

No dia 14 de novembro teremos a segunda edição deste evento organizado pela Tempo Real. E novamente teria a honra de apresentar uma palestra. O evento do ano passado foi muito bom (como relatei aqui), o que só aumenta a responsabilidade.



Detalhes e a grade de palestras podem ser vistas em

http://www.temporealeventos.com.br/?area=118

O objetivo da minha palestra será dar uma passada sobre as formas mais comuns de ligação de microcontroladores a outros dispositivos, apresentando exemplos em C.

Lembrando, este evento surgiu de ideias das comunidades Grupo C&C++ Brasil e do Portal Embarcados.

domingo, setembro 27, 2009

Os Álbuns dos Beatles - Beatles For Sale


A maratona continua, e no final de 64 é lançado o quarto álbum, gravado entre excursões pelo mundo à fora. Nada mais apropriado que as feições cansadas da foto da capa e o título "Beatles à venda".

Os Beatles retornam ao esquema de mesclar canções próprias (todas assinadas Lenon/McCartney) com convers extraídos do repertório dos shows. As novas canções foram compostas nos intervalos das excursões; tipicamente um dos dois tinha a ideia inicial e a apresentava para o outro que ajudava a completá-la.

A sofisticação das composições e gravações continua, com os Beatles estando mais presentes nas sessões de edição e mixagem. As músicas de Lenon acentuam o caráter mais auto-biográfico e sombrio.

Como em "A Hard Day's Night", apesar das gravações terem sido feitas em quatro canais o CD foi lançado com a mixagem mono.

sábado, setembro 26, 2009

Livro de Setembro: The Dangerous Transmission


A última vez que comentei sobre os Hard Boys, eu tinha acabado de ler uma versão facsimile de 1929. O livro ao lado representa a outra ponta da série, tendo sido publicado em 2004.

No post anterior eu mencionei a série "clássica" de 57 volumes, publicada de 1927 a 1979. Em 1979 uma batalha judicial levou os Hardy Boys para uma outra editora, surgindo os "Hard Boys Digests", publicados de 1979 a 2005, do qual o volume ao lado faz parte.

Outras séries foram publicadas em paralelo, notadamente "Hardy Boys Casefiles" que mudou radicalmente o enfoque e a personalidade dos Hardy Boys, mas isto fica para outra ocasião.

domingo, setembro 20, 2009

Os Álbums dos Beatles: A Hard Day's Night


Menos de dois anos após o primeiro compacto, saia o terceiro álbum dos Beatles. Desta vez todas as composições eram próprias (e, caso único, todas de Lenon-McCartney). John Lenon domina a composição sendo responsável pela maioria das músicas.

Com a Beatlemania em seu auge, "A Hard Day's Night" contém em seu lado A as músicas do filme de mesmo nome (que aqui nestas terras recebeu o infame nome "Os Reis do Ie-ie-ie"). O nome original vem de um malaproprismo de Ringo (menção incorreta de uma expressão corriqueira).

Além da crescente sofisticação das composições, o som é marcado pela nova guitarra de 12 cordas de George. Algumas músicas (I'll Cry Instead, Things We Said Today) revelam preocupações além do "garoto ama garota".

Embora todas as músicas tenham sido gravadas em quatro canais, o que permite uma mixagem estéreo decente, o álbum foi lançado em CD na versão mono.

sábado, setembro 19, 2009

Registro Eletrônico de Ponto - Final

Concluindo os meus comentários sobre a Portaria 1.510 do Ministério do Trabalho e Emprego, apresento aqui a minha visão quanto ao impacto desta portaria para os fornecedores e compradores de sistemas de registro eletrônico de ponto.

As normas estabelecidas pela portaria inclui requisitos bem diversos em relação à maioria dos sistemas em uso. É bastante provável que não esteja sendo comercializado no momento um sistema que atenda à portaria ou mesmo que possa ser adaptado facilmente. Alguns requisitos de hardware, como a impressora integrada, a memória à prova de apagamento e alteração e mesmo a porta USB não me parecem ser de fácil acréscimo a equipamentos já existentes, particularmente modelos com tecnologia mais simples ou antiga.

Isto significa que os empregadores que já utilizam sistema eletrônico de ponto provavelmente terão que substituir os seus equipamentos. Os requisitos técnicos e os novos procedimentos administrativos irão certamente pressionar custos e elevar preços.

Quem está em processo de adquirir um sistema eletrônico de marcação de ponto certamente desejará uma garantia de que o investimento poderá ser aproveitado após a entrada em vigor das regras.

Os fabricantes de equipamento terão que investir no desenvolvimento de sistemas que atendam às novas normas. Alguns destes fabricantes revendem atualmente modelos estrangeiros, cuja adequação poderá ser mais difícil. Não pode ser ignorada a possibilidade das normas serem revistas, adiadas ou abandonadas antes de entrar em vigor.

Os empregadores, além dos custos dos equipamentos, terão os custos associados à impressão (não somente o papel mas também os procedimentos operacionais relativos à sua compra, estocagem e substituição periódica).

Para o trabalhador, existe a perspectiva de passar a ter um comprovante físico das marcações de ponto e a expectativa de uma fiscalização mais efetiva.

Para todos os envolvidos existirá o desgaste da implantação e depuração de um novo sistema, tecnicamente mais complexo que os atuais.

Não será surpresa se algumas empresas decidirem retornar a métodos não eletrônicos, pelo menos enquanto esperam a poeira abaixar.

sexta-feira, setembro 18, 2009

Registro Eletrônico de Ponto - Parte 4

Prosseguindo com os meus comentários sobre a Portaria 1.510 do Ministério do Trabalho e Emprego (MTE), comento agora a certificação do Registrador Eletrônico de Ponto (REP).

Como vimos na parte anterior, existem normas muito específicas para o hardware e software do REP; a Certificação visa verificar se um equipamento atende estas normas.


quinta-feira, setembro 17, 2009

Registro Eletrônico de Ponto - Parte 3

Prosseguindo com os meus comentários sobre a Portaria 1.510 do Ministério do Trabalho e Emprego, analiso aqui os meus entendimentos sobre o hardware e software do Registrador Eletrônico de Ponto (REP).

Como vimos nas partes anteriores, o REP é o equipamento onde o ponto é registrado; ele deve servir exclusivamente para isto.

quarta-feira, setembro 16, 2009

Registro Eletrônico de Ponto - Parte 2

Continuo aqui a colocar os meus comentários sobre a Portaria 1.510 do Ministério do Trabalho e Emprego, falando agora sobre as consequências do ponto de vista de sistema.

A portaria divide um Sistema de Registro Eletrônico de Ponto (SREP) em duas grandes partes: o Registrador Eletrônico de Ponto (REP) e o Programa de Tratamento de Registro de Ponto.

terça-feira, setembro 15, 2009

Registro Eletrônico de Ponto - Parte 1

No final de agosto o Ministério do Trabalho e Emprego publicou a Portaria 1.510, que regulamenta o Registro Eletrônico de Ponto. As normas estabelecidas por esta portaria afetam significativamente o registro de ponto de forma eletrônica, em termos de operação, sistema, hardware e software. Além disso, estabelece um "Certificado de Conformidade" obrigatório para os equipamentos (e os respectivos "programas residentes").

Neste post e nos próximos vou colocar o meu entendimento e comentários sobre esta portaria.

segunda-feira, setembro 14, 2009

Adeus ao Google Code Jam 2009

Não é de hoje que eu me meto a tentar fazer coisas demais ao mesmo tempo e acabo fazendo nada ou muito pouco. Apesar dos post que eu coloquei por aqui, a verdade é que me preparei muito mal e estive sempre desfocado nas provas.

Para a primeira rodada, o regulamento estipulava três tentativas (sexta, sábado e domingo), com cada concorrente podendo participar de duas. Minha inscrição era para sábado e domingo, já prevendo que estaria cansado na sexta à noite.

Na sexta recebi e-mail avisando que estava liberada a participação nas três tentativas. Acompanhei desde o começo a prova de sexta à noite, mas não consegui enxergar como atacar nenhum dos três problemas.

No sábado eu estava com uma pequena reforma no jardim andando, o que certamente não ajudou. Por falta de planejamento, não almocei antes (a prova começou às 13:00) e portanto tive o incômodo da fome. Consegui resolver o primeiro problema (o mais fácil) mas demorei um tempo grande (1:45) devido a besteirinhas. Com 45 minutos sobrando, ataquei o terceiro problema e não concluí a tempo. Por alguns instantes tive a ilusão de ter perdido por falta de cinco minutos, mas assim que a prova foi liberada para treino descobri que a minha solução estava incorreta (por não ter lido direito o enunciado).

Sobrou a última tentativa no domingo - e eu confundi o horário! Ao iniciar a prova já tinha perdido uns 45 minutos. Novamente ataquei primeiro o primeiro problema (o mais fácil), desta vez consegui resolver mais rápido (1:15), mas falhei na primeira tentativa por não tratar corretamente um caso de contorno. Comecei a atacar o terceiro problema com meia hora restando, mas abandonei quando faltavam 5 minutos.

O mais interessante é que com a desclassificação veio uma sensação de alívio, por ter uma coisa a menos a tocar.

Pretendo ainda comentar no blog algumas das questões desta rodada. No próximo ano só vou participar se tiver conseguido me preparar de verdade.

sábado, setembro 12, 2009

Os Álbums dos Beatles - With The Beatles


Por mais surpreendente que possa parecer nos dias de hoje, os planos de George Martin e Brian Epstein eram para os Beatles lançarem dois LPs e quatro compactos por ano. Considerando que os Beatles faziam questão de gravar material próprio, isto exigia uma grande capacidade de composição - e isto não faltou neste início de carreira.

Oito meses após o lançamento de Please Please Me era lançado With The Beatles, com oito novas composições próprias. Entre os dois, dois compactos ('From Me To You'/'Thank You Gir'l e 'She Loves You'/'I'll Get You'). Uma semana depois, mais um compacto ('I Want To Hold Your Hand'/'This Boy'). E o LP não continha nenhuma das seis músicas dos compactos!

"With The Beatles" foi para o topo das paradas, substituindo "Please Please Me". Com estes dois álbums os Beatles ocuparam o topo por 51 semanas consecutivas.

Várias músicas deste disco tiveram uma número grande de takes e receberam sobreposições (overdubs). No último dia de gravação começou a ser usado gravador de quatro faixas, o que aumentava a flexibilidade tanto da gravação quanto da mixagem. Os Beatles começavam a fugir do "som ao vivo" do primeiro LP e partir para obras mais complexas.

Embora algumas destas músicas sejam consideradas menores (tanto pelos Beatles como por críticos) é evidente o avanço dos Beatles como compositores e interpretes.

Vamos às músicas:

It Won't Be Long

Composta principalmente por John, que assume o vocal solo, contém algumas características típicas dos primeiros sucessos, como o formato pergunta-e-resposta e os "yeah-yeahs" (que fizeram o estilo ser chamado de "iê-iê-iê" no Brasil).

All I've Got to Do

Composição de John, cantada pelo próprio. Nas palavras dele, uma música feita para o mercado americano pois telefones não faziam parte da vida dos garotos ingleses.'

John estava tentando copiar o estilo de Smokey Robinson (compositor de "You Really Got A Hold On Me", também presente no disco). Nos primeiros discos dos Beatles era comum eles adorem os estilos dos seus ídolos, que rapidamente ultrapassaram.

All My Loving

Composta e cantada por Paul, é uma espécie de country acelerado, o que é destacado pelo solo de George. Faz até hoje grande sucesso nos shows de Paul, de alguma forma a música parece convidar quem a escuta a cantar junto.

Don't Bother Me

A estreia de George como compositor. Com uma temática mais sombria que as músicas dos Beatles na época, nunca foi considerada grande coisa por George. O clima da música é gerado por um vocal "dobrado" de George, forte reverbação nas guitarras e alguns instrumentos diferenciados na percurssão.

Little Child

Composta por Jonh e Paul para ser cantada por Ringo, acabou sendo cantada por eles mesmos, que a consideravam uma canção menor, apenas para completar o álbum (filler). A harmônica de John tem bastante destaque; quem toca o piano é Paul.

Till There Was You

Cover de uma balada sem guitarras elétricas, mostrando a versatilidade dos Beatles em atingir diversos tipos de plateia. O vocal é de Paul.

Uma curiosidade: Beto Guedes gravou uma versão em português (com um forte sotaque mineiro) chamada "Quanto Te Vi" - veja no YouTube.

Please Mister Postman

Um cover que fazia inicialmente parte das apresentações ao vivo no Cavern. Vocal principal de John ("double tracked").

Roll Over Beethoven

Como disse John, se você quiser chamar rock and roll de outra coisa, chame de Chuck Berry. Cover com George nos vocais.

Hold Me Tight

Composta principalmente por Paul (que faz o vocal principal). Considereda fraca por eles mesmos.

You Really Got A Hold On Me

Outro cover, com vocais soberbos de John e George. George Martin toca o piano.

I Wanna Be Your Man

Composição que John e Paul fizeram para os Rolling Stones (e completada num canto de sala na frente dos Stones!), acabou sendo aproveita para ser o vocal de Ringo no disco.

Devil In Her Heart

George assume os vocais deste cover.

Not A Second Time

Música e vocais (double tracked) de John. Mais uma vez, John estava tentando copiar o estilo de Smokey Robinson.

Money

Para completar o disco, um cover enérgico com Lenon mais uma vez nos vocais e várias sobreposições de piano por George Martin.

Projetos com Sucesso - IV

Fechando esta série de posts, algumas considerações sobre atitudes do projetista que acredito colaborarem para um projeto ter sucesso. Esta lista vem principalmente em resposta a situações que me incomodam tanto ao gerenciar outras pessoas como ao analisar o meu próprio comportamento.

Preocupe-se com o Sucesso do Projeto

Um projeto bem sucedido provavelmente terá boas consequências. Pode ser um reconhecimento vindo de outros, um aumento na auto-estima ou a simples sensação agradável de ter feito algo que deu certo.

Já um projeto mal sucedido, mesmo que não seja por sua causa, provavelmente o prejudicará.

Dentro das suas possibilidade, lute para que o projeto tenha sucesso.

Não Seja Ingênuo

Este é um conselho duro de dar, pois a ingenuidade é uma coisa muito pura e bonita. Mas ela traz problemas sérios nos projetos. Não assuma que todos os envolvidos estão interessados no sucesso do projeto. Valide o que se fala com o que é feito. Documente decisões, reuniões e visitas.

Você precisa ter cuidado redobrado nos contatos com clientes. Já vi pequenos deslizes serem silenciosamente registrados por pessoas sorridentes que posteriormente os usam para atacar o profissional sem nenhuma piedade.

Se algo der errado, o ingênuo é a pessoa perfeita para ser o "bode expiatório", pois estará totalmente desprotegida.

Tome Cuidado com Preconceitos

Não estou falando especificamente de preconceitos de raça ou religião (que infelizmente ainda ocorrem) mas de qualquer tipo de julgamento precipitado com base em aspectos irrelevantes. Aparência e modo de falar são duas fontes muito comuns disso. Na nossa área somam-se a escolha de linguagens, ambientes e ferramentas.

Lembre-se que isto vale para os dois lados e tanto para indivíduos como empresas. Não pré-julgue os outros.

Tenha Senso de Urgência

Somos todos forçados a enfrentar no dia a dia uma série de "falsas urgências", tipicamente aquelas em que alguém "senta em cima" de uma decisão por semanas ou meses e depois quer os resultados "para ontem". Uma consequência nefasta disto é o sentimento contrário, o de que prazo é irrelevante, tanto faz concluir um projeto hoje, amanhã ou na semana que vem (afinal o salário é o mesmo...).

Embora na maioria dos casos um prazo não seja questão de vida ou morte, com frequência temos prazos importantes sejam por eventos externos (fora do controle de todos), por considerações econômicas ou mesmo por motivos psicológicos. Um pequeno exemplo é que terminar algo sexta feira à tarde significa concluir dentro da semana; terminar na manhã da segunda seguinte significa deixar escorregar para a próxima semana.

Além da sensibilidade a estes prazos importantes, o desenvolvedor deve estar sempre visando o término do projeto. É mais ou menos com o "instinto assassino" de um centro-avante: o que todo mundo quer é que ele conclua a jogada e faça o gol, não que fique correndo e driblando sem produzir resultado.

Mantenha a Concentração

Depois da incompetência, a fonte mais comum dos erros é a distração. Leia com atenção as especificações. Pense antes de codificar. Releia o que você codificou.

Os erros por distração, quando ocorrem com frequência, irritam quem está companhando o andamento do projeto, que acaba concluindo que está diante de incompetência.

Tenha cuidado especial em conjugar Concentração com o Senso de Urgência; a tendência das pessoas é em se fixar em somente uma delas e sacrificar a outra.

Não Tenha Medo de Pedir Ajuda

Um clássico no The Daily WTF é a história de Paula Bean, a programadora que em vários meses produziu apenas meia dúzia de linhas de código (e com um erro de ortografia na mensagem). Durante todo o tempo ela informava aos supervisores e colegas que o projeto estava andando bem.

Já observei cousa semelhante (em menor escala): ao enfrentar uma tarefa para qual não está preparada a pessoa fica insistindo sem resultados enquanto finge estar avançando. Se você perceber que está "empacado" busque orientação. Você vai aprender mais rápido, o projeto vai avançar e todos ficarão mais felizes.

Mantenha Controle do Estado do Projeto

Independente de um cronograma formal, o projetista deve ter sempre claro o que já foi feito e o que falta fazer. É extremamente irritante alguém dizer que o projeto "está pronto" e quando se pergunta sobre alguma parte específica receber respostas como "esta parte ainda não" ou "esqueci disto".

Junto com esta lista de pendências você deve ter as suas estimativas de prazo, mesmo que seja para o seu próprio controle. Uma meta ajuda a focar o esforço. Ao final do projeto compare as suas estimativas com o real; onde tiver errado feio procure descobrir o motivo e se algo deve ser feito diferente em um projeto futuro.


Espero que estas considerações ajudem vocês a terem mais projetos com sucesso. Lembre-se que são apenas a minha opinião e que nem de longe as considero condições necessárias ou suficientes para o sucesso.

quarta-feira, setembro 09, 2009

Google Code Jam 3009 - Watersheds

Vamos examinar agora o segundo problema da rodada de qualificação. Tive bastante dificuldade em enxergar uma forma de resolvê-lo, mas quando a achei a solução foi (na minha opinião) bastante eficiente.

O Problema

Resumindo o enunciado oficial:
  • Devem ser resolvidos até 100 casos de testes (T).
  • Em cada caso de teste é fornecido um mapa de elevação, que consiste em uma matriz de H linhas por W colunas de células. No small input o tamanho do mapa pode ser até 10x10 e no large input até 100x100.
  • Para cada célula é fornecida a sua altitude, que é um número inteiro (0 a 9 no small input e 0 a 9999 no large input).
  • Considera-se que a chuva que cai em cada célula irá ficar na célula ou fluir para uma das quatro células vizinhas (ao Norte, Sul, Leste e Oeste), conforme as altitudes delas. Se todas as células vizinhas tiverem altitude igual ou maior, a água ficará na célula que é considerada um dreno (sink). Caso contrário, a água irá pra a célula vizinha com altitude mais baixa. No caso de empate, escolhe-se a altitude mais baixa na ordem Norte, Oeste, Leste e Sul.
  • Formam-se assim bacias, que são conjuntos de células cuja água flui, direta ou indiretamente para o mesmo dreno. No small input garante-se que existirão no máximo 2 bacias, no large input podem ser até 16.
  • As bacias são identificadas por letras minúsculas de cima para baixo da direita para a esquerda.
  • O resultado solicitado é uma tabela com as identificações das bacias de cada célula.
A melhor forma de entender o problema é examinando um exemplo, no caso com um mapa 3 x 3.
No primeiro desenho temos o mapa com as altitudes. As setas no segundo indicam a direção da água. As cores no terceiro mostram as bacias, que são identificadas com as letras no último desenho.

Minha Solução

Percorrer as células determinando a direção da água é bastante simples, a questão é como determinar as bacias.

Minha primeira ideia era ir agrupando as células em conjuntos à medida em que determinava o fluxo. O que atrapalhava esta ideia era a possibilidade de ter uma bacia em formato de U, onde eu estaria determinando dois conjuntos separados que mais adiante eu teria que agrupar.

A coisa simplificou bastante quando me veio a ideia de olhar o resultado do final para o começo, seguindo a água no sentido contrário ao fluxo. Partindo de cada dreno temos uma árvore onde cada pai tem no máximo quatro filhos. Aproveitando o exemplo anterior:

Meu algoritmo ficou o seguinte:
  • Percorrer o mapa, determinando que são os drenos e marcando de onde vem a água para cada célula (o que cria as árvores).
  • Numerar as bacias, partindo de cada dreno e percorrendo cada célula da árvore correspondente.
  • Percorrer o mapa de cima para baixo, da esquerda para direita, para associar as letras corretas à numeração criada no item anterior.
Cada célula é armazenada em uma estrutura com os seguintes campos:
  • altitude
  • de onde vem a água (usei um bit para indicar cada uma das quatro direções possíveis)
  • um flag que indica se é um dreno
  • a bácia à qual a célula pertence
O código abaixo possui uma pequena alteração em relação ao que usei no Code Jam. Aqui map é uma matriz de duas dimensões, no meu código original era um vetor (matriz de uma dimensão) acessado através de lin*100+col (que no fundo é o código que o compilador vai gerar).
//
// Google CodeJam 2009 - Qualification Round, Problem B
// DQuadros
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
int alt;
char flows;
char sink;
char basin;
} Cell;

Cell map [100][100];
char letter [26];

#define FLOW_NORTH 1
#define FLOW_WEST 2
#define FLOW_EAST 4
#define FLOW_SOUTH 8

// recursive tree travel
void mark (int l, int c, char b)
{
map[l][c].basin = b;
if (map[l][c].flows & FLOW_NORTH)
mark (l-1, c, b);
if (map[l][c].flows & FLOW_SOUTH)
mark (l+1, c, b);
if (map[l][c].flows & FLOW_WEST)
mark (l, c-1, b);
if (map[l][c].flows & FLOW_EAST)
mark (l, c+1, b);
}

void main (void)
{
int iCase, nCases;
int H, W;
int lin, col, i;
char b;
int neighb [4]; // North, West, East, South.
int min;

scanf ("%d\n", &nCases);
for (iCase = 1; iCase <= nCases; iCase++)
{
// read dimensions
scanf ("%d %d\n", &H, &W);

// init map
for (lin = 0; lin < H; lin++)
{
for (col = 0; col < W; col++)
{
scanf ("%d ", &map[lin][col].alt);
map[lin][col].sink = 0;
map[lin][col].flows = 0;
}
}

// determine flow
for (lin = 0; lin < H; lin++)
{
for (col = 0; col < W; col++)
{
// find to where it will flow
if (lin == 0)
neighb [0] = 99999;
else
neighb [0] = map[lin-1][col].alt;
if (col == 0)
neighb [1] = 99999;
else
neighb [1] = map[lin][col-1].alt;
if (col == (W-1))
neighb [2] = 99999;
else
neighb [2] = map[lin][col+1].alt;
if (lin == (H-1))
neighb [3] = 99999;
else
neighb [3] = map[lin+1][col].alt;
min = 0;
if (neighb [1] < neighb[min])
min = 1;
if (neighb [2] < neighb[min])
min = 2;
if (neighb [3] < neighb[min])
min = 3;
if (map[lin][col].alt <= neighb[min])
{
// it's a sink
map[lin][col].sink = 1;
}
else
{
// mark where it comes from
switch (min)
{
case 0: // to North, from South
map[lin-1][col].flows |= FLOW_SOUTH;
break;
case 1: // to West, from East
map[lin][col-1].flows |= FLOW_EAST;
break;
case 2: // to East, from West
map[lin][col+1].flows |= FLOW_WEST;
break;
case 3: // to South, from North
map[lin+1][col].flows |= FLOW_NORTH;
break;
}
}

}
}

// follow trees from sink to upper lands
b = 0;
for (lin = 0; lin < H; lin++)
{
for (col = 0; col < W; col++)
{
if (map[lin][col].sink)
{
mark (lin, col, b);
b++;
}
}
}

// assign letters
for (i = 0; i < 26; i++)
letter[i] = 0;
b = 'a';
for (lin = 0; lin < H; lin++)
{
for (col = 0; col < W; col++)
{
if (letter [map[lin][col].basin] == 0)
letter [map[lin][col].basin] = b++;
}
}

// print result
printf ("Case #%d:\n", iCase);
for (lin = 0; lin < H; lin++)
{
for (col = 0; col < W; col++)
{
i = lin*100+col;
if (col > 0)
printf (" %c", letter [map[lin][col].basin]);
else
printf ("%c", letter [map[lin][col].basin]);
}
printf ("\n");
}
}
}

terça-feira, setembro 08, 2009

Projetos com Sucesso - III

Retomando esta série de posts, vou falar hoje sobre as atitudes de quem contrata o projeto (o cliente). Esta é uma visão delicada, já que estamos condicionados que "o cliente tem sempre a razão" e "culpar o cliente" é uma postura condenável (embora muito praticada). E assim caímos direto no primeiro ponto.

O Cliente Também É Responsável Pelo Sucesso do Projeto

Umas das expressões ouvidas quando um projeto descarrilha é "contratei vocês para não ter problemas" (ou algo equivalente). Quem contrata um projeto precisa estar ciente que mesmo a melhor empresa vai precisar do apoio seu apoio.

Conhecimentos sobre "as melhores práticas do segmento" precisam ser complementados com as características específicas do cliente. Em alguns casos estas características se sobrepõem às melhores práticas, e em outros geram a necessidade de cuidados especiais ao adotá-las.

Defina um Ponto de Contato Principal

É fundamental alocar uma pessoa para ser o contato principal com a empresa contratada. Esta pessoa não precisa necessariamente ter autonomia para decisões, mas precisa estar ciente de todas as comunicações, garantindo que elas cheguem às pessoas apropriadas. Muitos problemas de projeto ocorrem por decisões não serem tomadas ou informadas às pessoas corretas.

O ideal é que esta pessoa exerça uma função de Gerente de Projeto, acompanhando o cronograma e os resultados.

O caminho inverso também é importante: é preciso saber que é o ponto de contato principal na empresa contratada. Muitos clientes assumem que esta pessoa é o representante comercial que o atendeu durante as negociações, mas em todas empresas que conheço a responsabilidade muda de mãos após o fechamento do negócio.

Envolva As Pessoas Corretas, o Mais Cedo Possível

Por mais estranho que pareça, muitos clientes só envolvem na implantação as pessoas que serão os usuários do projeto. Estas pessoas precisam ser envolvidas no começo, para darem o seu depoimento sobre o processo atual e necessidades. Este envolvimento cria também uma certa "cumplicidade" com o projeto, que passa a ser também delas e não algo que está sendo "imposto de cima para baixo".

Além dos usuários diretos, outras pessoas serão afetadas, de forma nem sempre facilmente prevista. O envolvimento delas diminui a probabilidade de surpresas desagradáveis durante ou logo após a implantação.

Não Menospreze a Documentação

Muitas pessoas (e não somente no lado do cliente, isto se aplica também à empresa e ao desenvolvedor) tendem a tratar documentação como uma burocracia que atraza o andamento real do projeto.

O primeiro documento importante é a proposta, que precisa definir de forma clara o escopo. O segundo é o detalhamento da especificação. Lembre-se que mudar no papel é sempre mais fácil que mudar um projeto pronto. A especificação detalhada é também a base para os testes. O terceiro documento é o manual, que contém as instruções de instalação e operação e será a base para resolver dúvidas rapidamente, sem ter que consultar o fornecedor.

Tente Manter a Calma Quando as Coisas Dão Errado

É natural que o cliente fique descontente quando prazos não são cumpridos e as coisas não funcionam como esperado. Nesta hora é preciso que todos mantenham a calma e foquem em como colocar o projeto nos trilhos.

O pior que pode ser feito é se deixar levar pela raiva e tentar consertar o projeto "no grito". Ataques pessoais devem particularmente evitados, pois não contribuem em nada com a solução dos problemas. Infelizmente já tive a oportunidade de ver clientes que "queimaram todas as pontes" com o fornecedor. O resultado nestes casos, quando o projeto não é simplesmente abortado para prejuízo e alívio mútuo, é um sistema extremamente ruim encerrado pelo cansaço das duas partes. E o sistema permanece desta forma, pois não existe clima para continuidade dos trabalhos. Após uns poucos anos de operação capenga um novo projeto é iniciado, retomando o ciclo.

Prepare os Testes de Aceitação

Testar um projeto (particularmente um de software) é uma coisa complexa.

O primeiro ponto a planejar é como (e onde) viabilizar um teste. Isto pode exigir disponibilizar equipamentos extras (como um servidor de teste) e montar uma operação simulada (envolvendo pessoas, equipamentos e materiais).

O segundo ponto é pensar o que se quer testar. A especificação detalhada é a base para isto.

O terceiro ponto é detalhar o procedimento de teste e preparar os dados necessários. Muitas vezes se vê testes totalmente aleatórios e desorganizados; além de não cobrirem adequadamente o projeto estes testes são muitas vezes irreprodutíveis.

Um bom roteiro de teste servirá não somente para um primeiro teste mas também para verificar que os problemas encontrados foram solucionados e que outros erros não foram introduzidos e para validar versões posteriores.

Faça Uma Implantação Gradual

É normal surgirem dificuldades operacionais quando um novo processo é introduzido. É também possível que sejam encontrados problemas, por melhor que tenham sido os testes. É, portanto, importante que a implantação seja gradual e com uma opção de contingência (se possível sendo usada em paralelo).

Aqui cabe o relato de um caso real. Certa vez um cliente estava implantando um sistema que ia ser usado nas seis docas da sua expedição. No primeiro dia o gerente juntou todos os funcionários, fez uma apresentação bem detalhada de todo o sistema e mandou todos trabalharem. Não demorou muito para ser chamado para uma das docas para tirar uma dúvida. Antes de acabar de resolvê-la, uma outra doca já estava parada aguardando para tirar outra dúvida. O gerente passou o dia todo correndo de uma doca para outra. No fim do dia estava cansado, frustado e a produtividade estava lá em baixo. No dia seguinte ele resolveu usar uma tática diferente: deixou cinco docas trabalhando com o sistema antigo e ficou direto na doca restante. Ao final da manhã os funcionários daquela doca já estavam seguros na operação do novo sistema; à tarde ele os deixou trabalhando sozinhos e foi para a segunda doca. Ao final do dia ele estava com duas docas operando com o sistema novo e os ganhos de produtividade já começavam a ser sentidos. E ele estava bem menos cansado. Mais dois dias e todas as docas estavam operando o novo sistema. Se o gerente tivesse insistido em implantar simultaneamente em todas as docas era bem provável que o sistema tivesse sido "queimado".

Evolua o Sistema

Um engano comum é pensar que um sistema está pronto quando foi implantado. Isto se deve às vezes pelo desgaste durante o projeto, mas muitas vezes é apenas um visão equivocada.

Durante o projeto é comum surgirem muitas ideias, a maioria das quais são deixadas de lado por não estarem no escopo. O uso real do sistema é também fonte para ideias de aperfeiçoamento. Estas ideias não devem ser desperdiçadas!

A maioria das empresas fornece apenas correções durante a garantia. Contratos de manutenção às vezes incluem pequenos aperfeiçoamentos; poucos clientes optam por estes contratos e, dentre os que optam, muitos simplesmente os sub-utilizam. Um outro ponto a favor dos contratos de manutenção é que a empresa contratada fica obrigada a manter profissionais preparados para dar suporte e manutenção. Embora na prática muitas empresas continuem dando suporte após o término da garantia, com o passar dos anos é grande o risco das pessoas envolvidas terem mudado de cargo ou deixado a empresa e não estarem mais disponíveis pessoas que conheçam o projeto ou mesmo as tecnologias envolvidas.

segunda-feira, setembro 07, 2009

Google Code Jam 2009 - Alien Language

Neste post vou discutir o primeiro problema da rodade de qualificação do Google Code Jam 2009. Se você não quiser ver a solução (ou preferir tentar resolver primeiro), pare de ler por aqui e vá para a página oficial.

O Problema

O enunciado completo está, é claro, na página oficial. Segue um resumo:
  • É fornecido um conjunto (dicionário) de D palavras, todas com exatamente L letras minúsculas ('a' a 'z'). No pior caso (large input) D pode ser 5000 e L 15.
  • Devem ser resolvidos N casos de teste. No large input N pode chegar a 500.
  • Em cada caso de teste é preciso responder quantas palavras do dicionário atendem a um determinado padrão.
  • O padrão contem L partes, cada uma correspondendo a uma letra da palavra. Uma parte pode ser uma letra isolada (indicando que somente ela pode ser aceita nesta posição) ou uma sequência de letras cercada por parenteses (indicando que pode ser aceita qualquer uma destas letras nesta posição).
Por exemplo, considerando L = 3, D = 5 e o dicionário

aaa
abc
baa
bbb
xyz

o padrão (ab)a(ac) é atendido por duas palavras (aaa e baa).

Minha Solução

Adotei uma solução "força-bruta", gerando as combinações correspondente ao padrão e procurando-as, uma a uma, no dicionário. Para otimizar a busca no dicionário, ele é ordenado (usando o qsort da biblioteca do C) e feita uma busca binária. Cheguei a pensar em algo mais sofisticado, mas o dicionário é relativamente pequeno (5000 itens requerem no máximo 13 comparações na busca binária).

Minha primeira versão, que gerava todas as combinações, estava muito lenta. Para acelerar, eu passei a testar as combinações parciais e deixei de gerar combinações cujo começo já não estivessem no dicionário. Isto é útil na medida em que o tamanho das palavras aumenta e poucas palavras atendam ao padrão. Não é maravilhoso, mas conseguiu resolver o large input dentro do tempo estipulado (com boa folga).

O meu código ficou assim (qualquer semelhante com a minha solução do primeiro problema do ano anterior é mero cut-and-paste)

//
// Google CodeJam 2009 - Qualification Round, Problem A
// DQuadros
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Dictionary
#define MAX_WORDS 5000
#define MAX_L 15
int nW = 0;
char Words [MAX_WORDS][MAX_L+1];
int order [MAX_WORDS];

// Compare words for qsort
int compWord (const void *elem1, const void *elem2)
{
int i1 = *((int *) elem1);
int i2 = *((int *) elem2);
int dif = strcmp (Words[i1], Words[i2]);
return dif;
}

// Find a partial Word
// (good old binary search)
int FindWordN (char *w, int n)
{
int first, last, mid, dif;

first = 0;
last = nW-1;
while (last >= first)
{
mid = (last+first)/2;
dif = memcmp (Words[order[mid]], w, n);
if (dif == 0)
return mid;
else if (dif < 0)
first = mid + 1;
else
last = mid - 1;
}
return -1; // not found
}

void main (void)
{
int iCase, nCases;
int L, D;
char word [16];
int nHits;
char query [26*15+1];
char qt [15] [27];
int pos [15];
int i, j, k;

scanf ("%d %d %d\n", &L, &D, &nCases);

// Read the dictonary
for (nW = 0; nW < D; nW++)
{
gets (word);
strcpy (Words[nW], word);
order[nW] = nW;
}
qsort (order, nW, sizeof(int), compWord);

for (iCase = 1; iCase <= nCases; iCase++)
{
// Process the query
gets (query);
nHits = 0;
for (i = j = 0; query[i] != 0; i++, j++)
{
if (query[i] == '(')
{
i++;
for (k = 0; query[i] != ')'; i++, k++)
qt [j][k] = query[i];
qt [j][k] = 0;
}
else
{
qt [j][0] = query [i];
qt [j][1] = 0;
}
}

i = 0;
pos[0] = 0;
word[L] = 0;
while (1)
{
word[i] = qt[i][pos[i]];
if (FindWordN (word, i+1) != -1)
{
if (i == (L-1))
{
nHits++;
}
else
{
i++;
pos[i] = -1;
}
}
pos[i]++;
while (qt[i][pos[i]] == 0)
{
i--;
if (i < 0)
break;
pos[i]++;
}
if (i < 0)
break;
}

printf ("Case #%d: %d\n", iCase, nHits);
}

}
Uma Solução Melhor

Uma das coisas legais no Code Jam é que o código fonte dos participantes fica disponível para download, o que permite garimpar soluções interessantes. No caso eu "encontrei ouro" logo na solução de quem ficou em primeiro (que se identifica como 'liszt1990').

Ao invés de gerar as combinações, o que ele faz é testar cada palavra do dicionário contra o padrão. Isto é melhor, pois ele utiliza uma forma muito eficiente para testar se uma palavra atende ao padrão. Cada parte do padrão é expandida para um vetor de 26 posições, cada uma indicando se a letra correspondente é aceita. O teste de uma posição se resume assim a uma indexação.

O código abaixo é a minha implementação desta ideia (o código original de liszt1990 pode ser baixado do site).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Dictionary
#define MAX_WORDS 5000
#define MAX_L 15
int nW = 0;
char Words [MAX_WORDS][MAX_L+1];

void main (void)
{
int iCase, nCases;
int L, D;
int nHits;
char query [28*15+1];
char qt [15] [26];
int i, j;

scanf ("%d %d %d\n", &L, &D, &nCases);

// Read the dictonary
for (nW = 0; nW < D; nW++)
gets (Words[nW]);

for (iCase = 1; iCase <= nCases; iCase++)
{
// Process the query
gets (query);
memset (qt, 0, sizeof(qt));
for (i = j = 0; query[i] != 0; i++, j++)
{
if (query[i] == '(')
{
i++;
for (; query[i] != ')'; i++)
qt [j][query[i]-'a'] = 1;
}
else
{
qt [j][query[i]-'a'] = 1;
}
}

// Check words in dictionary
nHits = 0;
for (i = 0; i < nW; i++)
{
for (j = 0; j < L; j++)
if (qt [j] [Words[i][j]-'a'] == 0)
break;
if (j == L)
nHits++;
}

printf ("Case #%d: %d\n", iCase, nHits);
}

}

domingo, setembro 06, 2009

Os Álbuns dos Beatles - Please Please Me


"Please Please Me" é o primeiro álbum dos Beatles, sendo notável por vários motivos.

O primeiro deles é que é essencialmente um álbum ao vivo. George Matin quis lançar o álbum rapidamente e a solução foi gravar o repertório habitual dos shows dos Beatles. Os recursos técnicos da época não permitiam grandes alterações no que tinha sido gravado (o que hoje é padrão nos discos chamados de "ao vivo").

A gravação da maior parte do álbum foi feita em um dia (11 de fevereiro de 1963), das 10 da manhã até um pouco depois das 10 da noite (iniciando uma rotina de quebrar as regras do estúdio). As quatro músicas adicionais tinham sido gravadas anteriormente e lançadas em compactos.

A gravação foi feita em dois canais. Na época a mixagem mais importante para os discos "pop" era a mono (visando as vitrolas portáteis dos jovens). Por este motivo, a gravação concentrava os intrumentos em um canal e os vocais no outro; o que permitia controlar o volume relativo dos vocais na mixagem. Como consequência, as versões estéreo dos primeiros discos dos Beatles soa estranha.

Das catorze músicas no disco, nada menos de oito eram composições de Lennon/McCartney (por erro indicadas na capa e no disco a McCartney/Lennon). Na época era uma surpresa um grupo (ainda mais novo) lançar um disco onde eles próprios fossem responsáveis pelos vocais, instrumentos e composição. Com o sucesso dos Beatles, isto passaria a ser mais frequente.

Mais um detalhe curioso: a faixa título foi gravada e lançada como compacto antes da gravação do resto do álbum. Posteriormente ao lançamento do álbum foram lançados dois singles com músicas extraídas do álbum.

O álbum mostra alguns dos pontos que iriam caracterizar as obras dos Beatles: composições inspiradas, bons vocais e boas harmonias e sacadas de produção (como a inclusão da contagem no início do disco).

Vamos às músicas.

I Saw Her Standing There

Uma composição principalmente de Paul, completada com a ajuda de John. O vocal principal é de Paul, que inclui esta música em seus shows até hoje. É uma música enérgica, a começar pela contagem inicial em voz alta (que foi colada de um take diferente do restante da música).

Misery

Composição conjunta de John e Paul, que dividem os vocais. Esta música é uma das poucas que receberam uma sobreposição significativa (overdub), no caso o piano tocado por George Martin. Para facilitar, a gravação foi feita com o dobro da velocidade normal; a parte de piano foi tocada uma oitava a baixo (e mais lentamente) com a fita tocando a velocidade normal.

Anna (Go To Him)

Cover de uma balada lenta, cantada por John com backing de Paul e George. Na parte instrumental, Ringo cuida bem do ritmo incomum e George toca a guitarra que marca a música.

Chains

Música composta por Carole King e Gerry Goffin, tem vocal de George e a harmônica de John Lennon.

Boys

Outro cover, é a oportunidade de Ringo assumir os vocais.

Ask Me Why

Música de Johm, cantada por John, com harmonias de Paul e George.

Please Please Me

Composição de John (e cantada por ele), tinha originalmente um ritmo mais arrastado, tentando imitar Roy Orbison. Por sugestão de George Martin, o ritmo foi acelerado e surgiu assim o lado A do segundo compacto dos Beatles e seu primeiro grande sucesso. Traz as harmonias de George e Paul e a harmônica de John, característica desta fase inicial. A tocada competente de Ringo espantou de vez as dúvidas de George Martin.

Existem três mixagens diferentes desta música: a do compacto, a do álbum mono (com eco adicional) e a do álbum estéreo (refeita a partir das gravações originais).

Love Me Do

Considerada o começo do sucesso (lado A do primeiro compacto). George Martin pretendia que os Beatles gravassem uma música de outros compositores, mas eles insistiram em um música própria. É uma composição conjunta de John e Paul, que também dividem os vocais. Começa com a harmônica de John, que aparece novamente em outros pontos da música (o que obrigou Paul a assumir um pedaço de vocal que normalmente não cantava).

Foi gravada três vezes com bateristas diferentes: Pete Best, Ringo e Andy White (um músico de estúdio trazido por George Martin por não confiar em Pete e Ringo). A versão do álbum é a com Andy White.

P.S. I Love You

O lado B de Love Me Do, foi composta principalmente por Paul, que assume os vocais. Na bateria, novamente Andy White que coloca uma batida bem diferente da característica da fase inicial dos Beatles.

Baby It's You

Uma balada composta por Burt Bacharach, com John no vocal principal e harmonias de Paul e George.

Do You Want To Know A Secret

Composição conjunta de Paul e John, feita especificamente para ser cantada por George.

A Taste of Honey

Outro cover, cantado com a tradicional competência por Paul.

There's A Place

Outra composição conjunta de Paul e John. Destaque para os vocais em harmonia dos dois.

Twist And Shout

Fechando o álbum e a sessão do dia 11, John Lennon solta a voz neste cover. A gravação foi deixada por último justamente por forçar a voz de Lennon, que ainda por cima estava gripado no dia. O que se escuta no disco é o primeiro take; foi feita em seguida uma segunda gravação completa mas a voz de John estava realmente gasta.

Para quem perde tempo comparar John com Paul: Paul gravaria outro número "destrói garganta" (Long Tall Sally) também em um take.

sábado, setembro 05, 2009

Livro de Agosto: Failure Is Not An Option

"Failure Is Not An Option" é um relato muito especial do programa espacial americano do projeto Mercury ao projeto Apollo. O autor é Gene Kranz; a forma mais simples de dizer quem ele é citar que foi representado por Ed Harris no filme Apollo 13; lembrou dele?

A minha cópia deste livro tem uma história especial. Em 2000 eu fui para uma conferência nos EUA e a palestra motivacional foi dada por ... Gene Kranz. Ao final da apresentação foram distribuídos alguns livros e eu tive a oportunidade de ganhar um autógrafo.


Gene Kranz

Gene Kranz é um real herói americano e o livro está repleto de um patriotismo que hoje pode parecer fora de moda. Antes de entrar para a NASA, foi piloto da força aérea americana e trabalhou em pesquisa e testes na McDonnell.

Como mostra a foto da capa, é extremamente sério. Absorto com o projeto espacial desde o início dos anos 60, ele manifesta a sua surpresa e incompreensão com os acontecimentos do final da década.

Seu entusiasmo e liderança foram fundamentais para a obtenção do que ele chama de "a irmandade", a camaradagem e confiança mútua entre controladores e astronautas.

Controle da Missão

O livro gira todo em torno do conceito do "Controle da Missão". Todo mundo já viu em algum filme a imagem da sala de controle, com um monte de pessoas sentadas na frente de um monte de consoles. As pessoas nestes consoles estão organizada em grupos com nomes como RETRO, Flight, FIDO. O diretor de voo é quem coordena o trabalho de todos eles e toma as decisões finais. Estas decisões são baseadas nas regras de voo, compostas principalmente de critérios Go/No-Go.

Outro ponto destacado no livro são as simulações efetuadas antes das missões. A equipe que planeja e controla as simulações mostram uma paixão quase sádica em testar os controladores. Este zelo foi fundamental para o sucesso da Apollo 11.

O Programa Espacial Americano

Os americanos estavam em nítida desvantagem no começo da corrida espacial (embora hoje se saiba que a diferença não era tão grande quanto parecia). O livro começa com o chamado "voo de 10 centímetros": no primeiro teste com o propulsor Redstone, o foguete "apagou" logo após começara a subir, deixando de pé um foguete cheio de combustível e totalmente desconectado do controle.

Quando ainda estavam obtendo os primeiros sucessos, Robert Kennedy assumiu a meta de colocar um homem na lua até o final da década de 60. O resultado foram os projetos Gemini e Apollo. Os voos do projeto Gemini, assim como os primeiros voos do Apollo, tinham por objetivo desenvolver uma a umas as técnicas necessárias para a viagem à Lua.

Ao final do projeto Gemini, os americanos estavam na frente dos russos (embora isto não fosse tão evidente na época). Veio então a primeira e única tragédia americana desta época, com a morte da tripulação da Apollo I em um teste preparatório rotineiro considerado não perigoso. Nove meses depois, os EUA estavam de volta à corrida com a Apollo 4.

Os voos seguintes do projeto Apollo foram bem sucedidos, culminando com o primeiro pouso na Lua com a Apollo 11, até a Apollo 13. Como todo mundo sabe, graças ao filme, as coisas deram errado logo no começo da viagem para a Lua e somente graças a um trabalho incrível dos controladores os astronautas conseguiram retornar sãos e salvos à Terra.

Embora não tenham ganhado o mesmo destaque que a Apollo 13, em quase todas as missões ocorreram momentos críticos, vários deles descritos no livro. Kranz chega a afirmar no livro que hoje se assusta com alguns dos riscos corridos e acha que hoje não existiria ambiente para assumí-los.

O Veredito Sobre o Livro

O livro contém inúmeras histórias interessantes, contadas por quem esteve lá. Porque demorei tanto para acabar de ler o livro? Acho que o problema é o estilo. Em alguns momentos Kranz se detêm em longas listas de nomes e biografias de pessoas que, apesar de importantes para o programa espacial americano, tem pouca relevância para o que está sendo contado. Existe também um amontoado de siglas que às vezes confunde o leitor. O resultado é um livro enfadonho em alguns momentos (principalmente entre as missões).

Conhecidos para quem emprestei o livro também o acharam arrastado em alguns pontos, mas não tão fortemente quanto eu.

Apesar disto eu recomendo o livro para os interessados no programa espacial. Talvez seja necessário um pequeno esforço para avançar por alguns trechos, mas o leitor certamente se sentirá recompensado.

sexta-feira, setembro 04, 2009

Google Code Jam - Qualification Round 2009

Apesar de tudo que andei escrevendo por aqui, acabei me preparando mal para o Google Code Jam. Os aborrecimentos do começo da semana também não ajudaram muito.

De qualquer forma, na quarta feira estava às 20:00 de frente do micro vendo a contagem regressiva para o início da competição. Nesta fase o tempo não é crítico, já que não existe limite do número de pessoas que passam para a fase seguinte e os problemas ficam disponíveis por 24 horas. O requisito para passar é acertar no mínimo um "small input" e um "large input". Para quem não está a par das regras, são três problemas a serem resolvidos. Para cada problema você pode fazer múltiplas tentativas de resolver um conjunto pequeno de dados ("small input") e apenas uma tentativa de resolver um conjunto grande de dados ("large input"). Nos dois casos existe um limite de tempo entre baixar os dados e enviar a resposta. O resultado do small input é validado na hora, o do large input somente no final do período de prova.

Está nos meus planos comentar cada um dos problemas, mas por hoje vou ficar apenas em uma visão geral. Em uma olhada rápida, o primeiro e o terceiro problemas tinham solução "força bruta" óbvia. O segundo problema me pareceu mais complicado.

Comecei pelo primeiro, implementando uma solução "força bruta" com pequenas otimizações. Quando estava com o programa pronto para tentar o "small input", o site começou a apresentar problema no download. Aproveitei a pausa forçada para fazer testes com volume de dados mais próximo do limite do "large input", o que me mostrou que o meu algorítmo estava muito ruim. Após alguns aperfeiçoamentos, consegui baixar o "small input" e o resultado foi aprovado na primeira. Entusiasmado, baixei o "large" e fiquei torcendo para dar tempo. Não foi instantâneo mas ficou dentro do limite e a partir daí era esperar 24 horas (pois o prazo foi dilatado em função dos problemas no download) para saber se estava certo. Neste ponto já tinham passado mais de duas horas, o que é mau sinal para as próximas etapas onde o tempo total para os três problemas é de 2 a 4 horas.

Ataquei em seguida o terceiro problema, novamente pela força bruta. O programa ficou pronto logo, mas se mostrava bastante lento. Como não exergava uma forma de otimizar, resolvi tentar o "small input" e novamente passei de primeira. No entusiasmo, parti para o "large input" e estourei o tempo.

Com as oportunidades reduzidas, resolvi pensar bastante no segundo problema antes de me arriscar. Fui durmir à meia-noite, com algumas idéias vagas. No começo da manhã seguinte comecei a pensar novamente no problema e finalmente achei uma forma inteligente de atacá-lo. O small input passou de primeira e o large input foi processado num piscar de olhos.

Quinta feira, 3 de setembro, 22:00 - a hora da verdade. E a internet cai (devido à chuva)! Após meia hora de espera, consigo acessar novamente o site. E confirmar que acertei os dois "large input" e estou na próxima fase.

Algumas estatísticas:
  • Os primeiros 2425 marcaram 99 pontos (tudo certo)
  • Dois competidores fizeram 89 pontos (erraram somente um small input e acertaram o large input nos acréscimos)
  • Os competidores nas posições 2428 a 3888 fizeram 76 pontos (erraram um large input). Estou aqui, em 2861.
  • Um competidor fez 69 pontos (acertou somente os large inputs!)
  • Os competidores nas posições 3890 a 4823 fizeram 66 pontos (erraram um small e um large)
  • Os competidores nas posições 4824 a 4828 fizeram 56 pontos
  • Os competidores nas posições 4829 a 5154 fizeram 53 pontos
  • Os competidores nas posições 5155 a 5949 fizeram 43 pontos
  • Os competidores nas posições 5950 a 7835 fizeram 33 pontos
  • Daqui para frente estão os que não passaram: 7836 a 7877 (30 pontos), 7878 a 7898 (23 pontos), 7899 a 8035 (20 pontos) e 8036 a 8605 (10 pontos)

quinta-feira, setembro 03, 2009

Engrossando as Estatísticas

Com o fim das férias prolongadas pela gripe suína, o trânsito em São Paulo voltou com tudo. Como consequência, acabei sendo forçado a mudar os meus trajetos habituais. Em particular, comecei a passar na volta do trabalho por uma rua com fama de perigosa. Não estou falando de uma rua pequena, mal iluminada, com pouco tráfego. É uma rua larga, mão única, com cinco pistas com um imenso Carrefour. O perigo vem justamente do excesso de carros.

Nas primeiras vezes que passei por ela, o transito estava pesado, mas fluindo. Segunda feira, perto das 19:00 ainda com luz ambiente, o transito estava completamente parado. Vidro fechado, atento... mas não adiantou nada. De repente três indivíduos se aproximaram do carro, anunciaram assalto e acabaram levando meu celular e a minha pasta. O prejuízo monetário não foi elevado, mas se foram documentos, contas, anotações, pen drives, etc. Há certo tempo eu ando preocupado com a quantidade de coisas que carregava na pasta, mas pouco tinha feito para reduzí-la.

Mais tarde, fui fazer o "B.O." na delegacia que fica na avenida paralela. Atendimento cortês, razoavelmente rápido (contando que tem que aguardar uma impressão em quatro vias em "near letter quality" em impressora matricia). Mas fica aquele ar de resignação de todos, de coisa inevitável que acontece toda hora e vai continuar acontecendo, um tracinho a mais na contabilidade das estatísticas.

Em contra partida, o Poupatempo de Osasco mostra como o serviço público pode ser excelente. Só não foi perfeito, pois não faz parte do treinamento o caso de brasileiros natos nascidos no exterior e isto complicou um pouco os atendentes. Mesmo assim, uma carteira de identidade solicitada no final da terça pode ser retirada hoje (quinta) cedo. A carteira de motorista, solicitada no fim a manhã de hoje, deve ter ficada pronta hoje mesmo no final do dia (só vou pegar amanhã).